题目描述
Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negativeintegers and empty spaces .
题目大意
实现一个最基本的计算器，输入一个字符串，字符串中只包含 ‘0-9’，‘+’，‘-’，‘ ’。
示例
E1
E2
E3
解题思路
基本不需什么复杂的算法，只需要细心的思考所有可能的情况就好。
例如，
输入的数字可能会布置一位数字，有可能会有多位整数；
输入中存在负数；
输入中存在多个多余的空格，其空格的位置不确定；
输入的数字之前出现多余的 ‘+’ 表示正数；
。。。
解决方案是先对字符串进行初始化，将字符串中的空格去除，同时如果出现数字之前有多余操作符表示正负数，插入数字 ‘0’ 来表示正常的运算，方便之后的计算（例如输入的是“ - 2 + 1”会被处理成“0-2+1”）。之后通过入栈出栈操作来进行基本的算术运算即可。
复杂度分析
时间复杂度：O(N)
空间复杂度：O(N)
代码
class Solution { public: int calculate(string s) { init(s); // 遍历字符串，将运算数与操作符分别入栈，遇到操作符 ’）‘时将该括号内的运算结 // 果计算完毕，并入栈 int len = s.length(); for(int i = 0; i < len; ++i) { if(s[i] >= ‘0‘ && s[i] <= ‘9‘) { int tmp = s[i] - ‘0‘, j = i + 1; while(s[j] >= ‘0‘ && s[j] <= ‘9‘) { tmp *= 10; tmp += s[j] - ‘0‘; ++j; } num.push(tmp); i = j - 1; } else { if(s[i] == ‘(‘) { op.push(s[i]); } else if(s[i] == ‘)‘) { cal(); } else { op.push(s[i]); } } } cal(); return num.top(); } // 处理初始的字符串，使其符合正常的运算规律 void init(string& s) { bool f = true; string::iterator iter = s.begin(); while(iter != s.end()) { if(*iter == ‘ ‘) { s.erase(iter); } else if(*iter >= ‘0‘ && *iter <= ‘9‘) { f = false; ++iter; } else if(*iter != ‘(‘ && *iter != ‘)‘){ if(f) { s.insert(iter, ‘0‘); f = false; } else { f = true; } ++iter; } else { ++iter; } } } // 进行基本运算，需注意，应使用另一个栈来保存运算树和操作数，因为第一次入栈的 // 顺序并非应该的运算顺序（从左向右），因此应该将顺序改变 void cal() { stack<int> tmp_n; stack<char> tmp_o; while(num.size() > 1) { if(op.top() == ‘(‘) { op.pop(); break; } tmp_n.push(num.top()); num.pop(); tmp_o.push(op.top()); op.pop(); } tmp_n.push(num.top()); num.pop(); while(!tmp_o.empty()) { int a, b; char o = tmp_o.top(); tmp_o.pop(); a = tmp_n.top(); tmp_n.pop(); b = tmp_n.top(); tmp_n.pop(); tmp_n.push(o == ‘+‘ ? a + b : a - b); } num.push(tmp_n.top()); } private: stack<int> num; stack<char> op; };
原文：https://www.cnblogs.com/heyn1/p/11085022.html