Evaluate Sums With Brackets
Problem
A spreadsheet cell holds a formula made of non-negative integers, +, -, round brackets and spaces. A - may also be unary, as in "-(2 + 3)" or "1 - (-2)". Return the value of the formula without calling any built-in evaluator. The formula is valid, is at most 300,000 characters long, and every intermediate value fits in a 32-bit signed integer, so the parser must run in linear time.
Examples
Input: s = "1 + 1"
Output: 2Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23Input: s = "-(2 + 3) - (1 - 10)"
Output: 4
Why: a unary minus in front of a bracket flips the sign of its whole valueHints
0 / 3
With only + and -, a formula is a running total where each number is added with a sign of +1 or -1.
A bracket starts a new, smaller running total. When it opens, you need to remember the total so far and the sign that sits in front of the bracket.
Push (total, sign) on each opening bracket and start a fresh total. On the closing bracket, finish the inner total, pop, and fold it back in as previous_total + previous_sign × inner_total.
Solution
Without brackets the formula is a running total: digits build the current number, and each + or - adds that number with the pending sign and sets the sign for the next one. A bracket is a sub-formula with its own running total, and the only context it needs from outside is the total so far and the sign written in front of it. So an opening bracket pushes that pair and resets, and a closing bracket finishes the inner total, pops the pair and folds the inner value back in with its sign. A unary minus needs no special case, because it simply sets the pending sign before a number or a bracket while the total is still unchanged. Each character is handled once, so time is O(n), and the stack holds at most one entry per open bracket, so space is O(depth).
def evaluate(s):
total, num, sign, stack = 0, 0, 1, []
for ch in s:
if ch.isdigit():
num = num * 10 + int(ch)
elif ch in "+-":
total += sign * num
num, sign = 0, (1 if ch == "+" else -1)
elif ch == "(":
stack.append((total, sign)) # context outside the bracket
total, sign = 0, 1
elif ch == ")":
total += sign * num
num = 0
outer_total, outer_sign = stack.pop()
total = outer_total + outer_sign * total
return total + sign * num
print(evaluate("1 + 1")) # -> 2
print(evaluate("(1+(4+5+2)-3)+(6+8)")) # -> 23
print(evaluate("-(2 + 3) - (1 - 10)")) # -> 4
print(evaluate(" 2-1 + 2 ")) # -> 3Stuck on the idea rather than the code? Valid Parentheses covers it.