Shunting-yard algorithm or operator-precedence parsing
Further discussed in Basic Calculator II
Way 2: O(n)
Below is a widely used JAVA example ( not written by me):
Running the test expression in mind is the best way to understand it.
e.g. 2-(5-6); 3-(2-(5-6)+3);
This solution uses a stack to store operators based on parentheses and calculates the result orderly.
In an expression, the operands are always one more than operator. So we need to push 1 twice into stack at the
beginning to make sure that there is at least one element stored in the bottom of stack for the next operator to
get stack.peek()
The Key is to realize that operators in parentheses is based on the status before the parentheses.
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 | public class Solution { public int calculate(String s) { Stack<Integer> stack = new Stack<Integer>(); stack.push(1); stack.push(1); int res = 0; for(int i=0; i<s.length(); i++){ char tmp = s.charAt(i); if(Character.isDigit(tmp)){ int num = tmp - '0'; int j = i+1; while(j<s.length() && Character.isDigit(s.charAt(j))){ num = num * 10 + s.charAt(j) - '0'; j++; } i = j-1; res += stack.pop() * num; }else if(tmp == '+' || tmp == '('){ stack.push(stack.peek()); }else if(tmp == '-'){ stack.push(-1*stack.peek()); }else if(tmp == ')'){ stack.pop(); } } return res; } } |
My codes(c++):
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 | class Solution { public: int calculate(string s) { int res = 0; stack<bool> mystack; mystack.push(true); mystack.push(true); for(int i = 0; i < s.size(); i++){ char c = s[i]; if(c == '+' || c == '(') mystack.push(mystack.top()); if(c == '-') mystack.push(!mystack.top()); if(c == ')') mystack.pop(); if(isdigit(c)){ int num = c - '0'; int j = i + 1; while(j < s.size() && isdigit(s[j])){ num = num * 10 + s[j] - '0'; j++; } i = --j; if(mystack.top()) res += num; else res -= num; mystack.pop(); } } return res; } }; |
Reference:
Wikipedia--RPN
explains the steps well
JAVA example
没有评论:
发表评论