  Blog

## Postfix expression in Data Structures

21 September, 2018

## 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--;