Conversion from Infix to Postfix Notation

Why Convert Infix to Postfix?

Humans naturally understand infix expressions like x + y / z. We know from the BODMAS rule that division has higher precedence than addition, so we evaluate y / z first, even though the + operator appears earlier when reading left to right. A computer, however, does not have this built-in knowledge of operator precedence. If we simply feed it an infix expression, it would not know which operation to perform first without extra rules.

Postfix notation (also called Reverse Polish Notation) solves this problem. In a postfix expression, the operators are placed after their operands, and the order of operators already reflects the correct precedence. This means a computer can evaluate the expression in a single left-to-right scan, without needing to worry about precedence or parentheses. The same logic applies to prefix notation, where operators come before operands.

The conversion from infix to postfix is therefore a crucial step in expression evaluation. A stack is the perfect data structure for this job because it can temporarily hold operators (and parentheses) until their correct position in the output is determined.

The Algorithm for Conversion (Algorithm 3.1)

The algorithm processes the infix expression character by character, from left to right. It uses two things:

• A stack to keep track of operators and parentheses.
• A string variable (let's call it postExp) to build the final postfix expression.

Here are the steps:

1. Initialise: Create an empty string postExp and an empty stack.
2. Input: Read the infix expression into a variable, say inExp.
3. Process each character: For every character in inExp (from left to right), do the following:
   • If the character is an operand (like a variable x, y, or a number 8): Append it directly to postExp.
   • If the character is a left parenthesis (: Push it onto the stack.
   • If the character is a right parenthesis ): Pop operators from the stack one by one and append each to postExp until you pop the matching left parenthesis (. Discard both parentheses (do not append them to postExp).
   • If the character is an operator (like +, -, *, /):
     • Check the precedence of this operator against the operator currently at the top of the stack.
     • If the current operator has lower precedence than the operator at the top of the stack: Pop operators from the stack and append them to postExp until you encounter an operator with precedence less than the current operator. Then, push the current operator onto the stack. Because popping only stops at a strictly lower-precedence operator, an operator of equal precedence already on the stack is popped first.
     • Otherwise (if the current operator has higher precedence, or the stack top is not an operator): Simply push the current operator onto the stack.
4. Empty the stack: After all characters in inExp have been processed, pop any remaining operators from the stack and append them to postExp.
5. Output: The string postExp now contains the equivalent postfix expression.

Worked Example: Converting (x + y) / (z * 8)

Let's trace Algorithm 3.1 with the infix expression (x + y) / (z * 8). The following table shows the state of the stack and the postExp string after processing each symbol.