Postfix Expression Evaluation

The compiler finds it convenient to evaluate an expression in its postfix form. The virtues of postfix form include elimination of parentheses which signify priority of evaluation and the elimination of the need to observe rules of hierarchy, precedence and associativity during evaluation of the expression.

As Postfix expression is without parenthesis and can be evaluated as two operands and an operator at a time, this becomes easier for the compiler and the computer to handle

Evaluation rule of a Postfix Expression states:

While reading the expression from left to right, push the element in the stack if it is an operand.
Pop the two operands from the stack, if the element is an operator and then evaluate it.
Push back the result of the evaluation. Repeat it till the end of the expression.

Algorithm

Create a stack to store operands (or values).
Scan the given expression and do the following for every scanned element.
1. If the element is a number, push it into the stack
2. If the element is an operator, pop operands for the operator from the stack.
  Evaluate the operator and push the result back to the stack
When the expression is ended, the number in the stack is the final answer

Let's see an example to better understand the algorithm:

Expression: 456*+

Program using C

//ITERATIVE BINARY SEARCH
#include<stdio.h>     
#include<conio.h>        
#include<string.h>      
#define MAX 50             
int stack[MAX];             
char post[MAX];             
int top=-1;                  
void pushstack(int tmp);       
void evaluate(char c);          
void main()
    {
       int i,l;
       //clrscr();
       printf("Insert a postfix notation :: ");
       gets(post);                    
       l=strlen(post);           
       for(i=0;i<l;i++)
       {
          if(post[i]>='0' && post[i]<='9')
          {
              pushstack(i);           
          }
          if(post[i]=='+' || post[i]=='-' || post[i]=='*' ||
          post[i]=='/' || post[i]=='^')       
          {
              evaluate(post[i]);  
          }
       }  
       printf("\n\nResult :: %d",stack[top]);
       getch();
    }
    
    void pushstack(int tmp)          //definition for push
    {
       top++;                             
       stack[top]=(int)(post[tmp]-48);    
    }
    
    void evaluate(char c)       //evaluate function
    {
       int a,b,ans;    
       a=stack[top];   
       stack[top]='\0';   
       top--;        
       b=stack[top];         
       stack[top]='\0';
       top--;           
       switch(c)  
       {
          case '+':      
              ans=b+a;
              break;
          case '-':          
              ans=b-a;
              break;
          case '*':            
              ans=b*a;
              break;
          case '/':       
              ans=b/a;
              break;
          case '^':
              ans=b^a;
              break;
          default:
              ans=0;
       }
       top++;          
       stack[top]=ans;    
    }