Back to Study Material Data Structures and Algorithms

Infix Prefix Postfix

Mathematical expressions can be written in three distinct notations depending on where the operator is placed relative to its operands. Understanding all t...

Infix Prefix Postfix

Three Notations for Arithmetic Expressions

Mathematical expressions can be written in three distinct notations depending on where the operator is placed relative to its operands. Understanding all three is essential for compiler design, expression evaluation, and calculator implementations.

Infix notation is the standard human-readable form where the operator sits between two operands: A + B, or (3 * 4) + 2. The notation requires parentheses and operator precedence rules to resolve ambiguity. Without parentheses, the expression 3 + 4 * 2 means different things depending on whether addition or multiplication is evaluated first. Computers must parse precedence rules before evaluating infix expressions, adding complexity to the evaluation engine.

Prefix notation, also called Polish notation, places the operator before its operands: + A B, or + * 3 4 2. No parentheses are needed because the structure is unambiguous. The expression + * 3 4 2 means first multiply 3 and 4 giving 12, then add 2, yielding 14. Prefix notation is processed right to left using a stack: when an operand is encountered, push it; when an operator is encountered, pop two operands, apply the operator, and push the result.

Postfix notation, also called Reverse Polish notation, places the operator after its operands: A B +, or 3 4 * 2 +. This is the easiest notation for computers to evaluate using a stack and is used internally by many calculators and compilers. Process left to right: push operands onto a stack; when an operator is encountered, pop the top two values, apply the operator, and push the result back. The final value on the stack is the answer.

The space complexity for all three evaluation algorithms is O(n) for the stack. Time complexity is O(n) where n is the number of tokens in the expression, since each token is processed exactly once.

Worked example: evaluate postfix expression 5 1 2 + 4 * + 3 -. Push 5, push 1, push 2. Operator +: pop 2 and 1, push 3. Operator *: pop 4 and 3, push 12. Operator +: pop 12 and 5, push 17. Push 3. Operator -: pop 3 and 17, push 14. Result is 14.

Interview tip: practice converting a given infix expression to postfix using the shunting-yard algorithm. This algorithm uses both a stack and an output queue and is one of the most elegant demonstrations of stack utility in compiler front-ends.

Converting Infix to Postfix: The Shunting-Yard Algorithm

The shunting-yard algorithm, designed by Edsger Dijkstra, converts an infix expression to postfix notation using a stack for operators and a queue or list for output. It handles operator precedence and associativity correctly without requiring recursive descent parsing.

The algorithm scans the infix expression token by token from left to right. If a token is a number or variable (an operand), it goes directly to the output queue. If a token is an operator, compare its precedence with the operator currently on top of the stack. While the stack is not empty, the top is not a left parenthesis, and the top operator has greater or equal precedence (for left-associative operators) than the current token, pop the top operator to output. Then push the current operator onto the stack. If the token is a left parenthesis, push it onto the stack. If the token is a right parenthesis, pop operators to output until a left parenthesis is found on the stack, then discard both parentheses. After all tokens are processed, pop any remaining operators from the stack to the output queue.

Operator precedence conventions: exponentiation has the highest precedence (right-associative), multiplication and division next, then addition and subtraction at the lowest precedence among standard operators.

Time complexity is O(n) because each token is pushed and popped at most once. Space complexity is O(n) for the stack in the worst case, such as when all tokens are operators.

Worked example: convert 3 + 4 * 2 to postfix. Scan 3: output [3]. Scan +: stack [+]. Scan 4: output [3, 4]. Scan *: * has higher precedence than +, so push without popping; stack [+, *]. Scan 2: output [3, 4, 2]. End of tokens: pop * to output, then pop + to output. Final postfix: 3 4 2 * +. Evaluating this: push 3, push 4, push 2, operator *, pop 2 and 4, push 8, operator +, pop 8 and 3, push 11. Result 11 matches 3 + (4 * 2).

Interview tip: when explaining the shunting-yard algorithm, draw the stack and output queue side by side and trace each token. This visual explanation is far clearer than prose alone and demonstrates structured thinking.

Evaluating Prefix Expressions with a Stack

Evaluating a prefix expression efficiently uses a single stack and a right-to-left scan of the expression. This approach is simpler than handling infix notation because no precedence rules or parentheses need to be resolved during evaluation.

The algorithm reads the prefix expression from right to left, one token at a time. If the token is an operand (a number), push it onto the stack. If the token is an operator, pop the top two elements from the stack, apply the operator to them in the correct order (the first popped value is the left operand and the second popped value is the right operand for all non-commutative operators), and push the result back onto the stack. After processing all tokens, the single value remaining on the stack is the result of the entire expression.

Maintaining correct operand order is critical for subtraction and division. In prefix notation, the operator appears before both of its operands. When scanning right to left, the first element popped is the left operand and the second is the right. For the prefix expression - 10 3, scanning right to left gives 3 then 10. Pop 3 (left operand) and pop 10 (right operand). This is counterintuitive: remember that scanning right to left reverses the original order, making the second pop the first operand in the expression.

Time complexity is O(n) where n is the number of tokens. Space complexity is O(n) for the stack because in the worst case the expression contains only operands followed by operators.

Worked example: evaluate prefix * + 2 3 4. Scan right to left: token 4, push 4; token 3, push 3; token 2, push 2; token +, pop 2 and 3, compute 2 + 3 equals 5, push 5; token *, pop 5 and 4, compute 5 * 4 equals 20, push 20. Stack has one element: 20. The expression in infix is (2 + 3) * 4, confirming the result is 20.

Interview tip: if you confuse the operand order during an interview, narrate your reasoning aloud. Saying explicitly that the first pop is the left operand and the second pop is the right operand shows the interviewer you understand the subtlety and have a strategy for avoiding bugs.