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

Difficulty: Hard

Problem Description

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation. You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Key Insights

  • The expression can include digits, '+' and '-' operators, and parentheses.
  • The challenge involves correctly handling operator precedence and parentheses.
  • A stack data structure is beneficial to manage nested expressions and maintain the current result during evaluation.
  • Space must be managed efficiently to handle the maximum length of the input string, which can be up to 300,000 characters.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. Each character is processed once. Space Complexity: O(n), in the worst-case scenario where all characters are stored in the stack (e.g., for deeply nested parentheses).

Solution

To solve this problem, we can use a stack to keep track of numbers and operations. We will iterate through the string while managing the current number, handling operators, and using the stack to evaluate expressions inside parentheses. The algorithm involves:

  1. Initializing a stack to keep track of the results and the current operator.
  2. Iterating through each character in the string:
    • If it's a digit, build the complete number.
    • If it's an operator ('+' or '-'), process the current number based on the last operator.
    • If it's a '(', push the current result and operator onto the stack and reset for a new sub-expression.
    • If it's a ')', pop from the stack and combine the results.
  3. At the end of the iteration, return the final result accumulated from the stack.

Code Solutions

def calculate(s: str) -> int:
    stack = []
    current_number = 0
    current_result = 0
    sign = 1  # 1 means positive, -1 means negative

    for char in s:
        if char.isdigit():
            current_number = current_number * 10 + int(char)
        elif char in '+-':
            current_result += sign * current_number
            current_number = 0
            sign = 1 if char == '+' else -1
        elif char == '(':
            stack.append(current_result)
            stack.append(sign)
            current_result = 0
            sign = 1
        elif char == ')':
            current_result += sign * current_number
            current_number = 0
            current_result *= stack.pop()  # This will be the sign before '('
            current_result += stack.pop()  # This will be the result before '('

    return current_result + sign * current_number
← Back to All Questions