Why it works
- With only + and −, the value is a sum of numbers, each with its sign. A number is added once it ends, at the next sign, at ")" or at the end of the string.
- A bracket is a sum of its own, so at "(" the outer result and the sign in front are saved and the inside starts from 0. At ")" the inner sum is multiplied by that sign and added back: the latest "(" is the first to close, so the saved pair is on top.
- A minus at the very start or right after "(" needs no special case: it adds num = 0 and sets the sign to −1.
Complexity
Time O(n): each character is read once. Memory O(n): two numbers on the stack for every bracket open at once, at most n.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