Basic Calculator hard

Problem Statement

Evaluate a string s representing an expression, where the expression consists of non-negative integers and the operators +, -, (, and ).

Constraints:

• 1 <= s.length <= 3 * 10^5
• s consists of digits, '+', '-', '(', ')', and ' '.
• s is a valid expression.

Example 1

Input: s = "1 + 1" Output: 2

Example 2

Input: s = "2-1 + 2" Output: 3

Steps to Solve

This problem requires careful handling of operator precedence and parentheses. We can use a stack-based approach to achieve this efficiently.

1. Initialization: Create two stacks: nums to store numbers and ops to store operators. We'll use ops to track the current operation, allowing us to handle precedence correctly.

2. Iteration: Iterate through the input string s.

   • Digits: If a digit is encountered, build up a number until a non-digit character is found. Push the formed number onto the nums stack.
   • Operators: If an operator (+, -, or ) is encountered:
     • Parentheses Handling: If it's a closing parenthesis ): Evaluate expressions within parentheses by repeatedly popping from nums and ops until an opening parenthesis ( is encountered. Then discard the opening parenthesis.
     • Operator Precedence: If it's a + or -, process all pending operations with the same or higher precedence (i.e., also + and -). This involves popping numbers and operators from the stacks and performing the calculations. After processing pending operations, push the current operator onto the ops stack.
   • Opening Parenthesis (: Push the opening parenthesis onto the ops stack.

3. Final Calculation: After iterating through the string, process any remaining operations in the stacks to get the final result.

Explanation

The stack approach mimics the order of operations. The ops stack manages the pending operations, ensuring that higher-precedence operations (within parentheses) are handled before lower-precedence ones. By processing pending operations before adding a new operator, we maintain the correct order.

Code (Python)

def calculate(s: str) -> int:
    nums = []
    ops = []
    num = 0
    sign = 1  # 1 for +, -1 for -

    for char in s:
        if char.isdigit():
            num = num * 10 + int(char)
        elif char in ['+', '-']:
            nums.append(num * sign)
            num = 0
            sign = 1 if char == '+' else -1
            ops.append(char)
        elif char == '(':
            nums.append(num * sign)
            num = 0
            sign = 1
            ops.append('(')
        elif char == ')':
            while ops and ops[-1] != '(':
                op = ops.pop()
                n2 = nums.pop()
                n1 = nums.pop()
                nums.append(n1 + n2 if op == '+' else n1 - n2)
            ops.pop() # remove '('

    nums.append(num * sign) #handle the last number

    while ops:
      op = ops.pop()
      n2 = nums.pop()
      n1 = nums.pop()
      nums.append(n1 + n2 if op == '+' else n1 - n2)
    
    return nums[0]

Complexity

• Time Complexity: O(n), where n is the length of the input string. We iterate through the string once. Stack operations are O(1) on average.
• Space Complexity: O(n) in the worst case, as the stacks could potentially store all the numbers and operators in the input string. The space usage is proportional to the nesting depth of parentheses and the length of the expression.