Conversion of infix expression to postfix expression


Problem Statement : Conversion of infix expression to postfix expression

Theory : Infix Expression: Notation in which, the operator comes in-between its operands.
Example: (a+b)*c
Representation of postfix expression is : abc+*

Infix to postfix operation uses following algorithm:

Algorithm:
Step 1: Scan the given string from left to right.
Step 2: Initialize an empty stack
Step 3: If the scanned character is operand, add it to the postfix string
Step 4: If the scanned character is operator and if the stack is empty add it to the stack, else compare the operator with the present operator in the stack. If the present operator is having higher priority then remove it from the stack and add to postfix array else push the new operator at the next position into the stack.
Step 5: Repeat these steps till all the characters get scanned.
Step 6: At the end pop all the operators from the stack and add them to the postfix array.







Steps to perform the operation of conversion :
((a+b)*c)

Symbol
Stack
Postfix Array
(
(

(
((

A
((
a
+
((+
a
B
((+
ab
)
((+)
ab
*
(*
ab+
C
(*
ab+c
)
(*)
ab+c

Empty
ab+c*

In this example, the expression from inner bracket is converted into postfix format i.e. ab+ and then the outer bracket is consider and the final result is ab+c*.

Questions:
  1. What is operator precedence order?
  2. Explain the need of conversion from infix to prefix.
  3. What are the steps to convert an expression from infix to prefix?
  4. write an expression with 5 operands in all forms that is prefix,infix and postfix form.

Comments