Infix to Postfix conversion using stack algorithm

Infix to postfix conversion algorithm

To understand the concept of infix to postfix conversion concept you need to know the know the meaning of the infix, prefix and postfix. Please go through this article to understand the concept better.

Infix to postfix conversion algorithm
Infix to postfix conversion algorithm
READ  Infix Prefix postfix expressions - datastructures

Before we dive in we need to be aware of a few basic concept used in this algorithm.

Priority order

^  >  * or /  >  + or –

Precedence order

+, – follows left to right

*, / follows left to right

^ right to left

Algorithm

  1. Create a stack
  2. Get an infix expression, and start traversing through the string until the end of a string is encountered.
  3. If the encountered character is an operator then output the character.
  4. Else if it is a right parenthesis then pop from the stack unless a left parenthesis is encountered.
  5. Else if it is an operator or left parenthesis, then compare it with the top of the stack, pop from the stack unless a token with lower priority is encountered or stack is empty.Push it into the stack.
  6. After the end of the string is reached pop and output the stack elements until it is empty.

OTHER RESOURCES

 

 

 

Related Post

Rating: 5.0. From 1 vote.
Please wait...