Postfix to infix conversion

Build expressions with a stack

Read postfix tokens left to right. Push each operand string. On an operator, pop the right operand first and the left operand second, form ( + left + operator + right + ), and push the result. After all tokens, exactly one stack entry must remain for a valid expression. Parentheses make precedence explicit and avoid needing a separate precedence table.

The invariant is that each stack item is the complete infix expression for one already-parsed postfix subexpression. Each token is processed once, so structural time is O(t) for t tokens; output construction can be larger because the resulting string itself may be large. Space is O(t) in the worst case. Test a single operand, nested operators, subtraction and division to verify operand order, multi-character tokens if tokenization allows them, and invalid input with too few operands. Do not pop left then right, which silently reverses subtraction and division.