Data Structures: Lecture 9

Department: MCA
Semester    : II

Subject       : Data Structures through C++

Paper          : CCMCA 203 

Faculty        : Avinash Kumar

Syllabus covered in  this blog

STACK (Infix to Post-fix, Evaluation of Post-fix)

Infix to Postfix Conversion

X is an arithmetic expression written in infix notation.

This algorithm finds the equivalent post-fix expression Y.

  

1.    Scan X from left to right and repeat Step 2 to 5 for each element of X until the Stack is empty.

2.    If an operand is encountered, add it to Y.

3.    If a left parenthesis is encountered, push it onto Stack.

4.    If an operator is encountered ,then:

a.    Pop from Stack and add each operator which has the same precedence as or higher precedence than scanned operator to Y.

b.    Add the scanned operator to Stack.

5.    If a right parenthesis is encountered ,then:

a.    Pop each operator from the Stack until a left parenthesis is encountered and add it to Y.

b.    Remove the left Parenthesis

Let’s take an example to better understand the algorithm

Infix Expression: 

 

    A+ (B*C-(D/E^F)*G)*H

  where ^ is an exponential operator.

Evaluation of Post-fix expression

·         While reading the expression from left to right, push the element in the stack if it is an operand.

·         Pop the two operands from the stack, if the element is an operator and then evaluate it.

·         Push back the result of the evaluation. Repeat it till the end of the expression.

Algorithm

1.    Add ) to postfix expression.

2.    Read postfix expression Left to Right until ) encountered

3.    If operand is encountered, push it onto Stack

4.    If operator is encountered, Pop two elements

a.    A -> Top element

b.    B-> Next to Top element

c.    Evaluate B operator A

d.    Push B operator A onto Stack

Example

Expression:  456*+