Description

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.

Example 1:

Input: "3+2*2"
Output: 7

Example 2:

Input: " 3/2 "
Output: 1

Example 3:

Input: " 3+5 / 2 "
Output: 5

Note:

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

Solution

这道题的重点就是，将string按照+和-分割，将每段计算的中间结果存储到stack中，最后累加即可。

还需要注意的是，string中可能会出现两位以上的数字，千万别忘了啊。

Stack, time O(n), space O(n)

class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        int num = 0;
        char sign = '+';
        
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            
            if (Character.isDigit(c)) {
                num = num * 10 + c - '0';
            }
            
            if ("+-*/".indexOf(c) >= 0 || i == s.length() - 1) {  // important
                if (sign == '+') {
                    stack.push(num);
                } else if (sign == '-') {
                    stack.push(-num);
                } else if (sign == '*') {
                    stack.push(stack.pop() * num);
                } else {
                    stack.push(stack.pop() / num);
                }
                
                sign = c;
                num = 0;    // clear num
            }
        }
        
        int res = 0;
        
        while (!stack.empty()) {
            res += stack.pop();
        }
        
        return res;
    }
}

Iteration, time O(n), space O(1)

从上面的解法中可以看出，遍历string的过程中，只跟stack的栈顶元素发生关系。所以可以去掉stack，用一个变量代表栈顶元素即可。

class Solution {
    public int calculate(String s) {
        int res = 0;
        char sign = '+';  // sign prior to current num
        
        for (int i = 0, num = 0, pre = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                num = num * 10 + (int)(c - '0');
            }
            if ("+-*/".indexOf(c) >= 0 || i == s.length() - 1) {
                if (sign == '+') {
                    pre = num;
                } else if (sign == '-') {
                    pre = -num;
                } else if (sign == '*') {
                    res -= pre;
                    pre *= num;
                } else {
                    res -= pre;
                    pre /= num;
                }
                sign = c;
                num = 0;
                res += pre;
            }
        }
        
        return res;
    }
}