LeetCode 227: Basic Calculator II

Explanation

To solve this problem, we can use a stack to keep track of intermediate results while processing the expression from left to right. We iterate over the input string, and for each character, we either push the number onto the stack or perform the operation with the top element(s) on the stack based on the operator. We need to handle multiplication, division, addition, and subtraction with the correct precedence.

Algorithm

1. Initialize a stack to store intermediate results and a variable num to keep track of the current number being processed.
2. Iterate over the input string s.
3. If the current character is a digit, update num accordingly.
4. If the current character is an operator or we have reached the end of the string, perform the corresponding operation with the top element(s) on the stack based on the operator.
5. Finally, sum up all elements in the stack to get the final result.

Time Complexity

The time complexity of this algorithm is O(n), where n is the length of the input string s.

Space Complexity

The space complexity is also O(n) due to the stack used to store the intermediate results.

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 ((!Character.isDigit(c) && c != ' ') || i == s.length() - 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;
            }
        }
        
        int result = 0;
        while (!stack.isEmpty()) {
            result += stack.pop();
        }
        
        return result;
    }
}