Infix to Postfix using Stack

Infix to postfix conversion is very common in expression evaluation on computers. We, as a human, are good at interpreting infix notation, but computer evaluates the expression in postfix form. We will discuss both kinds of notations and we will also discuss the algorithm for the conversion of infix to postfix using stack data structures.

Infix Notation

Infix notation is a standard form of constructing arithmetic expressions in which the operator is placed between the operands. This notation is also used in programming languages. As an illustration, the operator “+” is positioned in the middle of the equation “2 + 3,” with the operands “2” and “3” on either side of it. Reading and writing with infix notation is straightforward for humans, but parsing it can be challenging for computers.

Postfix Notation

Postfix notation, also referred to as Reverse Polish notation is a different method of representing arithmetic expressions that places the operator after the operands. This notation is also known as “Reverse Polish notation.” For instance, the statement “2 plus 3” would be written as “2 three plus” if it were to be represented using postfix notation. When using postfix notation, the operands come first in the list, then the operator comes after that. Because it is simple to interpret and evaluate using a stack data structure, the postfix notation sees widespread application in the field of computer science.

Infix to postfix conversion using stack
Infix to postfix conversion

Example of Conversion

Example 1: a + b * c – d

  1. a + bc* – d
  2. abc*+ – d
  3. abc*+d-

Example 2: a ^ b ^ c * d – (e + f / g)

  1. a ^ b ^ c * d – (e + fg/)
  2. a ^ b ^ c * d – efg/+
  3. a ^ bc^ * d – efg/+
  4. abc^^ * d – efg/+
  5. abc^^d* – efg/+
  6. abc^^d*efg/+-

Example 3 a + b * c / (a + b * c)

  1. a + b * c / (a + b * c)
  2. a + b * c / (a + bc*)
  3. a + b * c / abc*+
  4. a + bc* / abc*+
  5. a + bc*abc*+/
  6. abc*abc*+/+

Infix to Postfix conversion using Stack

If you have a stack, you can transform an infix expression to a postfix expression by following these steps:

  1. Construct a stack that is empty to store the operators.
  2. Make a postfix expression string that has no content.
  3. Go from left to right as you examine the infix phrase.
  4. If the character that is now being processed is an operand (a number or a variable), then include it in the postfix expression.
  5. Put the character on top of the stack if it is an opening parenthesis and the current character is one.
  6. If the currently displayed character is an operator, remove those operators from the stack and add them to the postfix expression until either of the following conditions is met:
    1. There is nothing on top of the stack.
    2. The item on top of the stack is an opening parenthesis.
    3. The stack is empty. The precedence of the operator that is now on top of the stack has precedence that is either lower than or equal to the precedence of the operator that is currently active.
  7. The next step is to place the currently active operator atop the stack.
  8. If the currently-selected character is a closing parenthesis, pop operators from the stack and add them to the postfix expression one at a time until an opening parenthesis is discovered. Throw away both sets of parenthesis.
  9. It is necessary to repeat steps 4 through 7 until the complete infix expression has been analysed.
  10. Remove any operators that are still present from the stack, then include them in the postfix expression.

Example: Infix to Postfix conversion using Stack

Here is an illustration of that:

Infix expression: 22 + 33 * 44 – (55 + 66)
Stack: EMPTY
Postfix expression: EMPTY

Step 3: It involves reading the expression containing the infix from left to right.
The number 22 is an operand. Include it in the expression using the postfix.
Postfix expression number 22 is stacked.

Step 4: The number 33 serves as an operand. Include it in the expression using the postfix.
Stack:
Postfix expression: 22 33

Step 5: The plus sign (plus) is an operator. Place it on top of the other items.
Stack: +
Postfix expression: 22 33

Step 6: The number 44 serves as an operand. Include it in the expression using the postfix.
Stack: +
Postfix expression: 22 33 44

Step 6: Because * has higher precedence than +, it will remain on the stack.
Stack: + *
Postfix expression: 22 33 44

