AdSense

Tuesday, October 4, 2016

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 .
You may assume that the given expression is always valid.
Some examples:


"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

At first attempt, I used a stack. It did work, the solution got accepted. But when I revisit the problem, I think the code is too clumsy. So I searched online and find an easier solution. We know that there are only plus and minus operations. So we can just append signs to numbers and add all the numbers together. A stack is still needed to track the effects of parentheses because when we remove parentheses, the sign is changed. Every time we see a left parenthesis,  we need to push the sign to the stack. Note that we need to multiply current sign with stack.peek() before pushing it, that's because we want to pass the effect of the outer parenthesis to this one. For example, 1-(1-(1-1)), when we see the second parenthesis, we need to push -1 * -1 = 1 to stack.


public int calculate(String s) {
        int len = s.length();
        if (len == 0) {
            return 0;
        }
        Stack operators = new Stack<>();
        operators.push(1);
        int rst = 0, index = 0, sign = 1;
        
        while (index < len) {
            char c = s.charAt(index);
            if (c == '+') {
                sign = 1;
                index++;
            } else if (c == '-') {
                sign = -1;
                index++;
            } else if (c == '(') {
                operators.push(sign * operators.peek());
                index++;
                sign = 1;
            } else if (c == ')') {
                operators.pop();
                index++;
            } else if (c == ' ') {
                index++;
            }else {
                int pos = index;
                while (pos < len && Character.isDigit(s.charAt(pos))) {
                    pos++;
                }
                rst += Integer.valueOf(s.substring(index, pos)) * sign * operators.peek();
                index = pos;
            }
        }
        return rst;
    }


No comments:

Post a Comment