Convert between infix, prefix (Polish), and postfix (Reverse Polish) notation. Evaluate RPN expressions with step-by-step stack traces.
Polish notation (prefix notation), invented by Jan Łukasiewicz in 1924, writes operators before their operands: + 3 4 instead of 3 + 4. Reverse Polish notation (RPN, or postfix) puts operators after: 3 4 +. Both eliminate the need for parentheses and operator-precedence rules, making them ideal for stack-based computation.
This tool converts between standard infix notation and both Polish/Reverse Polish forms using Dijkstra's shunting-yard algorithm. It also evaluates any RPN expression and shows the full stack trace so you can follow each push and pop. Whether you are learning about expression parsing in a data structures course, debugging a Forth program, or simply curious about how HP calculators work, this converter makes the process transparent.
All five arithmetic operators are supported (+, −, ×, ÷, ^) with correct precedence and associativity. The step-by-step tables show the operator stack and output queue at every stage of the conversion, and the evaluation trace shows the numeric stack at every computation step.
Expression parsing is a fundamental topic in computer science — it appears in compilers, interpreters, calculators, and spreadsheet engines. Understanding how infix expressions are converted to postfix and evaluated on a stack is essential knowledge for any programmer.
This tool makes the abstract algorithm concrete. By watching the stack and output queues change step by step, concepts like operator precedence, associativity, and stack-based evaluation become intuitive rather than memorized.
Shunting-Yard Algorithm: scan tokens left-to-right; push numbers to output; push operators to stack (popping higher-precedence operators to output first); push "(" to stack; on ")" pop to output until "(". Evaluate RPN: push numbers to stack; on operator, pop two operands, compute, push result.
Result: Postfix: 3 4 2 * +, Result: 11
The * has higher precedence than +, so 4 2 * is evaluated first (= 8), then 3 + 8 = 11.
Polish notation was invented by the Polish logician Jan Łukasiewicz in 1924 as a way to write logical formulas without parentheses. Charles Hamblin and others later developed Reverse Polish Notation in the 1950s for computer science applications. Burroughs Corporation built the first stack-based computer (B5000, 1961) using RPN internally, and Hewlett-Packard popularized RPN calculators starting with the HP-35 in 1972.
Edsger Dijkstra described this algorithm in 1961. It converts infix notation to postfix in O(n) time using a single operator stack. The name comes from the analogy with a railroad shunting yard, where cars are sorted from one track to another. The algorithm processes tokens left-to-right: numbers go directly to output; operators are pushed to the stack after popping all higher-or-equal-precedence operators; left parentheses are pushed; right parentheses pop the stack to output until a matching left parenthesis is found.
Evaluating a postfix expression is beautifully simple: scan left to right; push numbers onto a stack; when an operator is encountered, pop two values, apply the operator, and push the result. The final value on the stack is the answer. This simplicity is why postfix notation is used in virtual machines (Java bytecode, Python bytecode), printer languages (PostScript), and embedded systems.
RPN (postfix) places operators after their operands: 3 4 + means 3 + 4. It requires no parentheses and is easy to evaluate with a stack.
RPN maps directly to stack-based hardware. It's faster for chained calculations and avoids the '=' key — each operator immediately computes.
Dijkstra's algorithm converts infix to postfix using an operator stack. It handles precedence, associativity, and parentheses in a single left-to-right pass.
Exponentiation (^) is right-associative: 2^3^2 = 2^(3^2) = 512, not (2^3)^2 = 64. The algorithm only pops operators of strictly higher precedence for right-associative ops.
This calculator supports the five basic arithmetic operators. Function support would extend the shunting-yard algorithm with a function stack.
In stack-based languages (Forth, PostScript), some calculators (HP), compiler intermediate representations, and mathematical logic. Use this as a practical reminder before finalizing the result.