Postfix expression in Data Structures

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]

5. Set value equal to the top element on STACK
6. 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[20]; int stack[20]; 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--;