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

Thursday, 18 January 2018

Convert the infix expression to postfix expression using stack data structure

Convert the infix expression to postfix expression using stack data structure. Infix to postfix conversion explained step-by-step. Infix to postfix conversion using stack example


Convert the following infix expression into postfix expression using stack data structure; show the steps involved;
(A+B)*C-D
Solution:


At the starting of this algorithm;
  • Input string: A+B*C-D
  • Stack is empty
  • Output is NULL
Input character
Operation
Stack
Output
Description
A


A
The input character is an operand. So send the character to output.
+
PUSH
+
A
The input character is an operator. PUSH the operator onto the stack.
B

+
AB
Input is operand, send to output.
*
PUSH
+*
AB
Input is operator, priority of ‘*’ is higher than ‘+’ in the stack. So PUSH the operator onto the stack.
C

+*
ABC
Input is operand, send to output.
-
POP



POP


PUSH
+






-
ABC*



ABC*+


ABC*+
Input is an operator. Priority of ‘-‘ is lower than the priority of top element ‘*’. Hence, POP ‘*’ and add to the output.
Yet, ‘–‘ is small or equal in priority with ‘+’. So POP ‘+’ and add to the output.
Now the stack is empty, so PUSH ‘–‘ onto the stack.
D

-
ABC*+D
Input is an operand, so add it to the output
End of input
POP

ABC*+D-
End of input string is reached. POP all the operators from stack and add to the output.

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









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