268. Evaluation of a Postfix Expression

Given a postfix (Reverse Polish) expression as space-separated tokens - integers (possibly negative) and the operators + - * / - evaluate it and print the result. Division truncates toward zero, like integer division in C/Java.

Input: The input is a single line containing space-separated postfix tokens - integers (possibly negative) and the operators + - * /. Output: Print a single integer - the evaluated result of the postfix expression.

1 <= number of tokens <= 10^5

Postfix notation entirely eliminates the need for operator precedence rules or parentheses - the ORDER tokens appear in already encodes exactly when each operation should happen, which is precisely why it's so easy to evaluate mechanically.

Evaluate an expression written in postfix (Reverse Polish) notation, where operators come AFTER their operands. Brute force: Convert the postfix expression back into infix (with proper parentheses) and evaluate that with a general expression parser - this works but is far more complex than necessary, since postfix is SPECIFICALLY designed to be trivially evaluable with a simple stack. Optimised: Postfix notation is designed so that by the time you encounter an operator, both its operands are ALREADY fully evaluated and sitting on top of the stack - a single left-to-right scan with a simple stack evaluates the whole expression with no need for precedence rules or parentheses handling at all.

Scan the tokens once with a single numeric stack: push every number token, and whenever an operator token is seen, pop the top two values, apply the operator to them in the correct order (second-popped op first-popped, with truncating division), and push the result back. After the single pass, the stack holds exactly the final answer. This needs no tree construction or rescanning - just one linear pass with a stack - making it both simplest and fastest. Time: O(n) Space: O(n)

Walk the tokens once using an auxiliary stack of tree nodes: push a leaf node for each number, and on each operator pop two subtrees, make them the children of a new operator node, and push that node back. After one pass the stack holds a single root representing the whole expression as a binary tree. Then evaluate that tree recursively (post-order: evaluate left, evaluate right, apply the operator). This is a genuinely different representation from a running accumulator - it reconstructs expression structure explicitly - though it costs extra memory to hold the tree. Time: O(n) Space: O(n)

Repeatedly scan the token list from the left looking for the first operator; once found, apply it to the two numeric tokens immediately preceding it, replace those three tokens with the single result, and start scanning again from the beginning. This mirrors how postfix expressions collapse but re-scans the (shrinking) list from scratch after every single operation, and shifting the list after each replacement costs extra work, making it quadratic overall. Time: O(n^2) Space: O(n)

1. Scan the tokens left to right. 2. Push every NUMBER onto a stack. 3. On an OPERATOR, pop the top TWO values (the second-popped is the LEFT operand, the first-popped is the RIGHT operand), apply the operator, and push the result back.

Time: O(n) - one single pass through the tokens. Space: O(n) in the worst case, for the stack (though in practice it rarely holds more than a few values at once).

Negative operand tokens; non-commutative operators (- and /) where popped-operand order matters; division truncating toward zero; up to 10^5 tokens for performance.

Be careful about operand ORDER for non-commutative operators (subtraction, division) - popping b then a means you must compute a - b (or a / b), NOT b - a, a very common off-by-order bug.