#224

Hard

auto_awesomeStack-based state management

LeetCode Problem Workspace

Basic Calculator

Implement a basic calculator to evaluate mathematical expressions, ensuring correct evaluation with stack-based management of operators and operands.

math string stack recursion

Problem Statement

You are given a string s representing a valid mathematical expression. Your task is to implement a basic calculator that evaluates the expression and returns the result. The string contains digits, operators ('+', '-', '(', ')'), and spaces. You are not allowed to use any built-in function that directly evaluates a string as a mathematical expression, such as eval().

The input expression is guaranteed to be valid, and no two consecutive operators will appear. The expression can contain parentheses and must account for operator precedence. Your solution should handle unary and binary operations while considering precedence and the handling of nested expressions.

Examples

Example 1

Input: s = "1 + 1"

Output: 2

Example details omitted.

Example 2

Input: s = " 2-1 + 2 "

Output: 3

Example details omitted.

Example 3

Input: s = "(1+(4+5+2)-3)+(6+8)"

Output: 23

Example details omitted.

Constraints

1 <= s.length <= 3 * 105
s consists of digits, '+', '-', '(', ')', and ' '.
s represents a valid expression.
'+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
'-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
There will be no two consecutive operators in the input.
Every number and running calculation will fit in a signed 32-bit integer.

Solution Approach

Stack-Based State Management

Use a stack to manage the operands and operators. Traverse the expression from left to right, handling each character based on whether it is a number, operator, or parenthesis. When encountering a number, compute the current result based on the most recent operator. Parentheses indicate a new level of operation that should be pushed and popped from the stack as needed.

Handling Unary and Binary Operators

The problem involves both unary and binary operators. When a '+' or '-' is encountered, the current number's sign is determined based on the previous operator. If no sign is found, treat it as positive. The stack will be used to manage these signs and apply them as operations are completed.

Parentheses and Operator Precedence

Parentheses in the expression create nested sub-expressions that should be handled as independent calculations. Use the stack to manage and compute each level of the parentheses separately. Ensure the precedence of operators is respected within the context of the parentheses, effectively managing the evaluation order.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on how the expression is traversed and evaluated. If each character is processed once, the time complexity is O(n), where n is the length of the expression. The space complexity depends on the maximum depth of parentheses and the size of the stack, which is O(n) in the worst case.

What Interviewers Usually Probe

Candidate can implement a stack to maintain operator precedence and operands.
Candidate can handle both unary and binary operators effectively.
Candidate handles parentheses and ensures nested expressions are evaluated correctly.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding how to handle unary minus operators (e.g., '-1' or '-(2+3)').
Not properly managing operator precedence when parentheses are involved.
Failing to correctly manage the stack when multiple levels of parentheses are nested.

Follow-up variants

Modify the solution to handle division and multiplication operators in addition to addition and subtraction.
Implement a more memory-efficient solution where only necessary state is maintained at each step.
Optimize the solution for handling expressions with significantly larger input sizes.

FAQ

How do I handle the parentheses in the Basic Calculator problem?

Use a stack to manage each level of parentheses as a separate sub-expression. When encountering a closing parenthesis, evaluate the sub-expression and combine it with the rest of the expression.

How do I handle the unary minus operator in the Basic Calculator?

A unary minus is handled as a sign for the following number or expression. You should check the preceding character to distinguish between unary and binary minus operations.

What is the time complexity of the Basic Calculator solution?

The time complexity is O(n), where n is the length of the expression, as we process each character exactly once.

Can I use eval() to solve the Basic Calculator problem?

No, you are specifically restricted from using built-in functions like eval() to evaluate the expression. You need to manually implement the evaluation logic.

How do I optimize the Basic Calculator for large inputs?

Focus on optimizing stack usage by processing characters efficiently and minimizing the number of operations required at each step. Consider handling large inputs with constant space or iterative solutions.

terminal

Solution

Solution 1: Stack

We use a stack $stk$ to save the current calculation result and operator, a variable $sign$ to save the current sign, and a variable $ans$ to save the final calculation result.

class Solution:
    def calculate(self, s: str) -> int:
        stk = []
        ans, sign = 0, 1
        i, n = 0, len(s)
        while i < n:
            if s[i].isdigit():
                x = 0
                j = i
                while j < n and s[j].isdigit():
                    x = x * 10 + int(s[j])
                    j += 1
                ans += sign * x
                i = j - 1
            elif s[i] == "+":
                sign = 1
            elif s[i] == "-":
                sign = -1
            elif s[i] == "(":
                stk.append(ans)
                stk.append(sign)
                ans, sign = 0, 1
            elif s[i] == ")":
                ans = stk.pop() * ans + stk.pop()
            i += 1
        return ans

Continue Practicing

#770 basic calculator iv #241 different ways to add parentheses #736 parse lisp expression