We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Basic Calculator II

Difficulty: Medium

Problem Description

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^31, 2^31 - 1].

Key Insights

  • The expression can contain non-negative integers and the operators +, -, *, and /.
  • Spaces in the expression should be ignored.
  • Multiplication and division take precedence over addition and subtraction.
  • We can use a stack to handle the operations according to their precedence.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can iterate through the string while maintaining a stack to keep track of the numbers and intermediate results. We process each character in the string in the following way:

  1. Ignore spaces.
  2. If the character is a digit, we build the complete number.
  3. If the character is an operator (+, -, *, /), we evaluate the previous number with the last operator stored and push the result onto the stack.
  4. After processing all characters, we sum up the values in the stack to get the final result.

The stack is used to manage the numbers and to handle the order of operations correctly.

Code Solutions

def calculate(s: str) -> int:
    stack = []
    current_number = 0
    operation = '+'
    s = s.strip() + '+'  # Add a '+' at the end to flush the last number

    for char in s:
        if char.isdigit():
            current_number = current_number * 10 + int(char)  # Build the current number
        elif char in "+-*/":
            if operation == '+':
                stack.append(current_number)
            elif operation == '-':
                stack.append(-current_number)
            elif operation == '*':
                stack[-1] = stack[-1] * current_number
            elif operation == '/':
                stack[-1] = int(stack[-1] / current_number)  # Truncate towards zero
            
            operation = char  # Update the current operation
            current_number = 0  # Reset the current number

    return sum(stack)  # Sum up all values in the stack
← Back to All Questions