How to convert Infix expression to Postfix expression using stack in python

In this post, we will convert infix expression to Post-fix expression using stack and implement that stack in python.

In mathematics, we commonly write arithmetic expressions using infix notation, where the operators are placed between the operands. For example, the expression “3 + 4” is written in infix notation. However, infix notation can be difficult to parse algorithmically. To overcome this, we can convert the expression into postfix notation, also known as Reverse Polish Notation (RPN). Postfix notation places the operator after the operands.

Algorithm to convert an infix to postfix expression using stack

The process of converting an infix expression to postfix notation involves two steps:

1. Create an empty stack and an empty postfix list.
2. Iterate over the characters in the infix expression. Depending on the type of character, perform one of the following operations:
   • If the character is an operand (i.e., a number or variable), add it to the postfix list.
   • If the character is a left parenthesis, push it onto the stack.
   • If the character is a right parenthesis, pop operators off the stack and add them to the postfix list until a left parenthesis is encountered. Discard the left parenthesis.
   • If the character is an operator, repeatedly pop operators off the stack and add them to the postfix list until an operator with lower precedence is encountered. Then push the new operator onto the stack.
3. After iterating over all the characters in the infix expression, pop any remaining operators off the stack and add them to the postfix list.

Example

Let’s walk through an example to illustrate this process. Consider the infix expression (3 + 4) * 5 / (2 + 3). Using the above algorithm, we can convert this to postfix notation as follows:

1. We start with an empty stack and an empty postfix list:

               Stack:  []
               Postfix: []

2. We iterate over the characters in the infix expression, performing the following operations for each character:
   • (: We push the left parenthesis onto the stack. Stack: [(] Postfix: []
   • 3: We add the operand to the postfix list. Stack: [(] Postfix: [3]
   • +: We push the operator onto the stack. Stack: [(, +] Postfix: [3]
   • 4: We add the operand to the postfix list. Stack: [(, +] Postfix: [3, 4]
   • ): We pop operators off the stack and add them to the postfix list until we encounter the left parenthesis. We discard the left parenthesis. Stack: [] Postfix: [3, 4, +]
   • *: We push the operator onto the stack. Stack: [*] Postfix: [3, 4, +]
   • 5: We add the operand to the postfix list. Stack: [*] Postfix: [3, 4, +, 5]
   • /: We repeatedly pop operators off the stack and add them to the postfix list until we encounter an operator with lower precedence. Then we push the new operator onto the Stack: [/] Postfix: [3, 4, +, 5, *]
   • (: We push the left parenthesis onto the stack. Stack: [(/, (] Postfix: [3, 4, +, 5, *] We add the operand to the postfix list. Stack: [(/, (] Postfix: [3, 4, +, 5, *, 2]
   • +: We repeatedly pop operators off the stack and add them to the postfix list until we encounter an operator with lower precedence. Then we push the new operator onto the stack. Stack: [(/, (, +] Postfix: [3, 4, +, 5, *, 2, /]
   • 3: We add the operand to the postfix list. Stack: [(/, (, +] Postfix: [3, 4, +, 5, *, 2, /, 3]
   • ): We pop operators off the stack and add them to the postfix list until we encounter the left parenthesis. We discard the left parenthesis. Stack: [(/] Postfix: [3, 4, +, 5, *, 2, /, 3, +]

3. After iterating over all the characters in the infix expression, we pop any remaining operators off the stack and add them to the postfix list.

          Stack:  []
          Postfix: [3, 4, +, 5, *, 2, /, 3, +]

Therefore, the postfix expression equivalent to the infix expression (3 + 4) * 5 / (2 + 3) is 3 4 + 5 * 2 3 + /.

Stack Representation of above example

Example -1:

For example, consider the infix expression (3 + 4) * 5 / (2 + 3). Using the above algorithm, we can convert this to postfix notation as follows:

The resulting postfix expression is 3 4 + 5 * 2 3 + /. The same algorithm can be used to convert any infix expression to postfix notation.

Example 2 :

For example, consider the infix expression A+(B*C-(D/E^F)*G) Using the above algorithm, we can convert this to postfix notation as follows:

The resulting postfix expression is A B C * D E F ^ / G * – H * +. The same algorithm can be used to convert any infix expression to postfix notation.

In conclusion, the process of converting an infix expression to postfix notation involves iterating over the expression and using a stack to keep track of operators and parentheses. By following the algorithm outlined above, we can convert any infix expression to postfix notation, making it easier to parse and evaluate.

Python code to implement infix to postfix conversion using stacks

Here’s a Python code to implement infix to postfix conversion using stacks:

def infix_to_postfix(expression):
    stack = []
    postfix = []
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
    for char in expression:
        if char.isalnum():
            postfix.append(char)
        elif char in ['+', '-', '*', '/']:
            while stack and stack[-1] != '(' and precedence[char] <= precedence.get(stack[-1], 0):
                postfix.append(stack.pop())
            stack.append(char)
        elif char == '(':
            stack.append(char)
        elif char == ')':
            while stack and stack[-1] != '(':
                postfix.append(stack.pop())
            stack.pop()
    while stack:
        postfix.append(stack.pop())
    return ''.join(postfix)

string = input("Enter your infix expression :")
postfix_expr = infix_to_postfix(string)
print(f"Conversion of {string} to Postfix expression is :",postfix_expr)

Output:

Related Post:

• Write a python program to implement a stack for student-details using list data structure
• Write a python program to implement a stack using list
• Write push and pop methods,in python to add books and remove books from list
• Each node of stack contains city-details(pin code of city,name of city).Write a python program to implement push and pop operations in stack