227. Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7 " 3/2 " = 1 " 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.

思路：

用一个栈来保存数字，

如果之前的运算符是+，则将该数压入栈；

如果之前的运算符是-，则将该数的负数压入栈；

如果之前的运算符是*，则弹出栈顶数，和当前的数相乘压入栈；

如果之前的运算符是-，则弹出栈顶数，和当前的数相除压入栈；

注意处理最后一次的情况

class Solution { public: int calculate(string s) { int len = s.size(); stack<int> stk; int num = 0; char sign = '+'; for (int i = 0; i < len; i++){ if (isdigit(s[i])){ num = num * 10 + s[i] - '0'; } if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/'||i==len-1){//不加else if (sign == '+'){ stk.push(num); } else if (sign == '-'){ stk.push(-num); } else if (sign == '*'){ int top = stk.top(); stk.pop(); stk.push(top*num); } else{ int top = stk.top(); stk.pop(); stk.push(top/num); } sign = s[i]; num = 0; } } int res = 0; while (!stk.empty()){ res += stk.top(); stk.pop(); } return res; } };

224. Basic Calculator

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.

思路：遇到 '(' 就把之前的结果和符号push进stack. 遇到')'就把 当前结果*stack中的符号 再加上stack中之前的结果.

class Solution { public: int calculate(string s) { stack<int> stk; int len = s.size(); int res = 0; int sign = 1; int i = 0; while (i<len){ if (isdigit(s[i])){ int num = 0; while (i < len&&isdigit(s[i])){ num = num * 10 + s[i] - '0'; i++; } res += num*sign; } else if (s[i] == '+'){ sign = 1; i++; } else if (s[i] == '-'){ sign = -1; i++; } else if (s[i] == '('){ stk.push(res); stk.push(sign); res = 0; sign = 1; i++; } else if (s[i] == ')'){ res = res*stk.top(); stk.pop(); res += stk.top(); stk.pop(); i++; } else{ i++; } } return res; } };