Expression tree is a binary tree in which each internal node corresponds to operator and each leaf node corresponds to operand so for example expression tree for 3 + ((5+9).2) would be: Inorder traversal of expression tree produces infix version of given postfix expression (same with preorder traversal it gives prefix expression)Evaluating the.
Here you will get algorithm and program for evolution of postfix expression in C.
In postfix or reverse polish notation, every operator follows all of its operands.
For example: 5 3 2 * +
Also Read: Infix to Postfix Conversion in C [Program and Algorithm]
Algorithm for Evaluation of Postfix Expression
Create an empty stack and start scanning the postfix expression from left to right.
- If the element is an operand, push it into the stack.
- If the element is an operator O, pop twice and get A and B respectively. Calculate BOA and push it back to the stack.
- When the expression is ended, the value in the stack is the final answer.
Evaluation of a postfix expression using a stack is explained in below example:
Program for Evaluation of Postfix Expression in C
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 | //Assumption -- primary operators '-,+,*,/,%' operand -- a single digit #include<stdio.h> #define MAX 20 typedefstructstack intdata[MAX]; }stack; voidinit(stack*); intfull(stack*); voidpush(stack*,int); { charx; init(&s); printf('Enter the expression(eg: 59+3*)nSingle digit operand and operators only:'); while((x=getchar())!='n') if(isdigit(x)) push(&s,x-48);//x-48 for removing the effect of ASCII { op1=pop(&s); push(&s,val); } val=pop(&s); } intevaluate(charx,intop1,intop2) if(x'+') if(x'-') if(x'*') if(x'/') if(x'%') } voidinit(stack*s) s->top=-1; { return(1); return(0); { return(1); return(0); { s->data[s->top]=x; { x=s->data[s->top]; } |
Output
Enter the expression(eg: 59+3*)
Single digit operand and operators only:74+5-
Single digit operand and operators only:74+5-
Value of expression=6
Image Credit:http://cis.stvincent.edu/html/tutorials/swd/stacks/stacks.html