LeetCode [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 .

Example 1:

Input: "1 + 1"
Output: 2

Example 2:

Input: " 2-1 + 2 "
Output: 3

Example 3:

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

Note:

• You may assume that the given expression is always valid.
• Do not use the eval built-in library function.

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 60 61 62 63 64 65

class Solution { stack<int> ops, nums; public: int calculate(string s) { int lhs = 0, rhs = 0, sign = 1; for(auto c:s){ if(isdigit(c)){ rhs = rhs*10+(c-'0'); }else{ lhs += sign * rhs; rhs = 0; if(c=='+') sign = 1; else if(c=='-') sign = -1; else if(c=='('){ ops.push(sign); nums.push(lhs); sign = 1; lhs = 0; }else if(c==')'){ lhs = nums.top() + ops.top()*lhs; nums.pop(); ops.pop(); } } } return lhs + sign*rhs; } }; class Solution { public: int calculate(string s) { stack<int> nums; stack<char> ops; int i = 0, n = s.size(); while(i<n){ if(s[i]==' '){ while(i<n && s[i]==' ') ++i; }else if(s[i]=='('||s[i]=='+'||s[i]=='-'){ ops.push(s[i++]); }else{ int rhs = 0; if(s[i]>='0' && s[i]<='9'){ while(i<n && s[i]>='0' && s[i]<='9') rhs = rhs*10+(s[i++]-'0'); }else{//')' ++i; rhs = nums.top(); nums.pop(); ops.pop();//pop '(' } while(!ops.empty() && ops.top()!='('){ int lhs = nums.top(); nums.pop(); switch(ops.top()){ case '+': rhs = lhs + rhs; break; case '-': rhs = lhs - rhs; break; } ops.pop(); } nums.push(rhs); } } return nums.top(); } };

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

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();//pop '(' }else{//'+', '-' if(hasV) nums.push(v); v = 0; hasV = false; if(!ops.empty() && precedence(ops.peek())>=precedence(c)) evaluate(nums, ops); ops.push(c); } } return nums.pop(); } int precedence(char op){ switch(op){ case '(' : return -1; case '+' : return 0; case '-' : return 0; 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; default: break; } nums.push(result); } }