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
- Add a right parenthesis “)” at the end of p [This acts of a sentinel]
- Scan p from left to right and repeat steps 3 and 4 for each element of p until the sentinel ”)” is encountered.
- if an operand is encountered, put it on STACK
- If an operator X is encountered, Then :
- Remove the two top elements of STACK, where A is the top element and B is the next to top element
- Evaluate BXA
- Place the result of (b) back on STACK
[End of if structure]
[End of step2 loop]
- Set value equal to the top element on STACK
- 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--;
