Advanced Database Management System - Tutorials and Notes: Convert infix expression to postfix expression using stack - algorithm

Search Engine

Please visit, subscribe and share 10 Minutes Lectures in Computer Science

Thursday, 18 January 2018

Convert infix expression to postfix expression using stack - algorithm

How to convert infix expression to postfix expression using stack?, Algorithm for converting infix expression to postfix expression, solved examples for postfix conversion

Algorithm - Infix to Postfix using Stack

  • 1: Read the input string from left to right character by character.
  • 2: If the input character is an operand, then send it to the output.
  • 3: If the input character is an operator, then call PUSH operation based on the following;
    • 3a: If the stack is empty, then PUSH the character into the stack.
    • 3b: If the stack is not empty, then compare the priority of the top element in the stack with that of the new operator to be pushed.
      • If the new operator is with higher priority, then PUSH the operator into stack.
      • If the new operator is with lower priority, then POP the top element from the stack and add it to the output.
    • Repeat 3b until stack is empty or the top element is with lower priority than the operator to be pushed.
  • 4: Repeat steps 2 to 3b for entire input string.
  • 5: If you have reached the end of the input string and the stack is empty then the output is your postfix expression. 
Example:

Infix Expression: A + B * C


Input character
Operation
Stack
Output
A

Empty
A
+
PUSH
+
A
B

+
AB
*
PUSH
+*
AB
C

+*
ABC
End of input
POP

ABC*+
 
 Postfix expression: ABC*+

******************

Go to Data structures home page

Go to Programs for implementing data structures page





Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents