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-negative integers and empty spaces .
You may assume that the given expression is always valid.
Some examples:
"1 + 1" = 2 " 2-1 + 2 " = 3 "(1+(4+5+2)-3)+(6+8)" = 23
Note: Do not use the eval built-in library function.
这道题让我们实现一个基本的计算器来计算简单的算数表达式，而且题目限制了表达式中只有加减号，数字，括号和空格，没有乘除，那么就没啥计算的优先级之分了。于是这道题就变的没有那么复杂了。我们需要一个栈来辅助计算，用个变量sign来表示当前的符号，我们遍历给定的字符串s，如果遇到了数字，由于可能是个多位数，所以我们要用while循环把之后的数字都读进来，然后用sign*num来更新结果res；如果遇到了加号，则sign赋为1，如果遇到了符号，则赋为-1；如果遇到了左括号，则把当前结果res和符号sign压入栈，res重置为0，sign重置为1；如果遇到了右括号，结果res乘以栈顶的符号，栈顶元素出栈，结果res加上栈顶的数字，栈顶元素出栈。代码如下：
解法一：
class Solution { public: int calculate(string s) { int res = 0, sign = 1, n = s.size(); stack<int> st; for (int i = 0; i < n; ++i) { char c = s[i]; if (c >= '0') { int num = 0; while (i < n && s[i] >= '0') { num = 10 * num + s[i++] - '0'; } res += sign * num; --i; } else if (c == '+') { sign = 1; } else if (c == '-') { sign = -1; } else if (c == '(') { st.push(res); st.push(sign); res = 0; sign = 1; } else if (c == ')') { res *= st.top(); st.pop(); res += st.top(); st.pop(); } } return res; } };
下面这种方法和上面的基本一样，只不过对于数字的处理略微不同，上面的方法是连续读入数字，而这种方法是使用了一个变量来保存读入的num，所以在遇到其他字符的时候，都要用sign*num来更新结果res，参见代码如下：
解法二：
class Solution { public: int calculate(string s) { int res = 0, num = 0, sign = 1, n = s.size(); stack<int> st; for (int i = 0; i < n; ++i) { char c = s[i]; if (c >= '0') { num = 10 * num + (c - '0'); } else if (c == '+' || c == '-') { res += sign * num; num = 0; sign = (c == '+') ? 1 : -1; } else if (c == '(') { st.push(res); st.push(sign); res = 0; sign = 1; } else if (c == ')') { res += sign * num; num = 0; res *= st.top(); st.pop(); res += st.top(); st.pop(); } } res += sign * num; return res; } };
本文转自博客园Grandyang的博客，原文链接：基本计算器[LeetCode] Basic Calculator ，如需转载请自行联系原博主。
