InFix to PostFix and PostFix expression evaluation.

shabbir's Avatar author of InFix to PostFix and PostFix expression evaluation.
This is an article on InFix to PostFix and PostFix expression evaluation. in C.
Rated 5.00 By 1 users
InFix to PostFix

Introduction



Infix Expression :

Notation in which the operator separates its operands. Eg (a + b) * c. Infix notation requires the use of brackets to specify the order of evaluation.

Postfix Expression :

Reverse Polish Notation or Suffix Notation Notation in which the operator follows its operands. Eg a + b * c represented as abc*+.

Infix to Postfix Conversion Algo :
  1. Scan the Infix string from left to right.
  2. Initialise an empty stack.
  3. If the scannned character is an operand, add it to the Postfix string. If the scanned character is an operator and if the stack is empty Push the character to stack.
  4. If the scanned character is an Operator and the stack is not empty, compare the precedence of the character with the element on top of the stack (topStack). If topStack has higher precedence over the scanned character Pop the stack else Push the scanned character to stack. Repeat this step as long as stack is not empty and topStack has precedence over the character.
  5. Repeat this step till all the characters are scanned.
  6. After all characters are scanned, we have to add any character that the stack may have to the Postfix string. If stack is not empty add topStack to Postfix string and Pop the stack. Repeat this step as long as stack is not empty.

The Code



Code: C
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>

#define N 64

#define LP 10
#define RP 20
#define OPERATOR 30
#define OPERAND 40

// Left parentheses precedence. Minimum of all
#define LPP 0

// Addition Subtraction precedence. Minimum among all operator precedence
#define AP 1
#define SP AP

// Multiplication divisor precedence.
#define MP 2
#define DP MP

// Remainder precedence.
#define REMP 2

#define NONE 9

static char infix[N+1],stack[N],postfix[N+1];
static int top;

void infixtopostfix(void);     /** POSTFIX CONVERSION FUNCTION **/
int gettype(char);             /** TYPE OF EXPRESSION GENERATOR **/
void push(char);               /** PUSH FUNCTION **/
char pop(void);                /** POP FUNCTION **/
int getprec(char);             /** PRECEDENCE CHECKER FUNCTION **/

void main()
{
    char ch;
    do
    {
        top=-1;
        printf("\nEnter an infix expression\n");
        fflush(stdin);
        gets(infix);
        infixtopostfix();
        printf("\ninfix = %s\npost fix =%s\n",infix,postfix);
        printf("\nDo you wish to continue\n");
        ch=getche();
    }while(ch=='Y' || ch=='y');
}

void infixtopostfix(void)
{
    int i,p,l,type,prec;
    char next;
    i=p=0;
    l=strlen(infix);
    while(i<l)
    {
        type=gettype(infix[i]);
        switch(type)
        {
        case LP:
            push(infix[i]);
            break;
        case RP:
            while((next=pop())!='(')
                postfix[p++]=next;
            break;
        case OPERAND:
            postfix[p++]=infix[i];
            break;
        case OPERATOR:
            prec=getprec(infix[i]);
            while(top>-1 && prec <= getprec(stack[top]))
                postfix[p++]=pop();
            push(infix[i]);
            break;
        }
        i++;
    }
    while(top>-1)
        postfix[p++]=pop();
    postfix[p]='\0';
}


int gettype(char sym)
{
    switch(sym)
    {
    case '(':
        return(LP);
    case ')':
        return(RP);
    case '+':
    case '-':
    case '*':
    case '/':
    case '%':
        return(OPERATOR);
    default :
        return(OPERAND);
    }
}

void push(char sym)
{
    if(top>N)
    {
        printf("\nStack is full\n");
        exit(0);
    }
    else
        stack[++top]=sym;
}

char pop(void)
{
    if(top<=-1)
    {
        printf("\nStack is empty\n");
        exit(0);
    }
    else
        return(stack[top--]);
}

int getprec(char sym)
{
    switch(sym)
    {
    case '(':
        return(LPP);
    case '+':
        return(AP);
    case '-':
        return(SP);
    case '*':
        return(MP);
    case '/':
        return(DP);
    case '%':
        return(REMP);
    default :
        return(NONE);
    }
}

Post Fix Expression Evaluation



Now after making the conversion what we have gained. As PostFix strings are parenthesis-free notation mathematical calculations and precedence is already defined within the string and so calculation is done very easily.

