Basic Calculator

Given a string expression containing non-negative integers, '+', '-', parentheses, and spaces, evaluate it.

You may assume the expression is valid and fits in a 32-bit signed integer.

Why this is worth learning

Parentheses suspend an outer accumulator and its pending sign. When the inner expression finishes, it becomes one signed operand of that suspended context.

Before coding: one-minute experiment

What is the value of "1-(2-(3+4))", and which sign applies to the whole inner expression?

Function signature

func Calculate(s string) int

Inputs / outputs

• s: expression string.
• Return: evaluated result.

Example

s = "1 + (2 - 3) + 4"
Output: 4

Constraints

• 0 <= len(s) <= 100_000; empty input returns 0.
• Nonempty expressions use valid syntax with binary +/-, parentheses, spaces, and unary minus only at an expression or parenthesized-expression start.
• Every decimal literal and signed intermediate accumulator value fits the course's 64-bit int; the final result fits a signed 32-bit integer. A small final result alone would not bound intermediate arithmetic.

Core idea (near-solution)

Use a running result and sign, and a stack to handle parentheses.

When you see '(', push the current result and sign onto the stack, then reset them for the sub-expression. When you see ')', pop and combine.

Invariant: result and sign represent the value of the expression since the last '('.

Algorithm (step-by-step)

1. Initialize result = 0, sign = 1, num = 0.
2. For each character:
   • If digit: build num.
   • If '+' or '-': add sign * num to result, set sign, reset num.
   • If '(' : push result and sign; reset result=0, sign=1.
   • If ')' : commit sign * num and reset num = 0; pop the saved outer sign and prevResult, then set result = prevResult + outerSign*result.
3. After the loop, add sign * num to result, then return result. Resetting num after each commit prevents a parenthesized expression's final number from being counted twice.

Correctness sketch

Within one nesting level, result is the sum of committed signed operands, num is the decimal value currently being read, and sign applies to that pending operand. A plus or minus commits num and sets the next sign. Opening a parenthesis saves the outer result and sign, then starts an independent inner accumulator. Closing it commits the last inner number and restores outerResult+outerSign*innerResult, exactly substituting the parenthesized value into its context. Spaces do not change state, and the final commit includes the last number. Induction over tokens and nested subexpressions gives the value of a valid expression in the supported grammar.

Trace (hand walkthrough)

s = "1 + (2 - 3) + 4"
- read '1': num=1; '+' commits it, result=1, num=0, sign=+1
- '(' saves (outerResult=1, outerSign=+1), resets result=0, sign=+1
- read '2': num=2; '-' commits it, result=2, num=0, sign=-1
- read '3': num=3; ')' commits -3, so inner result=-1 and num=0
- restore outer scope: result=1 + 1*(-1)=0
- '+' commits the pending zero, then sign=+1
- read '4': num=4; end of input commits +4; return 4

Pitfalls to avoid

• Forgetting to apply the last number at the end.
• Mishandling unary minus (handled naturally by sign tracking).

Debugging lens

Test multi-digit operands, nested subtraction, and unary minus at expression or parenthesis starts. Preserve the valid-expression grammar; this is not a general parser for multiplication, division, or arbitrary chains of unary operators.

Complexity

• Time: O(n)
• Extra space: O(n)

Implementation notes (Go)

• Parse multi-digit numbers and skip spaces.
• Use a stack to store (result, sign) when entering parentheses.

Contract precision

The supplied evaluator supports +, -, parentheses, spaces, and unary minus at the start of an expression or parenthesized expression. It assumes valid syntax and does not report parse errors. Empty input retains the legacy result zero.

Reconstruction checkpoint

What is the value of "1-(2-(3+4))", and which sign applies to the whole inner expression?

Return to Stack + Monotonic · Module quiz