Tuesday, February 17, 2015

C Program and Algorithm for Conversion of an Expression from Infix to Postfix

In infix notation or expression operators are written in between the operands while in postfix notation every operator follows all of its operands.

Example:
Infix Expression: 5+3*2
Postfix Expression: 5 3 2*+.

Algorithm for Conversion of an Expression from Infix to Postfix

Let Q be any infix expression and we have to convert it to postfix expression P. For this the following procedure will be followed.

1. Push left parenthesis onto STACK and add right parenthesis at the end of Q.

2. Scan Q from left to right and repeat step 3 to 6 for each element of Q until the STACK is empty.

3. If an operand is encountered add it to P.

4. If a left parenthesis is encountered push it onto the STACK.

5. If an operator is encountered, then
  • Repeatedly pop from STACK and add to P each operator which has same precedence as or higher precedence than the operator encountered.
  • Push the encountered operator onto the STACK.

6. If a right parenthesis is encountered, then
  • Repeatedly pop from the STACK and add to P each operator until a left parenthesis is encountered.
  • Remove the left parenthesis; do not add it to P.

7. Exit

Also Read: C Program and Algorithm for Evaluation of a Postfix Expression
Also Read: What is Quick Sort? Algorithm and C Program to Implement Quick Sort

An example of converting infix expression into postfix form, showing stack status after every step is given below. Here RPN stands for reverse polish notation (postfix notation).

An example of converting infix expression into postfix form, showing stack status after every step


C Program for Conversion of an Expression from Infix to Postfix

// Operator supported: +,-,*,/,%,^,(,)
// Operands supported: all single character operands

#include<stdio.h>
#include<conio.h>
#include<ctype.h>

#define MAX 50

typedef struct stack
{
    int data[MAX];
    int top;
}stack;

int precedence(char);
void init(stack *);
int empty(stack *);
int full(stack *);
int pop(stack *);
void push(stack *,int);
int top(stack *);   //value of the top element
void infix_to_postfix(char infix[],char postfix[]);

void main()
{
    char infix[30],postfix[30];
    printf("Enter an infix expression(eg: 5+2*4): ");
    gets(infix);
    infix_to_postfix(infix,postfix);
    printf("
Postfix expression: %s",postfix);
}

void infix_to_postfix(char infix[],char postfix[])
{
    stack s;
    char x,token;
    int i,j;    //i-index of infix,j-index of postfix
    init(&s);
    j=0;

    for(i=0;infix[i]!=
Posted by at
Labels: , , , , , , , , , , , ,

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.

Subscribe to: Post Comments (Atom)