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]

  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 scannedSTACK

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