Data Structures and Algorithms - Old Questions

3. Explain the algorithms for infix to postfix conversion and evaluation of postfix expression. Trace the algorithms with suitable example.

Algorithm to convert infix to postfix expression

1. Scan the infix string from left to right.

2. Initialize an empty stack.

3. If the scanned character is an operand, add it to postfix sting

4. If the scanned character is an operator, PUSH the character to stack.

5. If the top operator in stack has equal or higher precedence than scanned operator then POP the operator present in stack and add it to postfix string else PUSH the scanned character to stack.

6. If the scanned character is a left parenthesis ‘(‘, PUSH it to stack.

7. If the scanned character is a right parenthesis ‘)’, POP and add to postfix string from stack until an ‘(‘ is encountered. Ignore both '(' and ')'.

8. Repeat step 3-7 till all the characters are scanned.

9. After all character are scanned POP the characters and add to postfix string from the stack until it is not empty.

Example:

Infix expression: A*B+C

Postfix expression: AB*C+

Algorithm for evaluation of postfix expression

1. Create a stack to store operands.

2.  Scan the given expression from left to right.

3. a) If the scanned character is an operand, push it into the stack.

      b) If the scanned character is an operator, POP 2 operands from stack and perform operation and PUSH the result back to the stack.

4. Repeat step 3 till all the characters are scanned.

5. When the expression is ended, the number in the stack is the final result.

Example:

Let the given expression be “456*+“. We scan all elements one by one.