Basic Calculator II

Given a string s which represents an expression, evaluate this expression and return its value. 

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2<sup>31</sup>, 2<sup>31</sup> - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

Input: s = "3+2*2" Output: 7

Example 2:

Input: s = " 3/2 " Output: 1

Example 3:

Input: s = " 3+5 / 2 " Output: 5

Constraints:

1. 1 <= s.length <= 3 * 10^5
2. s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
3. s represents a valid expression.
4. All the integers in the expression are non-negative integers in the range [0, 2^31 - 1].
5. The answer is guaranteed to fit in a 32-bit integer.

def calculate(s: str) -> int:
    """Evaluates a string expression containing integers and operators (+, -, *, /).

    The integer division truncates toward zero.
    """
    stack = []
    current_number = 0
    operation = '+'
    s += '+0'  # Append a dummy operator to process the last number

    for char in s:
        if char.isdigit():
            current_number = (current_number * 10) + int(char)
        elif char in '+-*/' or char == ' ':
            if char == ' ':
                continue
            if operation == '+':
                stack.append(current_number)
            elif operation == '-':
                stack.append(-current_number)
            elif operation == '*':
                stack.append(stack.pop() * current_number)
            elif operation == '/':
                top = stack.pop()
                if top < 0 and top % current_number != 0:
                    stack.append(top // current_number + 1)
                else:
                    stack.append(top // current_number)
            operation = char
            current_number = 0

    return sum(stack)

# Example Usage:
# s = "3+2*2"
# print(calculate(s))  # Output: 7

# s = " 3/2 "
# print(calculate(s))  # Output: 1

# s = " 3+5 / 2 "
# print(calculate(s))  # Output: 5

Explanation:

1. Initialization:

   • stack: A list to store numbers. This stack will keep track of numbers to be added or subtracted.
   • current_number: An integer to construct the current number being parsed from the string.
   • operation: A character to store the last seen operator (+, -, *, /). Initialized to '+' so the first number is directly pushed to the stack.
   • s += '+0': Appends a dummy operator and a zero to the end of the string. This ensures that the last number in the string is processed correctly.

2. Iteration:

   • The code iterates through each character in the string s.
   • Digit Handling:
     • If the character is a digit, the current_number is updated. For example, if the current number is 1 and the character is '2', the current_number becomes 12.
   • Operator Handling:
     • If the character is an operator (+, -, *, /) or a space:
       • Spaces are ignored.
       • If the character is an operator, the previous operation is applied based on the operation variable.
       • '+': Push current_number to the stack.
       • '-': Push the negation of current_number to the stack.
       • '*': Pop the top element from the stack, multiply it by current_number, and push the result back onto the stack.
       • '/': Pop the top element from the stack, divide it by current_number (integer division), and push the result back onto the stack. The integer division truncates towards zero.
       • Update the operation variable to the current operator.
       • Reset current_number to 0.

3. Final Result:

   • After processing the entire string, the stack contains the numbers that need to be summed up. The sum() function calculates the sum of all elements in the stack, which is the final result.

Naive Solution

A naive solution would be to use eval(). However, this is not allowed based on the prompt.

def calculate_naive(s: str) -> int:
    return eval(s)

Big(O) Runtime Analysis

The time complexity is O(n), where n is the length of the string s. This is because the code iterates through the string once.

Big(O) Space Usage Analysis

The space complexity is O(n) in the worst case, where n is the length of the string s. This is because the stack can contain at most n/2 elements if the string contains alternating numbers and operators.

Edge Cases

1. Leading/Trailing Spaces: The code handles leading and trailing spaces correctly because it skips spaces during iteration.
2. Consecutive Operators: The problem statement mentions that the expression is always valid, so consecutive operators are not expected.
3. Division by Zero: The problem statement doesn't explicitly disallow division by zero. However, the integer division will simply result in an error, which should be handled in a production environment with error handling.
4. Large Numbers: The problem statement specifies that all integers are in the range [0, 2^31 - 1] and the result is guaranteed to fit in a 32-bit integer. This eliminates potential overflow issues.