## Evaluation of a postfix expression

Suppose p is an arithmetic expression written in postfix notation. The following algorithm, which user a STACK to held operands, evaluates P.

Algorithm

This algorithm finds the value of an arithmetic expression P written in postfix notation

1. Add a right parenthesis “)” at the end of p [This acts of a sentinel]
2. Scan p from left to right and repeat steps 3 and 4 for each element of p until the sentinel ”)” is encountered.
3. if an operand is encountered, put it on STACK
4. If an operator X is encountered, Then :
5. Remove the two top elements of STACK, where A is the top element and B is the next to top element
6. Evaluate BXA
7. Place the result of (b) back on STACK

[End of if structure]

[End of step2 loop]

1. Set value equal to the top element on STACK
2. Exit

Not that, when step 5 is executed, There should only one number on STACK.

### Example:

ABC+*DE/-

a=5, B=6,c=2,D=12,E=4

 Symbol scanned STACK A 5 B 5  6 C 5 6 2 + 5  8 * 40 D 40     12 E 40     12         4 / 40         3 - 37

### Postfix expression Program

Evaluation of a postfix expression

# include <stdio.h>

# include <conio.h>

# include <string.h>

char postfix;

int stack;

int Top=-1;

void get posttexpr()

{

printf(“Enter the postfix expression”);

case”-“ :   stack[Top] =B-A;

Top--;

break;

case”*“ :   stack[Top-1] =B*A;

Top--;

break;

case”/“ :   stack[Top-1] =B-A;

Top--;

break;

} /* switch      end */

}/*  else end */

}/*for end*/

}

void main()

{

clrscr();

getpastexpr();

calculate ();

display();

}

### output:

Enter the post fix expression :

ABC+*DE/-

Enter the value of A: 5

Enter the value of B: 6

Enter the value of c:2

Enter the value of D:1

Void display()

{

printf(“The calculated value is : %d\n”, stack[TOP]);

}

void calculate ()

{

int i, l, x;

l=strlen postfix;

for(i=0;i<=l;i++)

{

if(postfix(i)>=’A’  && postfix[i]<=’Z’)|| (postfix(i)>=’a’ && postfix[i]<=’Z’))

{

printf(“Enter the value of %c: ”, postfix,c[i]);

scanf(“%d”, &x);

Top=Top+1;

stack(Top] !=x;

}

else

{

int A=stack[Top];

int B=stack[Top-1];

switch postfix[i])

{

case :1

stack [Top-1]=B+A;

i--;