Polish Notation Converter (Prefix, Infix, Postfix)
Convert an expression between prefix (Polish), infix, and postfix (Reverse Polish) notation with the parsing steps shown.
Reviewed for accuracy by Manoj Kumar, Mathematics Educator
Polish Notation Converter (Prefix, Infix, Postfix)
Calculator
Adjust values & calculateEnter your values below. Every result is computed in your browser — no data is sent to any server.
Formula: Shunting Yard: scan tokens, use operator stack and output queue with precedence rules
Worked example — Prefix: - * + 3 4 2 5 | Postfix: 3 4 + 2 * 5 - | Result: 9
Formula
Shunting Yard: scan tokens, use operator stack and output queue with precedence rules
The Shunting Yard algorithm processes infix tokens left to right. Numbers go to output. Operators are pushed to a stack after popping higher-precedence operators to output. Parentheses control grouping. The result is a postfix expression that can be evaluated with a simple stack.
Worked Examples
Example 1: Converting (3 + 4) * 2 - 5
Problem:Convert the infix expression (3 + 4) * 2 - 5 to both prefix (Polish) and postfix (Reverse Polish) notation.
Solution:Infix: ( 3 + 4 ) * 2 - 5 Shunting Yard steps for postfix: 1. Push 3 to output 2. Push ( to stack 3. Push 3, then +, then 4 4. ) encountered: pop + to output 5. * pushed to stack 6. Push 2 to output 7. - has lower precedence: pop * to output, push - 8. Push 5 to output 9. Pop remaining: - Postfix (RPN): 3 4 + 2 * 5 - Prefix (PN): - * + 3 4 2 5 Evaluation: 3+4=7, 7*2=14, 14-5=9
Result:Prefix: - * + 3 4 2 5 | Postfix: 3 4 + 2 * 5 - | Result: 9
Example 2: Converting 2 ^ 3 ^ 2 (Right Associative)
Problem:Convert 2 ^ 3 ^ 2 noting that exponentiation is right-associative.
Solution:Infix: 2 ^ 3 ^ 2 Right-associative means: 2 ^ (3 ^ 2) = 2 ^ 9 = 512 Not: (2 ^ 3) ^ 2 = 8 ^ 2 = 64 Postfix: 2 3 2 ^ ^ Prefix: ^ 2 ^ 3 2 Evaluation: 3^2=9, 2^9=512
Result:Prefix: ^ 2 ^ 3 2 | Postfix: 2 3 2 ^ ^ | Result: 512
Frequently Asked Questions
What is Polish notation and why was it invented?
Polish notation, also called prefix notation, was invented by the Polish logician Jan Lukasiewicz in 1924 to simplify propositional logic expressions. In this notation, operators are placed before their operands rather than between them. For example, the infix expression 3 + 4 becomes + 3 4 in prefix notation. The key advantage is that Polish notation completely eliminates the need for parentheses and operator precedence rules because the order of operations is unambiguous from the expression structure itself. This makes expressions easier to parse programmatically and reduces potential ambiguity in mathematical and logical statements. Polish notation laid the groundwork for computer science expression evaluation and is still used in certain programming contexts today.
What is Reverse Polish Notation (postfix) and where is it used?
Reverse Polish Notation, commonly abbreviated RPN, places operators after their operands. The expression 3 + 4 becomes 3 4 + in RPN. This notation became famous through Hewlett-Packard calculators starting in the 1960s, where users would enter operands first, then press the operator key. RPN is particularly efficient for stack-based evaluation because you simply push operands onto a stack and apply operators to the top elements. Many programming languages and virtual machines use postfix notation internally. The Java Virtual Machine, for instance, uses a stack-based architecture that essentially processes bytecode in postfix order. RPN is also used in the PostScript page description language and in many embedded systems where memory efficiency is critical.
How does the Shunting Yard algorithm convert infix to postfix?
The Shunting Yard algorithm, invented by Edsger Dijkstra in 1961, converts infix expressions to postfix notation using two data structures: an output queue and an operator stack. When reading tokens left to right, numbers go directly to the output queue. When an operator is encountered, operators on the stack with higher or equal precedence (respecting associativity) are popped to the output queue before the new operator is pushed onto the stack. Left parentheses are pushed onto the stack, and when a right parenthesis appears, operators are popped to the output until the matching left parenthesis is found. After all tokens are processed, remaining operators on the stack are popped to the output. The algorithm runs in linear time relative to the number of tokens, making it highly efficient for expression parsing.
What role does operator precedence play in expression conversion?
Operator precedence determines the order in which operations are performed when an expression contains multiple operators without explicit parentheses. In standard mathematical convention, exponentiation has the highest precedence, followed by multiplication and division, then addition and subtraction. When converting between notations, precedence rules dictate when operators should be output or held on the stack. For example, in the expression 2 + 3 * 4, multiplication must happen before addition, so the postfix form is 2 3 4 * + rather than 2 3 + 4 *. Without proper precedence handling, conversions would produce mathematically incorrect results. Associativity also matters: most operators are left-associative, meaning 8 - 3 - 2 evaluates as (8 - 3) - 2, while exponentiation is right-associative, so 2 ^ 3 ^ 2 equals 2 ^ (3 ^ 2).
How do you evaluate a postfix (RPN) expression step by step?
Evaluating a postfix expression uses a simple stack-based algorithm. Read tokens from left to right. If the token is a number, push it onto the stack. If the token is an operator, pop the top two values from the stack, apply the operator with the first popped value as the right operand and the second as the left operand, then push the result back onto the stack. After processing all tokens, the single remaining value on the stack is the final result. For example, evaluating 3 4 + 2 * works as follows: push 3, push 4, see + so pop 4 and 3 and push 7, push 2, see * so pop 2 and 7 and push 14. The final answer is 14. This algorithm is elegant because it requires no parentheses and no precedence checking during evaluation.
What is the difference between prefix, infix, and postfix notation?
The three notations differ in where the operator is placed relative to its operands. Infix notation places the operator between operands (3 + 4), which is the standard mathematical notation humans learn in school. Prefix notation places the operator before the operands (+ 3 4), and postfix places it after (3 4 +). Infix notation requires parentheses and precedence rules to resolve ambiguity, while prefix and postfix are inherently unambiguous. Consider the expression (3 + 4) * 2 versus 3 + 4 * 2 in infix notation: the parentheses change the meaning. In prefix, these become * + 3 4 2 versus + 3 * 4 2 respectively, with no parentheses needed. Each notation has practical applications, with infix being most readable for humans, while prefix and postfix are more efficient for machine processing.
How are expression trees related to these notations?
An expression tree is a binary tree where leaf nodes contain operands and internal nodes contain operators. The three notations correspond directly to different tree traversal orders. Infix notation comes from an in-order traversal (left child, node, right child). Prefix notation comes from a pre-order traversal (node, left child, right child). Postfix notation comes from a post-order traversal (left child, right child, node). For the expression (3 + 4) * 2, the tree has * at the root, + as the left child with 3 and 4 as its children, and 2 as the right child. Pre-order gives * + 3 4 2, post-order gives 3 4 + 2 *, and in-order gives 3 + 4 * 2 (requiring parentheses for correctness). Expression trees are fundamental data structures in compilers and interpreters.
What programming languages use prefix or postfix notation natively?
Several programming languages use non-infix notation as their primary syntax. Lisp and its dialects (Scheme, Clojure, Racket) use prefix notation extensively, where every expression is written as (operator operand1 operand2). For example, (+ 3 (* 4 5)) adds 3 to the product of 4 and 5. Forth is the most well-known postfix language, where you write 3 4 + 2 * to compute (3 + 4) * 2. The PostScript page description language, used in printing and PDF generation, also uses postfix notation. Factor is a modern concatenative language built on postfix principles. Assembly languages often use a form of postfix notation in their instructions. HP calculators and financial calculators traditionally used RPN, and many engineers and scientists still prefer RPN calculators for their efficiency in chain calculations.
Can Polish notation handle functions with more than two arguments?
Yes, Polish notation naturally extends to functions with any number of arguments, which is one of its strengths over infix notation. In prefix form, a function with three arguments simply lists the function name followed by all three operands, such as max 3 7 5 for finding the maximum of three numbers. Lisp-family languages demonstrate this beautifully with expressions like (+ 1 2 3 4 5) to sum five numbers. For postfix notation, handling variable-argument functions requires either knowing the function arity in advance or using a delimiter. Some stack-based languages use special markers to indicate argument boundaries. This extensibility makes Polish notations particularly powerful for mathematical logic, where predicates can have arbitrary numbers of arguments, and for functional programming, where function composition and higher-order functions are common patterns.
What are the practical advantages of RPN calculators over algebraic calculators?
RPN calculators offer several practical advantages over standard algebraic entry calculators. First, complex calculations require fewer keystrokes because intermediate results are automatically stored on the stack, eliminating the need for parentheses keys and memory registers. For the calculation (3 + 4) * (5 + 6), an algebraic calculator needs parentheses keys, while RPN simply uses 3 enter 4 + 5 enter 6 + *. Second, you can always see intermediate results on the stack, making it easier to verify calculations step by step. Third, chained calculations flow more naturally because the result of one operation automatically becomes an operand for the next. Fourth, there is never ambiguity about operation order, reducing input errors. Engineers, scientists, and financial professionals who perform many sequential calculations often prefer RPN for these efficiency gains, despite the initial learning curve.
References
Reviewed for accuracy by Manoj Kumar, Mathematics Educator · Editorial policy
Related Calculators
🧮Inequality to Interval Notation Calculator
Calculate inequality to interval notation with inputs, formulas, and instant results.
🧮Interval Notation Calculator
Calculate interval notation with inputs, formulas, and instant results.
🧮Degrees to Radians Converter
Calculate degrees to radians converter with inputs, formulas, and instant results.
🧮Radians to Degrees Converter
Calculate radians to degrees converter with inputs, formulas, and instant results.
🧮Scientific Notation Calculator
Calculate scientific notation with inputs, formulas, and instant results.
🧮Binary Fraction Converter
Calculate binary fraction converter with inputs, formulas, and instant results.
🧮Gray Code Converter
Calculate gray code converter with inputs, formulas, and instant results.
🧮IEEE 754 Floating-Point Converter
Calculate ieee754floating point converter with inputs, formulas, and instant results.