0227. Basic Calculator II.md

Solution1

class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Deque<Integer> stack = new LinkedList<>();
        int num = 0;
        int res = 0;
        char preSign = '+';
        
        for (int i = 0; i < s.length(); i++) {
            if (Character.isDigit(s.charAt(i))) {
                num = 10 * num + s.charAt(i) - '0';
            }
            if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == s.length() - 1) {
                if (preSign == '+') {
                    stack.push(num);
                }
                if (preSign == '-') {
                    stack.push(-num);
                }
                if (preSign == '*') {
                    stack.push(stack.pop() * num);
                }
                if (preSign == '/') {
                    stack.push(stack.pop() / num);
                }
                num = 0;
                preSign = s.charAt(i);
            }
        }
        while (!stack.isEmpty()) {
            res += stack.pop();
        }
        return res;
    }
}

note

• time O(n) space O(n)
• The idea is to use stack to store our numbers. When the previous sign is '+' or '-', we simply push numbers into our stack. Note that if preSign is '-', we push -num into our stack. When the preSign is '*' or '/', we pop a number from the stack and calculate the result with the current number we have and push back the result to the stack. After the first iteration, all the operation left in the stack is adding. We simply pop out all numbers in the stack and add them to the result.
• Notice that the following condition:

!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == s.length() - 1

In this one line, we deal with skipping white spaces as well as reading contiguous digits when there's white space, and calculate out when the last operation.