Postfix Expression evaluation Algo :
  1. Scan the Postfix string from left to right.
  2. Initialise an empty stack.
  3. If the scannned character is an operand, add it to the stack. If the scanned character is an operator, there will be atleast two operands in the stack.
  4. If the scanned character is an Operator, then we store the top most element of the stack(topStack) in a variable temp. Pop the stack. Now evaluate topStack(Operator)temp. Let the result of this operation be retVal. Pop the stack and Push retVal into the stack.
  5. Repeat this step till all the characters are scanned.
  6. After all characters are scanned, we will have only one element in the
    stack. Return topStack as result

The Code



Code: C
#include<stdio.h>
#include<conio.h>
#include<ctype.h>

#define N 100

void push(float,float **);
void pop(float **);

/**********************************************************/
/*****  Evaluation of generalised postfix expression  *****/
/*****       inputed as floating point numbers        *****/
/**********************************************************/

void main()
{
    int var,i,j;
    float stack[N];
    float *top;
    float num[N],res;
    char pfix[N],ch;
    do
    {
        j=0;
        top=stack;
        do
        {
            printf("\nEnter the total number of variables you will use\n");
            scanf("%d",&var);
            if(var>26)
                printf("\nMaximum 26 variables\n");
        }while(var>26);
        printf("\nAssign values to each of them\n");
        for(i=0;i<var;i++)
        {
            printf("\nAssign value to %c\t",('A'+i));
            scanf("%f",&num[i]);
        }
        printf("\nEnter a postfix expression using above variables\n");
        for(i=0;(pfix[i]=getche())!=13;i++)
        {
            if(islower(pfix[i])!=NULL)
            {
                pfix[i]=toupper(pfix[i]);
                printf("\b%c",pfix[i]);
            }
        }
        pfix[i]='\0';
        for(i=0;pfix[i]!='\0';i++)
        {
            if(isalpha(pfix[i])!=NULL)
                push(num[j++],&top);
            else
            {
                pop(&top);
                pop(&top);
                if(pfix[i]=='+')
                {
                    res=*top+*(top+1);
                    push(res,&top);
                }
                else if(pfix[i]=='-')
                {
                    res=*top-*(top+1);
                    push(res,&top);
                }
                else if(pfix[i]=='*')
                {
                    res=*top**(top+1);
                    push(res,&top);
                }
                else if(pfix[i]=='/')
                {
                    res=*top/(*(top+1));
                    push(res,&top);
                }
            }
        }
        printf("\nResult is %g\n",stack[0]);
        printf("\nDo you wish to continue[y/n]\n");
        ch=getche();
    }while(ch=='Y' || ch=='y');
    getch();
}

void push(float num,float **top)
{
    *(*top)=num;
    (*top)++;
}

void pop(float **top)
{
    (*top)--;
}
You can download both the codes in the attachment.
Attached Files
File Type: zip Infix2PostFix and PostfixExpEval.zip (1.9 KB, 541 views)
0
Peter_APIIT's Avatar, Join Date: Apr 2007
Contributor
Nice Job
0
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
Quote:
Originally Posted by Peter_APIIT
Nice Job
Thanks.
0
bsnpr_24's Avatar, Join Date: Apr 2007
Newbie Member
I would love to see the programs that changes infix to postfix and then evaluates it in C++ not in C. Could you give it to me or post it or soemthing i am anxious to see it, thanks!
0
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
Quote:
Originally Posted by bsnpr_24
I would love to see the programs that changes infix to postfix and then evaluates it in C++ not in C. Could you give it to me or post it or soemthing i am anxious to see it, thanks!
I guess the function can always be converted into class easily
0
bsnpr_24's Avatar, Join Date: Apr 2007
Newbie Member
Here is what i got i need the main, i want two functions that you did the one that changes infix to post fix and one that evaluates, i am really stuck can you pleaseeee help me!

Here is my .h
Code:
#include <iostream>
using namespace std;

template <typename ElementType>
#ifndef STACK
#define STACK

class Stack
{
   private:
	   class Node
	   {
   public:
   	     ElementType info;
	     Node *next;
	   };
   typedef Node * Nodeptr;

    public:
		Stack();
		Stack(const Stack<ElementType> &);
		~Stack();
		//Stack<ElementType>  operator=(const Stack<ElementType> &);
		bool empty() const; 
		void Push(ElementType item); 
		ElementType Pop(); 
		ElementType Top() const;
		void display(ostream & out) const; 
		
