227 Basic Calculator II

227. Basic Calculator II

1. Question

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers,+,-,*,/operators and empty spaces. The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note:Do not use theevalbuilt-in library function.

2. Implementation

思路：这题只用考虑运算符号中乘号和除号需要考虑运算的优先级，但没有括号，所以整体来说难度降低了。和Basic Calculator I类似，我们仍然利用stack，但这时stack保存的不是正负号，而是之前运算的结果。当我们遇到加号或者减号时，直接将num或者-num放在stack。当我们遇到乘号或者除号时，我们需要将stack存的一个元素pop出来，与num相乘或者相除，然后再将结果放回stack。最后将stack的结果全都相加，得到最后的解。注意，当遇到输入只有数字，比如“111”，这类情况，我们必须在要将num放在stack里，不然最后stack是空的。

class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        int num = 0, res = 0;
        char sign = '+';
        Stack<Integer> stack = new Stack<>();
        int len = s.length();

        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);

            if (Character.isDigit(c)) {
                num = 10 * num + c - '0';
            }
            //字符是运算符或者到达字符串结束处，需要计算最后一次结果 
            if (isOperator(c) || i == len - 1) {
                if (sign == '+') {
                    stack.push(num);
                }
                else if (sign == '-') {
                    stack.push(-num);
                }
                else if (sign == '*') {
                    stack.push(stack.pop() * num);
                }
                else if (sign == '/') {
                    stack.push(stack.pop() / num);
                }
                sign = c;
                num = 0;
            }
        }

        while (!stack.isEmpty()) {
            res += stack.pop();
        }
        return res;
    }

    public boolean isOperator(char c ) {
        return c == '+' || c == '-' || c == '*' || c == '/';
    }
}

3. Time & Space Complexity

时间和空间都是O(n)

4. Follow Up

如果输入里还包含'(', ')'该怎么办？

http://www.lintcode.com/en/problem/expression-evaluation/