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.

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

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 ')' : add sign * num to result, pop sign and prevResult, and set result = prevResult + sign*result.
3. After the loop, add any remaining num.

Correctness sketch

• Invariant: result and sign represent the value of the expression since the last '('.
• The stack always holds the correct values of processed subexpressions.
• Applying an operator to the top values yields the correct combined value.
• The final stack top equals the expression value.

Trace (hand walkthrough)

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

Walk:
- read 1 -> result=1
- "(": push (result=1, sign=1), reset result=0
- read 2 -> result=2; "-" sign=-1; read 3 -> result=-1
- ")": result = 1 + 1*(-1) = 0
- read 4 -> result=4

Pitfalls to avoid

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

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.