LeetCode [772] Basic Calculator III

 772. Basic Calculator III

Hard

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 54 55 56 57 58 59

class Solution { public int calculate(String s) { Stack<Integer> nums = new Stack<>(); Stack<Character> ops = new Stack<>(); int v = 0; boolean hasV = false; s += '+'; for(char c:s.toCharArray()){ if(c==' ') continue; else if(Character.isDigit(c)){ v = v*10 + c - '0'; hasV = true; }else if(c=='('){ ops.push(c); }else if(c==')'){ if(hasV) nums.push(v); v = 0; hasV = false; while(!ops.empty() && ops.peek()!='(') evaluate(nums, ops); ops.pop(); }else{//'+', '-' if(hasV) nums.push(v); v = 0; hasV = false; while(!ops.empty() && precedence(ops.peek())>=precedence(c)) evaluate(nums, ops); ops.push(c); } } return nums.pop(); } int precedence(char op){ switch(op){ case '+' : return 0; case '-' : return 0; case '*' : return 1; case '/' : return 1; default: return -2; } } void evaluate(Stack<Integer> nums, Stack<Character> ops){ int r = nums.pop(); int l = nums.pop(); char op = ops.pop(); int result = 0; switch (op) { case '+' : result = l+r; break; case '-' : result = l-r; break; case '*' : result = l*r; break; case '/' : result = l/r; break; default: break; } nums.push(result); } }