	private: 
		Node *miStack;
};
template <typename ElementType>
ostream & operator<< (ostream & out, const Stack <ElementType> & astack); //ya

#include "stack.template"
#endif
here is my template (I need something in the top function check it out)
Code:
#include<iostream>
using namespace std;

template <typename ElementType>
Stack<ElementType>::Stack()
{
	miStack=NULL;
}

template <typename ElementType>
Stack<ElementType>::Stack(const Stack<ElementType> & orig)
{
	nodePtr p=orig.miStack;
	nodePtr pnuevo, anterior;
	while (p!=NULL)
	{
		pnuevo=new node;
		pnuevo->info=p->info;
		if (orig.miStack==p)
			miStack=pnuevo;
		else
			anterior->next=pnuevo;
		anterior=pnuevo;
		p=p->next;
	}
	if (orig.miStack==NULL)
		miStack=NULL;
	else
		pnuevo->next=NULL;
}

template <typename ElementType>
Stack<ElementType>::~Stack()
{
	nodePtr p = miStack, anterior;
	while (p!=NULL)
	{
		anterior=p;
		p=p->next;
		delete anterior;
	}
}

/* template <typename ElementType>
Stack<ElementType> Stack<ElementType>::operator = (const Stack<ElementType> & orig)
{
	if (this != & orig)
	{
		nodePtr p=miStack, anterior;
		while (p!=NULL)
		{
			anterior=p;
			p=p->next;
			delete anterior;
		}
	nodePtr q=orig.miStack;
	nodePtr pnuevo;
	while (q!=NULL)
	{
		pnuevo=new node;
		pnuevo->info=p->info;
		if (orig.miStack==p)
			miStack=pnuevo;
		else
			anterior->next=pnuevo;
		anterior=pnuevo;
		q=q->next;
	}
	if (orig.miStack==NULL)
		miStack=NULL;
	else
		miStack=NULL;
}
return *this;
}*/

template <typename ElementType>
bool Stack<ElementType>::empty() const
{
	return (miStack==NULL);
}

template <typename ElementType>
void Stack<ElementType>::Push(ElementType item)
{
	Nodeptr p = new Node;
	p->info=item; 
	p->next=miStack;
	miStack=p;
}

template <typename ElementType>
ElementType Stack<ElementType>::Pop()
{ 
Nodeptr p = miStack, elementType item;
	if(miStack != null)
		item = p->info;
		miStack = miStack->next;
		delete p;
		return item;
	else
	{	cerr<<"Stack vacio.  No se hizo pop "<<endl;
		exit(1);
	}
}

template <typename ElementType>
ElementType Stack<ElementType>::Top()
{ 
	return( )//I dont know what to put here, help me also
}

template <typename ElementType>
void Stack<ElementType>::display (ostream & out)const
{
	nodePtr p;
	p=miStack;
	out<<"Los Elementos de la lista son:";
	while (p!=NULL)
	{
		out<<p->info<<" ";
		p=p->next;
	}
	cout<<endl;
}

template<typename ElementType>	
ostream & operator<<(ostream & out, const Stack<ElementType> & astack)
{  
	astack.display(out); 
	return out;   
}
here is the main(this is what i need help with):
Code:
#include "stack.h"

using namespace std;

void main()
{
	
//HELP!!

}
Please i need help ASAP
0
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
What you are trying to do is have some classes but don't know how to call them. How did you get the classes? If you got from somewhere I am sure they will have the sample implementation as well.
0
ranims's Avatar, Join Date: May 2007
Light Poster
if i am trying to use more than four variables in postfix expression, output is not coming to me.
for ex: ab+ cd+*
can u guide me
sorry if i am wrong
0
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
Copy the code into your compiler (I have used MS VC 6)
Run the Program and enter you will see the following text
Code:
Enter an infix expression
Enter the Infix expression as follows
Code:
(a+b)*(c+d)
You will see output as follows
Code:
infix = (a+b)*(c+d)
post fix =ab+cd+*

Do you wish to continue
I don't see any problem with the 4 variables as input. In fact I don't see any problem when I have input as
Code:
(a+b)*(c+d)*(e+f)
as well
0
ranims's Avatar, Join Date: May 2007
Light Poster
sorry i didn't mentioned clearly, While using postfix evaluation program, if i am typing postfix expression ab+cd+* , result is not coming properly, if ab+ result is ok.
can u verify once. where i am doing wrong

thanks in advance