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

Initialize a stack to store intermediate results and a variable num to keep track of the current number being processed.
Iterate over the input string s.
If the current character is a digit, update num accordingly.
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.
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.

View Leetcode Problem

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;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.