Blog

Postfix expression in Data Structures

21 September, 2018

Related Blogs

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
  1. A
5
  1. B
5  6
  1. C
5 6 2
  1. +
5  8
  1. *
40
  1. D
40     12
  1. E
40     12         4
  1. /
40         3
  1. -
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--;