Basic Calculator II

Problem

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 the evil built-in library function.

Solution

O(n) time using Stack

public class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) return 0;
        String str = s.trim().replaceAll(" +", "");
        int len = str.length();
        Stack<Integer> stack = new Stack<>();
        int num = 0, sign = '+';
        for (int i = 0; i < len; i++) {
            char c = str.charAt(i);
            if (Character.isDigit(c)) num = num * 10 + (c - '0');
            if (!Character.isDigit(c) || i == len - 1) {
                switch (sign) {
                    case '+':
                        stack.push(num);
                        break;
                    case '-':
                        stack.push(-num);
                        break;
                    case '*':
                        stack.push(stack.pop() * num);
                        break;
                    case '/':
                        stack.push(stack.pop() / num);
                        break;
                }
                sign = c;
                num = 0;
            }
        }
        int res = 0;
        for (int i : stack) res += i;
        return res;
    }
}

O(n) time O(1) space no Stack solution

public class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) return 0;
        String str = s.trim().replaceAll(" +", "");
        int len = str.length();
        int res = 0, preVal = 0, num = 0, sign = '+';
        for (int i = 0; i < len; i++) {
            char c = str.charAt(i);
            if (Character.isDigit(c)) num = num * 10 + (c - '0');
            if (!Character.isDigit(c) || i == len - 1) { //Must handle the last index using previous "sign" 
                switch (sign) {
                    case '+':
                        res += preVal;
                        preVal = num;
                        break;
                    case '-':
                        res += preVal;
                        preVal = -num;
                        break;
                    case '*':
                        preVal *= num;
                        break;
                    case '/':
                        preVal /= num;
                        break;
                }
                sign = c;
                num = 0;
            }
        }
        res += preVal;
        return res;
    }
}

Analysis

This problem is tricky if you are not very careful with number and sign
The basic idea to solve this problem is that we have a reference to the number before we meet sign
Then according to the sign we encounter, we do some calculations and update the num, sign or res

First solution uses stack to store the previous number
When the current character is not digit or is the last one, we update the stack corresponding to the sign
Then we update the sign with current character and reset num to 0
At the end, we go through all numbers from stack and simply add them together to get our result

The second solution is using the similar idea but having a var preVal as role of stack
We only update the res if sign is + or -, when it's * or / we just update preVal
At the end, we also need to update the res with preVal

Notice that, we call s.trim() to remove the leading and trailing space
Then we use replaceAll(" +", "") to remove the space in the middle spaces Actually we can just simply use replaceAll() but I want you to get familiar with trim() method ;)