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 III

Number: 785

Difficulty: Hard

Paid? Yes

Companies: TikTok, Google, DoorDash, Meta, Verkada, Microsoft, Amazon, Snap, Jingchi, Pocket Gems, Hulu, Houzz

Problem Description

Implement a basic calculator to evaluate a simple expression string. The expression contains only non-negative integers, the operators '+', '-', '*', '/', and parentheses '(' and ')'. The expression is always valid, and integer division should truncate toward zero.

Key Insights

  • Use recursion to handle nested expressions defined by parentheses.
  • A stack can be used to correctly evaluate the expression and respect operator precedence.
  • Multiplication and division have higher precedence than addition and subtraction.
  • When encountering an open parenthesis, recursively compute its value until a closing parenthesis is found.
  • Use immediate calculation for multiplication and division by updating the top of the stack before moving to the next operator.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the string, as every character is processed. Space Complexity: O(n) due to the recursion stack or auxiliary stack used for intermediate results.

Solution

We use a recursive approach combined with a stack to solve the problem. As we iterate through the string:

  • Convert digits into numbers.
  • When encountering an operator or parenthesis, process the previously accumulated number based on the preceding operator.
  • For multiplication or division, pop the last number from the stack, apply the operation, and push the result back.
  • When a '(' is encountered, recursively evaluate the substring until the corresponding ')'.
  • After processing all tokens, sum the values in the stack to get the final result. This method correctly handles both operator precedence and nested expressions.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with line-by-line comments.

def calculate(s: str) -> int:
    # Recursive helper function that processes the expression starting from index 'i'
    def helper(i):
        stack = []
        num = 0
        sign = '+'
        while i < len(s):
            char = s[i]
            # Build the current number if the character is a digit
            if char.isdigit():
                num = num * 10 + int(char)
            # If '(' is encountered, evaluate the subexpression recursively
            if char == '(':
                num, i = helper(i + 1)
            # When encountering an operator or closing parenthesis, process the sign and number
            if (not char.isdigit() and char != ' ') or i == len(s) - 1:
                if sign == '+':
                    stack.append(num)
                elif sign == '-':
                    stack.append(-num)
                elif sign == '*':
                    prev = stack.pop()
                    stack.append(prev * num)
                elif sign == '/':
                    prev = stack.pop()
                    stack.append(int(prev / num))  # Truncate toward zero
                sign = char
                num = 0
            # If a closing parenthesis is reached, end this level of recursion
            if char == ')':
                return sum(stack), i
            i += 1
        return sum(stack), i

    result, _ = helper(0)
    return result

# Example test
print(calculate("2*(5+5*2)/3+(6/2+8)"))
← Back to All Questions