algoadvance

Leetcode 227. Basic Calculator II

Problem Statement

Given a string s which represents an expression, evaluate this expression and return its value. The integer division should truncate toward zero.

Clarifying Questions

  1. Can the input string contain invalid characters?
    • No, it will only contain integers, the four basic operators (+, -, *, /), and spaces.
  2. Can the input string be empty or contain only spaces?
    • The problem guarantees that the input string is a valid expression, so it cannot be empty or only contain spaces.
  3. How should division handle negative results?
    • The division should truncate toward zero (i.e., 7 / -3 should be -2).
  4. Are there any constraints on the size of the integers?
    • The constraints are not explicitly mentioned, but typical constraints for this problem involve integers fitting within the 32-bit signed integer range.

Strategy

  1. We will iterate through the input string and use a stack to manage the numbers and intermediate results:
    • Use a variable num to build the current number as we iterate.
    • Use a sign variable to keep track of the last seen operation (+ by default).
    • Use a stack to handle the numbers and the intermediate results efficiently.

  2. When we encounter a number, we will continue building it until we encounter an operator or the end of the string.

  3. When we encounter an operator or reach the end of the string:
    • Depending on the sign, we will process the previous number with the current number:
      • +: Push the current number to the stack.
      • -: Push the negated current number to the stack.
      • *: Pop the top of the stack, multiply it by the current number, and push the result back.
      • /: Pop the top of the stack, divide it by the current number, truncate toward zero, and push the result back.
  4. At the end of the iteration, the stack will contain all the numbers to be summed up to get the final result.

Code

import java.util.Stack;

public class BasicCalculatorII {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        int num = 0;
        char sign = '+';
        s = s.replaceAll(" ", ""); // Remove all spaces

        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) || i == s.length() - 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 result = 0;
        for (int number : stack) {
            result += number;
        }

        return result;
    }

    public static void main(String[] args) {
        BasicCalculatorII calc = new BasicCalculatorII();
        System.out.println(calc.calculate("3+2*2")); // Output: 7
        System.out.println(calc.calculate(" 3/2 ")); // Output: 1
        System.out.println(calc.calculate(" 3+5 / 2 ")); // Output: 5
    }
}

Time Complexity

The time complexity of this solution is (O(n)), where (n) is the length of the input string. This is because we process each character in the string exactly once.

The space complexity is also (O(n)) in the worst case because we might store each number in the stack before summing them up.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI