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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Basic Calculator II

Number: 227

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Tesla, Microsoft, DoorDash, TikTok, Apple, Verkada, IXL, Walmart Labs, Zoho, Coupang, The Trade Desk, Bloomberg, Google, Adobe, Snap, Oracle, ByteDance, DE Shaw, Accenture, Anduril, Airbnb

Problem Description

Given a valid arithmetic expression as a string that includes non-negative integers and the operators '+', '-', '*', and '/'. Evaluate the expression while respecting the operator precedence (multiplication and division have higher precedence than addition and subtraction). The division should truncate toward zero. The expression is guaranteed to be valid, and the answer will fit in a 32-bit integer.

Key Insights

  • The expression can be processed in one pass while using a stack to handle operator precedence.
  • When encountering '+' or '-' operators, the current number is directly added or subtracted (as a positive or negative value).
  • For '*' and '/' operators, compute immediately with the last number from the stack and update it.
  • Handle spaces and multi-digit numbers by building the number while iterating over the string.
  • Division truncation toward zero must be carefully applied, which aligns with typical integer division in most languages.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the expression, since the algorithm processes each character once.
Space Complexity: O(n) in the worst-case scenario when all numbers are stored in the stack.

Solution

We use a stack-based approach. Iterate over each character of the string while maintaining a variable for the current number and a previous operator (initialized to '+'). When an operator or the end of the string is reached, perform an action based on the previous operator:

  • For '+' add the current number to the stack.
  • For '-' add the negative of the current number.
  • For '*' and '/' pop the last number from the stack, compute the result by performing multiplication or division, and then push the result back to the stack. After processing the entire string, sum the elements in the stack to get the final result. This approach ensures that multiplication and division are handled before addition and subtraction.

Code Solutions

# Python solution for Basic Calculator II

def calculate(s: str) -> int:
    # Initialize the stack, current number, and the last seen operator.
    stack = []
    current_number = 0
    previous_operator = '+'
    
    # Loop over each character in the string along with one extra iteration to handle the end.
    for i, char in enumerate(s):
        if char.isdigit():
            # Build the current number by shifting previous digits.
            current_number = current_number * 10 + int(char)
        # If the character is an operator (or we're at the end), process the previous operator.
        if char in "+-*/" or i == len(s) - 1:
            if previous_operator == '+':
                stack.append(current_number)
            elif previous_operator == '-':
                stack.append(-current_number)
            elif previous_operator == '*':
                last_number = stack.pop()
                stack.append(last_number * current_number)
            elif previous_operator == '/':
                last_number = stack.pop()
                # Python division truncates toward negative infinity by default, so we use int() to truncate toward zero.
                stack.append(int(last_number / current_number))
            # Reset for the next number and update the operator.
            previous_operator = char
            current_number = 0
    # Sum up all numbers in the stack which gives the final result.
    return sum(stack)

# Example usage:
print(calculate("3+2*2"))   # Output: 7
print(calculate(" 3/2 "))   # Output: 1
print(calculate(" 3+5 / 2 "))  # Output: 5
← Back to All Questions