Expression notation

The essentials

An arithmetic expression can be written in three notations. In infix, the operator is between operands (A + B). In prefix (Polish notation), the operator comes before the operands (+ A B). In postfix (reverse Polish notation), the operator comes after the operands (A B +). Postfix and prefix need no brackets and no precedence rules, so computers evaluate them easily using a stack.

Key points

• Precedence: brackets first; then ^ (exponent); then *, /, %; then +, −. Operators of equal precedence (except ^) are applied left to right.
• Infix to postfix examples: A + B * C → A B C * +; (A + B) * C → A B + C *; A * B + C / D → A B * C D / +.
• Infix to prefix example: A + B * C → + A * B C.
• Infix to postfix algorithm (stack of operators): read the expression left to right. Operands go straight to the output. A left bracket is pushed. On a right bracket, pop operators to the output until the left bracket is found, then discard the brackets. On an operator, pop operators of higher or equal precedence to the output, then push the new operator. At the end, pop all remaining operators.
• Evaluating postfix (stack of operands): read left to right. Push each operand. On an operator, pop two operands: the first popped is the right operand, the second is the left operand. Apply the operator and push the result. At the end, the single value on the stack is the answer.
• Example: 5 3 + 2 * → push 5, push 3, + gives 8, push 2, * gives 16.

Exam tips

• For subtraction and division, order matters: for "8 2 −", pop 2 then 8, and compute 8 − 2 = 6.
• Check a conversion by bracketing the infix expression fully and moving each operator to the end of its bracket.

Common mistakes

• Reversing operand order when evaluating postfix.
• Writing operands in a different order from the infix expression; operand order never changes in conversion.