Home » Evaluating Postfix Expression Using Stack

# Evaluating Postfix Expression Using Stack

The postfix expression is a notation for expression used in computers where operator comes after the operands in the expression. It is also known as `reverse polish notation.` In this example, you will learn evaluating postfix expression using stack.

Suppose` A` and `B` are two operand and` '+'` is the operator. We humans write the infix expression which is` A + B.` However, the computer must convert the infix expression into postfix so that it can compute the expression.

It is the way computer look at expression.

## Algorithm To Evaluate Postfix Expression

Let’s call this postfix expression as P and the stack as S. To evaluate P, the program must use following algorithm.

1. Add a right parenthesis ‘)’ at the end of expression P . It marks the end of the expression.
2. Start scanning the expression P until ‘)’ is reached.
3. If an operand is found, push that to stack S.
4. If an operator `op` is found.
1. Remove top two element of stack S, where A is topmost, and second to top is B.
2. Evaluate `B op A`.
3. Push the result back to stack S.
5. Keep repeating step 3 and 4 until the end ‘)’ has reached.
6. The final result is top of the stack.
7. Stop the program.

## Program Code:

``````/* Program to evaluate postfix
expression and output result */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <conio.h>
#define MAXSIZE 100

/* Stack array and top variables in structure */
struct stack
{
int stack[];
int Top;
};

/* type definition for user-defined
data types */
typedef struct stack NODE;

/* This function will add an element
to Top of the stack */
void push(NODE *pu, int item)
{

if (pu->Top== MAXSIZE-1)
{
printf("\nThe Stack is Full");
getch();
}
else
{

pu->stack[++pu->Top] = item;
}
}
/* This function will delete an element
from the top of the stack */
int pop(NODE *po)
{
int item;
/* If the Top pointer points to
NULL then there is not element to
delete */
if(po->Top ==-1)
{
printf("\nThe Stack is Empty");
}
/*Otherwise delete the top of the stack
and decrement the top pointer */
else
{
item=po->stack[po->Top--];

}
return item;
}
/*Postfix evaluation*/
int Postfix_Eval(char postfix[])
{
int a,b,temp,len;
/* declaring a pointer variabe
of type structure NODE */
NODE *ps;
int i;
/* Initializing the Top pointer to NULL*/
ps->Top=-1;
push(ps,'#');
/* Find length of the string */
len = strlen(postfix);

for(i=0;i<len;i++)
{
if(postfix[i]<='9'&&postfix[i]>='0')
{
/*Operand is pushed to stack*/
push(ps,(postfix[i]-48));
}
else
{
/* Pop the two top operands for
operation */
a = pop(ps);
b = pop(ps);

switch(postfix[i])
{
case '+':
temp=b+a;
break;
case '-':
temp=b-a;
break;
case '*':
temp=b*a;
break;
case '/':
temp=b/a;
break;
case '%':
temp=b%a;
break;
case '^':
temp=pow(b,a);

}/* End of switch*/
push(ps,temp);
}

}
return(pop(ps));
}

int main() {

char choice,postfix[MAXSIZE];
do
{
clrscr();
printf("\n\nEnter the Postfix expression=");
fflush(stdin);
gets(postfix);
printf("\n\nThe Postfix Evaluation is = %d",Postfix_Eval(postfix));
printf("\n\nDo you want to continue(Y/y)=");
fflush(stdin);
scanf("%c",&choice);
}while(choice=='Y'||choice=='y');
return 0;
}``````

## Output

``````Enter the Postfix expression=46+9*

The Postfix Evaluation is = 90
Do you want to continue(Y/y)=_``````