1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

InFix to PostFix and PostFix expression evaluation.

Discussion in 'C' started by shabbir, Oct 21, 2006.

  1. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,293
    Likes Received:
    365
    Trophy Points:
    83
    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:
    #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:
    #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:

    Pepper Mint and (deleted member) like this.
  2. Peter_APIIT

    Peter_APIIT New Member

    Joined:
    Apr 11, 2007
    Messages:
    92
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Malaysia
  3. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,293
    Likes Received:
    365
    Trophy Points:
    83
    Thanks.
     
  4. bsnpr_24

    bsnpr_24 New Member

    Joined:
    Apr 23, 2007
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    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!
     
  5. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,293
    Likes Received:
    365
    Trophy Points:
    83
    I guess the function can always be converted into class easily
     
  6. bsnpr_24

    bsnpr_24 New Member

    Joined:
    Apr 23, 2007
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    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
     
  7. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,293
    Likes Received:
    365
    Trophy Points:
    83
    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.
     
  8. ranims

    ranims New Member

    Joined:
    May 24, 2007
    Messages:
    6
    Likes Received:
    0
    Trophy Points:
    0
    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
     
  9. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,293
    Likes Received:
    365
    Trophy Points:
    83
    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
     
  10. ranims

    ranims New Member

    Joined:
    May 24, 2007
    Messages:
    6
    Likes Received:
    0
    Trophy Points:
    0
    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
     
  11. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,293
    Likes Received:
    365
    Trophy Points:
    83
    I have used 4 variables as follows
    A=2, B=3, C=4, D=5
    with the expression as AB+CD+* and I got the following
    Code:
    
    Enter the total number of variables you will use
    4
    
    Assign values to each of them
    
    Assign value to A       2
    
    Assign value to B       3
    
    Assign value to C       4
    
    Assign value to D       5
    
    Enter a postfix expression using above variables
    AB+CD+*
    Result is 45
    . I don't see any problem. Can you please clarify a bit more.
     
  12. abdo

    abdo New Member

    Joined:
    Sep 8, 2007
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    can you make this evaluates a postfix in java....
    please cuz i saw it more easier for me to understand it.....
    thank you
     
  13. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,293
    Likes Received:
    365
    Trophy Points:
    83
    If you have understood it you should be able to convert it into any other language and then post it here for others to see.
     
  14. keshaj

    keshaj New Member

    Joined:
    Jun 26, 2007
    Messages:
    3
    Likes Received:
    0
    Trophy Points:
    0
    i need a progrm in this....InFix to PostFix and PostFix expression evaluation.....program in c.... i really need ur help..
     
  15. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,293
    Likes Received:
    365
    Trophy Points:
    83
    Did you read the article content. If not you should and you will get what you are looking for.
     
  16. bloom_star7

    bloom_star7 New Member

    Joined:
    Sep 15, 2007
    Messages:
    4
    Likes Received:
    1
    Trophy Points:
    0
    Shabbir,

    In the 4th point you mentioed i think it should be operator not operand.

    4.If the scanned character is an Operator[not Operand] 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.

    May be i am wrong. Please let me konw if i missed something.
     
  17. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,293
    Likes Received:
    365
    Trophy Points:
    83
    Yes it should be Operator as the precedence of the operand does not mean anything. Thanks for pointing it out and I have corrected that in the main article.
     
  18. abdo

    abdo New Member

    Joined:
    Sep 8, 2007
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    i try to do this....i want to know if i use this program, is that correct?
    Q:
    How to write a java program taht evaluates a postfix expression by using concept of stack?
    --------------------------------------------
    Code:
    public class PostfixEval 
    {
    
       public static void main(String[] args) 
        {
          
          TextIO.putln("This program can evaluate postfix expressions such as\n");
          TextIO.putln("        2 2 +");
          TextIO.putln("or");
          TextIO.putln("        7.3 89.2 + 9 1.83 * 2 + /\n");
          TextIO.putln("The operators +, -, *, /, and ^ can be used.\n\n");
          
          while (true) 
            {
                 // Get and process one line of input from the user.
            TextIO.putln("\n\n\nEnter a postfix expression or press return to end:\n");
            TextIO.put("? ");
            skipSpaces();
            if (TextIO.peek() == '\n') 
              {
                   // If the line is empty (except for spaces), we are done.
                break;
            }
            readAndEvaluate(); // Process the input.
            TextIO.getln(); // Discard the end-of-line.
          }
          
          TextIO.putln("\n\nExiting program.");
          
       } // end main();
       
       
       static void skipSpaces() 
        {
            // Skip past any spaces and tabs on the current input line.
            // When this routine returns, the next character is either
            // the end-of-line character, '\n', or is a non-blank.
          while (TextIO.peek() == ' ' || TextIO.peek() == '\t') 
            {
            TextIO.getAnyChar();
          }
       }
       
       
       static void readAndEvaluate()
         {
            // Read one line of input and process it as a postfix expression.
            // If the input is not a legal postfix expression, then an error
            // message is displayed. Otherwise, the value of the expression
            // is displayed. It is assumed that the first character on
            // the input line is a non-blank. (This is checked in the
            // main() routine.)
           
          NumberStack stack; // For evaluating the expression.
          
          stack = new NumberStack(); // Make a new, empty stack.
          
          TextIO.putln();
          
          while (TextIO.peek() != '\n') 
            {
          
              if ( Character.isDigit(TextIO.peek()) ) 
                 {
                      // The next item in input is a number. Read it and
                      // save it on the stack.
                  double num = TextIO.getDouble();
                  stack.push(num);
                  TextIO.putln("   Pushed constant " + num);
              }
              else 
                 {
                     // Since the next item is not a number, the only thing
                     // it can legally be is an operator. Get the operator
                     // and perform the operation.
                  char op; // The operator, which must be +, -, *, /, or ^.
                  double x,y;     // The operands, from the stack, for the operation.
                  double answer; // The result, to be pushed onto the stack.
                  op = TextIO.getChar();
                  if (op != '+' && op != '-' && op != '*' && op != '/' && op != '^') 
                      {
                          // The character is not one of the acceptable operations.
                      TextIO.putln("\nIllegal operator found in input: " + op);
                      return;
                  }
                  if (stack.isEmpty()) 
                      {
                      TextIO.putln("   Stack is empty while trying to evaluate " + op);
                      TextIO.putln("\nNot enough numbers in expression!");
                      return;
                  }
                  y = stack.pop();
                  if (stack.isEmpty()) 
                      {
                      TextIO.putln("   Stack is empty while trying to evaluate " + op);
                      TextIO.putln("\nNot enough numbers in expression!");
                      return;
                  }
                  x = stack.pop();
                  switch (op) 
                      {
                     case '+': answer = x + y; break;
                     case '-': answer = x - y; break;
                     case '*': answer = x * y; break;
                     case '/': answer = x / y; break;
                     default:   answer = Math.pow(x,y); // (op must be '^'.)
                  }
                  stack.push(answer);
                  TextIO.putln("   Evaluated " + op + " and pushed " + answer);
              }
              
              skipSpaces();
          
          } // end while
          
          // If we get to this point, the input has been read successfully.
          // If the expression was legal, then the value of the expression is
          // on the stack, and it is the only thing on the stack.
          
          if (stack.isEmpty()) 
            { // Impossible if the input is really non-empty.
              TextIO.putln("No expression provided.");
              return;
          }
           
          double value = stack.pop(); // Value of the expression.
          TextIO.putln("   Popped " + value + " at end of expression.");
    
          if (stack.isEmpty() == false) {
              TextIO.putln("   Stack is not empty.");
              TextIO.putln("\nNot enough operators for all the numbers!");
              return;
          }
    
          TextIO.putln("\nValue = " + value);
          
          
       } // end readAndEvaluate()
    
    
    } // end class PostfixEval 
    -----------------------------------------------------------------------
    Attached the question,i know for you is simple, but i really need your help...Thank you
     
    Last edited by a moderator: Sep 17, 2007
  19. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,293
    Likes Received:
    365
    Trophy Points:
    83
    You are posting Java question in a C-C++ article and I do not expect you would get any help relating to the same but anyway best of luck. You should have read Before you make a query ( Link in upper right corner ) for some better responses.

    Now also about your query I think the code given in the article is simple enough for the Java programmer to convert it into Java but I am not a Java expert.
     
  20. sarah24

    sarah24 New Member

    Joined:
    Sep 25, 2007
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    0
    i need some help pls help me...
    i have written a code for postfix expression evaluation but what if all the data and expressions to be evaluated are in text file..
    pls tell me how can i modify my code ..
    Code:
    #include <iostream>
    #include <stack> 
    #include <string>
    using namespace std;
    
    void main()
    {
        int i, choice = 1;
        string postfixExp;
        char token;
        float value, value1, value2;
        stack<float> s; //Declare a stack of floats
    
       
    
        while (choice != 0)
        {
            cout << "1. Evaluate a postfix expression" << endl;
            cout << "0. Exit " << endl;
            cout << "Enter the number for the option: ";
    
            cin >> choice;
            switch(choice)
            {
                case 1: cout << "Evaluate a postfix expression\n";
                        cout << "Enter the expression: ";
                        cin >> postfixExp;
                        i = 0;
                        token = postfixExp[i];
                        while((i < postfixExp.size()) && (token != '='))
                        {
                            if(isdigit(token))
                            {
                                value = token - '0';
                                s.push(value);
                            }
                            else
                            {
                                value2 = s.top();
                                s.pop();
                                value1 = s.top();
                                s.pop();
                                switch(token)
                                {
                                    case '+': value = value1 + value2;
                                              break;
                                    case '-': value = value1 - value2;
                                              break;
                                    case '*': value = value1*value2;
                                              break;
                                    case '/': value = value1/value2;
                                              break;
                                }
                                s.push(value);
                            }
                   i++;
                   token = postfixExp[i];
                        }
                        value = s.top();
                        s.pop();
                        cout << postfixExp << " " << value << endl;         
                        break;
    
                case 0: cout << "Exiting the program\n";
                        break;
    
                default: cout << "Invalid option\n";
                        break;
            }
         cout << endl;
        }
    }
     
    Last edited by a moderator: Sep 27, 2007

Share This Page