Sunday, 1 October 2017

Write the algorithm for evaluation of a postfix expression.

The postfix expression may be evaluated by making a left-to-right scan, stacking operands and evaluating operators using the correct number from the stack as operands and again placing the result onto the stack. This evaluation process is much simpler than attempting a direct evaluation from the infix notation. This process is continues till the stack is not empty. The following algorithm uses a stack data structure to calculate postfix expression. Suppose EXP is an arithmetic expression which is further written in postfix notation. The algorithm written below, which uses a STACK data structure to hold operands, evaluates EXP.  This algorithm finds the  RESULT of an arithmetic expression EXP written in postfix notation.

Steps which we follow when evaluating postfix expression.

1. First of all add a right parenthesis ‘)’ at the end of EXP in hand.
2. Scan EXP from left-to-right and repeat steps 3 & 4 for each data element in EXP until the ‘)’ is found in it.
3. If an operand is found in the EXP, then:
         a. Push that operand into STACK data structure.
4. If any operator Ø  ( like +, -, *, %, ?,^ etc) is found during EXP scan, then:
a. Remove the first two top elements from the STACK                data structure.
b. Evaluate RESULT = X Ø Y, where X is the top element and Y is next-to top element in the STACK.
c. Push the result of (b) back onto the STACK data structure.
5. Set RESULT equal to the top element of STACK data structure.
6. Exit.

Mukesh Rajput

No comments:

Post a Comment

Mukesh Rajput