Step 4: an operator is a minus sign. Take the asterisk from the top of the stack, and put it into the postfix expression. Stack Expression: 22 33 44 * Postfix Expression:

Step 5: (is the first parenthesis of the sentence. Place it on top of the other items.
Stack: + (
Postfix expression: 22 33 44 *

Step 4: The number 55 is an operand. Include it in the expression using the postfix.
Stack: + (
Postfix expression: 22 33 44 * 55

Step 5: The plus sign (plus) is an operator. Place it on top of the other items.
Stack: + (+
Postfix expression: 22 33 44 * 55

Step 4: The number 66 is an operand. Include it in the expression using the postfix.
Stack: + (+
Postfix expression: 22 33 44 * 55 66

Step 7: The closing parenthesis for Step 7 is shown here. Remove the + and the ( from the stack, then throw them away. To complete the postfix expression, add +.
Stack: +
Postfix expression: 22 33 44 * 55 66 +

The precedence of – is lower than that of +, hence it must be placed on the stack.
Postfix expression: 22 33 44 * 55 66 + in the stack

Step 4: This marks the end of the expression. Remove the dash character “-” from the stack, then incorporate it into the postfix expression.
Stack: expression using the postfix stack: 22 33 44 * 55 66 + –

The whole expression for the postfix is as follows: 22 33 44 * 55 66 + –

Python Code to convert Infix to Postfix

def infix_to_postfix(infix):
    stack = []
    postfix = ""
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '%': 2, '^': 3}
    associativity = {'+': 'left', '-': 'left', '*': 'left', '/': 'left', '%': 'left', '^': 'right'}
    
    for elem in infix:
        if elem.isalnum():
            postfix += elem
        elif elem == '(':
            stack.append(elem)
        elif elem == ')':
            while stack[-1] != '(':
                postfix += stack.pop()
            stack.pop() # discard left parenthesis
        elif elem in precedence:
            while (len(stack) > 0 and stack[-1] in precedence 
                   and (precedence[stack[-1]] > precedence[elem] 
                        or (precedence[stack[-1]] == precedence[elem] 
                            and associativity[elem] == 'left'))):
                postfix += stack.pop()
            stack.append(elem)

    # Retriving postfix notation from stack
    while len(stack) > 0:
        postfix += stack.pop()
    return postfix


infix = "a*b*c"# Left Associative
postfix = infix_to_postfix(infix)
print('Infix Notation   : ', infix)
print('Postfix Notation : ', postfix)

infix = "a^b^c" # Right associative
postfix = infix_to_postfix(infix)
print('\nInfix Notation   : ', infix)
print('Postfix Notation : ', postfix)

infix = "a*b^c-(d^e*f^g)+h"
postfix = infix_to_postfix(infix)
print('\nInfix Notation   : ', infix)
print('Postfix Notation : ', postfix)

Output:

Infix Notation   :  a*b*c
Postfix Notation :  ab*c*

Infix Notation   :  a^b^c
Postfix Notation :  abc^^

Infix Notation   :  a*b^c-(d^e*f^g)+h
Postfix Notation :  abc^*de^fg^*-h+

In this implementation, we first create an empty stack, an empty postfix string, and two dictionaries to store the operator precedence and associativity.

We then iterate through the infix expression from left to right, and for each element, we check if it is an operand, a left parenthesis, a right parenthesis, or an operator.

If the element is an operand, we add it to the output queue.

If the element is a left parenthesis, we push it onto the stack.

If the element is a right parenthesis, we repeatedly pop operators from the stack and add them to the output queue until a left parenthesis is encountered. We discard both the left and right parentheses.

If the element is an operator, we repeatedly pop operators from the stack and add them to the output postfix string as long as they have equal or higher precedence than the current operator, or have equal precedence and the current operator is left-associative. We then push the current operator onto the stack.

After all elements have been processed, we pop any remaining operators from the stack and add them to the output postfix string.

Finally, we return the resulting output queue, which contains the postfix equivalent of the input infix expression.


YouTube Channel: CodeCrucks

Leave a Reply

Your email address will not be published. Required fields are marked *