Library

PDT · Pushdown transduction

Polish notation to reverse Polish

Prefix to postfix: +x*xx becomes xxx*+. Each operator waits on the stack, remembering how many of its operands are complete; an x completes one, and an operator whose second operand completes is printed and itself counts as an operand for the one below. Łukasiewicz’s notation, turned round.

readoneend
The machine as drawn — 3 states, 8 transitions.

The author’s examples, run

x → accept · x+xx → accept · xx++x*xx → accept · xxx*+*+xxx → accept · xx+x*+*xx*xx → accept · xx*xx*++x → rejectxx → reject