Basic Calculator

Hard· stack· expression evaluation

Problem

Evaluate a string expression containing non-negative integers, +, -, parentheses and spaces. The minus sign may also be used as a unary negation. You may not use a built-in eval.

Examples

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

Output: 23

Input: s = "-(3-(2+1))+7"

Output: 7

The parenthesised part is 0, so the result is 7.

Constraints

• 1 <= s.length <= 3 * 10^5
• The expression is valid
• Every intermediate value fits in 32 bits

Hints & approach

Hint 1

Without parentheses, keep a running result and the sign of the next number.

Hint 2

A "(" starts a fresh sub-expression; remember the outer result and sign first.

Hint 3

On ")", fold the inner result back in: outer + sign * inner.

Approachtry the hints first

Track result, the current number being parsed, and sign (+1 or -1). When a number ends, add sign * number to result. On "+" or "-", set sign accordingly. On "(", push result and sign onto a stack, then reset result = 0 and sign = 1. On ")", finish the pending number, then pop the saved sign and outer result and set result = outer + savedSign * result. Unary minus works naturally because it just flips the sign before a number or a parenthesis.

Time O(n) · Space O(n)

← PreviousAsteroid Collision DoneBack to Stacks & queues