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+22" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Code

public class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) return 0;
        
        Stack<Integer> nums = new Stack<>();
        Stack<Character> ops = new Stack<>();
        StringBuilder sb = new StringBuilder();
        int i = 0;
        
        while (i < s.length()) {
            char c = s.charAt(i);
            if (c == ' ') {
                i++;
                continue;
            }
            if (c >= '0' && c <= '9') {
                sb.append(c);
                i++;
                for (; i < s.length(); i++) {
                    char ci = s.charAt(i);
                    if (ci >= '0' && ci <= '9') {
                        sb.append(ci);
                    } else {
                        break;
                    }
                }
                nums.push(Integer.parseInt(sb.toString()));
                sb.delete(0, sb.length());
                continue;
            }
            if (c == '*' || c == '/') {
                if (ops.isEmpty() || (ops.peek() == '+' || ops.peek() == '-')) {
                    ops.push(c);
                }
                else {
                    while (!ops.isEmpty() && ops.peek() != '+' && ops.peek() != '-') {
                        cal(nums, ops);
                    }
                    ops.push(c);
                }
                i++;
                continue;
            }
            if (c == '+' || c == '-') {
                while (!ops.isEmpty()) {
                    cal(nums, ops);
                }
                ops.push(c);
                i++;
                continue;
            }
        }
        
        while (!ops.isEmpty()) {
            cal(nums, ops);
        }
        return nums.pop();
    }
    
    public void cal(Stack<Integer> nums, Stack<Character> ops) {
        char op = ops.pop();
        int b = nums.pop();
        int a = nums.pop();
        nums.push(calculate(a, b, op));
    }
    
    public int calculate(int a, int b, char op) {
        switch (op) {
            case '+':
                return a + b;
            case '-':
                return a - b;
            case '*':
                return a * b;
            case '/':
                return a / b;
        }
        return 0;
    }
}

Solution

与Basic Calculator思路相似，利用数字栈和符号栈进行计算。

当符号为+或者-时，依次弹出符号栈中的符号并进行计算。当符号为或者/时，先判断栈顶符号，若栈顶符号为或者/则依次弹出符号栈中的符号进行计算，若栈顶符号为+或者-则直接入栈。