LeetCode [772] Basic Calculator III

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 .

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

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2147483648, 2147483647].

Some examples:

"1 + 1" = 2
" 6-4 / 2 " = 4
"2*(5+5*2)/3+(6/2+8)" = 21
"(2+6* 3+5- (3*14/7+2)*5)+3"=-12

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

typedef long long ll; class Solution { stack<int> nums; stack<char> ops; ll eval(){ int op = ops.top(); ops.pop(); ll v2 = nums.top(); nums.pop(); ll v1 = nums.top(); nums.pop(); switch(op){ case '+': return v1+v2; case '-': return v1-v2; case '*': return v1*v2; case '/': return v1/v2; } return 0; } bool op1first(char op1, char op2){ return (op1=='*'||op1=='/')&&(op2=='+'||op2=='-'); } public: int calculate(string s) { ll val = 0; int n = s.size(); for(int i=0; i<n; ++i){ char c = s[i]; if (c==' ') continue; if (isdigit(c)){ val = val*10+(c-'0'); if(i==n-1 || !isdigit(s[i+1])) {nums.push(val); val = 0;} }else{ if(c=='(') ops.push(c); else if(c==')'){ while(!ops.empty() && ops.top()!='('){ nums.push(eval()); } ops.pop(); }else{//+-*/ while(!ops.empty() && op1first(ops.top(), c)){ nums.push(eval()); } ops.push(c); } } } while(!ops.empty()){ nums.push(eval()); } return nums.top(); } };