Why it works
- In this notation an operator always comes right after its two operands are complete, so they are the two newest numbers: the top two of the stack.
- The result goes back as one number, which is exactly what the next operator may need as an operand, so the expression folds up from the inside out.
- The top was written last, so it is the right operand: for − and ÷ the first pop goes on the right. Truncating towards zero keeps −5.6 as −5.
Complexity
Time O(n): each token is read once, and a push or a pop is O(1). Memory O(n): when the numbers come first, most of them wait on the stack.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