2015年7月18日星期六

LeetCode: Basic Calculator

Way 1: transition from (inorder expression / infix notation) to (RPN(reverse polish notation) / postfix notation)
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








没有评论:

发表评论