Basic Calculator

Explanation & Solution

Description

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Input: s = "1 + 1"

Output: 2

Constraints

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

Approach

Stacks pattern

1. Track Running Result and Sign

Maintain result for the current running total and sign for the current sign (+1 or -1)
Build multi-digit numbers as you scan characters

2. Handle Digits

Build the number digit by digit: num = num * 10 + digit

3. Handle + and -

Add sign * num to the result, then reset num = 0
Set the new sign based on the operator

4. Handle Opening Parenthesis `(`

Push the current result and sign onto the stack
Reset result = 0 and sign = 1 to start evaluating the sub-expression

5. Handle Closing Parenthesis `)`

Finalize the current sub-expression: result += sign * num
Pop the saved sign and result from the stack
Combine: result = prevResult + prevSign * result

6. Final Step

After the loop, add any remaining sign * num to the result

Key Insight

The stack saves context (result + sign) when entering parentheses and restores it when leaving
This avoids recursion while correctly handling nested expressions
Time: O(n), Space: O(n)

Visualization

Input:

[1, , +, , 1]

—

Press ▶ or use ← → to step through

Left (L)Right (R)ConvergedDone

2 steps

Solution Code

Simplify Path

Basic Calculator II