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.

- Add a right parenthesis ‘)’ at the end of expression P . It marks the end of the expression.
- Start scanning the expression P until ‘)’ is reached.
- If an operand is found, push that to stack S.
- If an operator
`op`

is found.- Remove top two element of stack S, where A is topmost, and second to top is B.
- Evaluate
`B op A`

. - Push the result back to stack S.

- Keep repeating step 3 and 4 until the end ‘)’ has reached.
- The final result is top of the stack.
- 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)=_
```