Evaluation Of PostFix Expression - C/C++




Infix Expression : Any expression in the standard form like "2*3-4/5" is an Infix(Inorder) expression.
Postfix Expression : The Postfix(Postorder) form of the above expression is "23*45/-".

Postfix Evaluation :

  • In normal algebra we use the infix notation like a+b*c. The corresponding postfix notation is abc*+. The algorithm for the conversion is as follows : 
  • Scan the Postfix string from left to right. 
  • Initialise an empty stack. 
  • 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. 
  • 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. Repeat this step till all the characters are scanned. 
  • After all characters are scanned, we will have only one element in the stack. Return topStack. 

Example of Postfix Evaluation :


Let us see how the above algorithm will be imlemented using an example.

Postfix String : 123*+4-

Initially the Stack is empty. Now, the first three characters scanned are 1,2 and 3, which are operands. Thus they will be pushed into the stack in that order.



Stack



Expression

Next character scanned is "*", which is an operator. Thus, we pop the top two elements from the stack and perform the "*" operation with the two operands. The second operand will be the first element that is popped.



Stack



Expression

The value of the expression(2*3) that has been evaluated(6) is pushed into the stack.



Stack



Expression

Next character scanned is "+", which is an operator. Thus, we pop the top two elements from the stack and perform the "+" operation with the two operands. The second operand will be the first element that is popped.



Stack



Expression

The value of the expression(1+6) that has been evaluated(7) is pushed into the stack.



Stack



Expression

Next character scanned is "4", which is added to the stack.



Stack



Expression

Next character scanned is "-", which is an operator. Thus, we pop the top two elements from the stack and perform the "-" operation with the two operands. The second operand will be the first element that is popped.



Stack



Expression

The value of the expression(7-4) that has been evaluated(3) is pushed into the stack.



Stack



Expression

Now, since all the characters are scanned, the remaining element in the stack (there will be only one element in the stack) will be returned.

End result :
Postfix String : 123*+4-
Result : 3


Program for Evaluation of Postfix Expression :



#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 calculator(char c);
 
void main()
{
 int i;
 clrscr();
 printf("Insert a postfix notation :: ");
 gets(post);
 for (i = 0; i < strlen(post); i++)
 {
  if (post[i] >= '0' && post[i] <= '9')
  {
   pushstack(i);
  }
  if (post[i] == '+' || post[i] == '-' || post[i] == '*' || post[i] == '/' || post[i] == '^')
  {
   calculator(post[i]);
  }
 }
 printf("\n\nResult :: %d", stack[top]);
 getch();
}
 
void pushstack(int tmp)
{
 top++;
 stack[top] = (int)(post[tmp] - 48);
}
 
void calculator(char c)
{
 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;
}



Check out Infix To Postfix Conversion Program here

8 comments

Thanks for your post Jayesh. I was trying to take the code you have for the infix conversion and add the evaluation to the same code so it did it all in one step.

Reply

I like the output from : http://datastructuresprogramming.blogspot.com/2011/06/c-program-for-evaluating-postfix.html

and the code looked manageable. Problem I'm having is taking the string in post and assigning it to the char str[] instead of taking the input from the keyboard (since the conversion already exists.

Reply

Thanks buddy for your response.
I have already implemented the Evalution of Infix Notation and posted on the blog.
You can use the code from there and use it.
I have created separate programs for easier understanding :)

Reply

Really good and clear explanation
Please visit http://codingloverlavi.blogspot.in/2015/01/expression-evaluation-using-stacks.html for my implementation

Reply
This comment has been removed by the author.
This comment has been removed by the author.

#include
#include
using namespace std;
int stack[10];
string str;
int top = -1;

void push(int x);

void calculate(char c);

int main(){
int i;

cout<<"Insert a postfix expression "<= '0' && str[i] <= '9'){
push(i);
}
if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/' || str[i] == '^')
{
calculate(str[i]);
}
}
cout<<"Result="<<stack[top]<<endl;

}

void push(int x)
{
top++;
stack[top]=x;
}

void calculate(char c)
{
int a,b, ans;
a = stack[top];
top--;
b = stack[top];
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;
}

Reply

Post a Comment