Some old calculators have no parentheses key. Instead you type the operands first and the operator after them: 3 4 + means 3 + 4, and 3 4 + 2 * means (3 + 4) * 2. An operator always applies to the two values produced just before it, in order, so 8 2 - is 8 - 2.
Write eval_postfix(tokens) that takes such an expression as a list of strings and returns its value as an integer.
- Each token is either an operator
"+","-","*","/"or an integer such as"12"or"-7"(a minus sign followed by digits is a number, a lone"-"is subtraction). /is integer division that truncates toward zero:7 / -2is-3, not-4. (Python's//rounds down, so watch out.)- The expression is always valid: every operator has two values to work on, exactly one value is left at the end, and nothing is divided by zero.
eval_postfix(["3", "4", "+", "2", "*"]) # 14
eval_postfix(["10", "2", "8", "*", "+", "3", "-"]) # 23 (10 + 2 * 8 - 3)
eval_postfix(["20", "6", "-", "4", "/"]) # 3 ((20 - 6) / 4 = 3.5, truncated)
eval_postfix(["7", "-2", "/"]) # -3
eval_postfix(["-9"]) # -9
Constraints: 1 <= len(tokens) <= 2 * 10^5; number tokens are in [-10^4, 10^4]; every intermediate value and the result have absolute value at most 10^15.
Repeatedly searching for the first operator and splicing its result back into the list is O(n²). Aim for O(n).
Show hint
read left to right. When an operator arrives, the two values it needs are always the two most recent results that haven't been used yet.