A calculator stores formulas in postfix (reverse Polish) form, where each operator follows its two operands: a+b becomes ab+.
Convert an infix expression to postfix. Operands are single lowercase letters; operators are + - * / ^ with the usual precedence (^ highest, then * /, then + -). + - * / group left to right; ^ groups right to left (a^b^c means a^(b^c)). Brackets may appear.
Constraints
- 1 ≤ length ≤ 1000
- the expression is valid
Input and output
- Input
- One line: the expression, with no spaces.
- Output
- The postfix expression, with no spaces.
Examples
Input 1
a+b*cOutput
abc*+* binds tighter than +, so b and c are multiplied first: abc*+.
Input 2
(a+b)*cOutput
ab+c*Brackets force the addition first: ab+c*.
Show hints
- Operands go straight to the output; operators wait on a stack.
- Before pushing an operator, pop operators of higher precedence (or equal precedence, if the new one is left-associative).
Show the explanation
This is Dijkstra's shunting-yard algorithm. Letters go straight to the output. ( is pushed; ) pops to the output until the matching (. For an operator, first pop every operator on the stack that should be applied earlier: one with higher precedence, or equal precedence when the new operator groups left to right. Then push it. At the end, pop everything left. Treating ^ as right-associative is the classic trap.
Original UniCircle question. Last reviewed 22 Oct 2026.