INFIX TO POSTFIX CONVERSION

If you have any queries please leave a message here
Your Message
×


Algorithm to Convert Infix To Postfix

Let, X is an arithmetic expression written in infix notation. This algorithm finds the equivalent postfix expression Y.
  1. Push “ ( ” onto Stack, and add “ ) ” to the end of X.

  2. Scan X from left to right and repeat Step 3 to 6 for each element of X until the Stack is empty.

  3. If an operand is encountered, add it to Y.

  4. If a left parenthesis is encountered, push it onto Stack.

  5. If an operator is encountered ,then :

    • Repeatedly pop from Stack and add to Y each operator (on the top of Stack) which has the same precedence as or higher precedence than operator.

    • Add operator to Stack.
      [ End of If ]

  6. If a right parenthesis is encountered ,then :

    • Repeatedly pop from Stack and add to Y each operator (on the top of Stack) until a left parenthesis is encountered.

    • Remove the left Parenthesis.
      [ End of If ]
      [ End of If ]

  7. END.

Example

Infix Expression : A + (B * C - ( D / E ^ F ) * G ) * H

ScannedStackPostfix ExpressionDescription
(Start
A(A
+(+A
((+(A
B(+(AB
*(+(*AB
C(+(*ABC
-(+(-ABC*' * ' is at highest precedence then ' - '
((+(-(ABC*
D(+(-(ABC*D
/(+(-(/ABC*D
E(+(-(/ABC*DE
^(+(-(/^ABC*DE
F(+(-(/^ABC*DEF
)(+(-ABC*DEF^/POP from top on Stack, that's why ' ^ ' come first
*(+(-*ABC*DEF^/
G(+(-*ABC*DEF^/G
)(+ABC*DEF^/G*-POP from top on Stack, that's why ' * ' come first
*(+*ABC*DEF^/G*-
H(+*ABC*DEF^/G*-H
)EmptyABC*DEF^/G*-H*+END



C-Program to Convert Infix to Postfix Expression

/* This program converts infix expression to postfix expression.
  * This program assume that there are Five operators: (*, /, +, -,^)
  * This program will not work for fractional numbers.
  * Further this program does not check whether infix expression is valid or not in terms of number of operators and operands.*/

#include<stdio.h>
// for exit() function
#include<stdlib.h>
// for isdigit(char ) function
#include<ctype.h>
#include<string.h>
#define SIZE 100

// Global Variable Declaration
char stack[SIZE];
int top = -1;

//Global Function Declaration
void push(char c);
char pop();
int isoperator(char symbol);
int precedence(char symbol);
void InfixToPostfix(char infix_exp[], char postfix_exp[]);

// main() function begins
void main()
{
// Declare infix string and postfix string
char infix[SIZE], postfix[SIZE];
printf("\n\n Enter Infix expression : ");
gets(infix);
// Call to convert
InfixToPostfix(infix,postfix);
printf("\n Postfix Expression: ");
// Print postfix expression
puts(postfix);
}

void InfixToPostfix(char infix_exp[], char postfix_exp[])
{
int i, j;
char item, x;
// push ' ( ' onto stack
push('(');
// add ' ) ' to infix expression
strcat(infix_exp,")");
i=0;
j=0;
// Initialize before loop
item=infix_exp[i];
// Run loop till end of infix expression
while(item != '\0')
{
if(item == '(')
{
push(item);
}
else if( isdigit(item) || isalpha(item))
{
// Add operand symbol to postfix expr
postfix_exp[j] = item;
j++;
}
else if(isoperator(item) == 1)
{
// pop all higher precendence operator and add them to postfix expresion
x=pop();
while(isoperator(x) == 1 && precedence(x)>= precedence(item))
{
postfix_exp[j] = x;
j++;
x = pop();
}
// push the last pop oprerator symbol onto stack
push(x);
// push current oprerator symbol onto stack
push(item);
}
// if current symbol is ')' then pop and keep popping until '(' encounterd
else if(item == ')')
{
x = pop();
while(x != '(')
{
postfix_exp[j] = x;
j++;
x = pop();
}
}
else
{
// if current symbol is neither operand not '(' nor ')' and nor operator
printf("\nInvalid infix Expression.\n");
break;
}
i++;
// Go to next symbol of infix expression */
item = infix_exp[i];
} // End while loop
if(top > 0)
printf("\n Invalid infix Expression.");
postfix_exp[j] = '\0';
}

// Define push operation
void push(char c)
{
if(top >= SIZE-1)
printf("\n Stack Overflow.");
else
{
top++;
stack[top] = c;
}
}

// Define pop operation
char pop()
{
char c;
c='\0';
if(top < 0)
printf("\n Stack Underflow.");
else
{
c = stack[top];
top--;
}
return c;
}

// Define function that is used to determine whether any symbol is operator or not
int isoperator(char symbol)
{
if(symbol == '^' || symbol == '*' || symbol == '/' || symbol == '+' || symbol == '-')
return 1;
else
return 0;
}

// Define fucntion that is used to assign precendence to operator.
// In this fucntion we assume that higher integer value means higher precendence

int precedence(char symbol)
{
if(symbol == '^')
return(5);
else if(symbol == '/')
return(4);
else if(symbol == '*')
return(3);
else if(symbol == '+')
return(2);
else if(symbol == '-')
return(1);
else
return(0);
}



More Details on Infix to Postfix Conversion


ABOUT US

QuestionSolves.com is an educational website that helps worldwide students in solving computer education related queries.

Also, different software like Visual Studio, SQL Server, Oracle etc. are available to download in different versions.

Moreover, QuestionSolves.com provides solutions to your questions and assignments also.


MORE TOPIC


Windows Command

UNIX Command

IGNOU Assignment Solution

IGNOU Question Paper Solution

Solutions of Different Questions


WHAT WE DO


Website Devlopment

Training

Home Learning

Provide BCA, MCA Projects

Provide Assignment & Question Paper Solution


CONTACT US


Follow Us