Stack Application: Evaluation of Infix, Postfix and Prefix Expressions

Stack Applications

In computer science, stack is used for the following purposes:

1. Stack Frames:

When any procedure or function is called, a number of words—the stack frame—is pushed into a program stack. When procedure of function returns, this frame of data is popped off the stack.As a function calls another function, first its arguments, then the return address and finally space for local variables are pushed onto the stack.The use of stack frames in programming makes possible for recursion in a program.

2. Reversing a String:

Since the last inserted character is the one ot be popped off first in a stack, this technique is used for reversing string values.

3. Calculation of Postfix Expression:

An expression is defined as a number of operands or data items combined using several operators.

Let us consider A and B as two operands and + as the operator.

The following three ways of notation for an expression are used:

1. Infix: A + B

- Most common in general mathematics

- Operator is written between the operands

2. Prefix: +AB

- Operator is written before operands

- Also called “Polish” Notation

3. Postfix: AB+

- An operator is written after the operands.

- Also called “Suffix” or “Reverse Polish” Notation

Why Postfix ?

Postfix has universally accepted notation for designing ALU, it is the most suitable for the computer to calculate any expression. Once the postfix expression is prepared, the evaluation doesn’t need any rules (like an order of precedence, BODMAS rule, etc.) to be applied or remembered.

Operator Precedence Order:

1. Exponentiation ^

2. Multiplication/Division *, /

3. Addition/Subtraction +, -

As given expression is parenthesized from left to right, the operands having higher precedence operators are parenthesized first. If the same order operators are encountered multiple times, then the one in the leftmost is parenthesized first, except in the case of exponentiation, in which parenthesizing is done from right to left.

Eg:

• A + B + C = (A + B) + C
• A ^ B ^ C = A ^ (B ^ C)

A * B + C/D is converted to postfix as:

(A * B) + C/D = (AB*) + (C/D) = (AB*) + (CD/) = AB*CD/+

Some more examples:

• A * B + C => AB*C+
• (A+B)*(C-D) => AB+CD-*
• A+B*C+(D*E+F) => ABC*+DE*F+G*+
• A+[(B+C)+(D+E)*F)]/G => ABC+DE+F*+G/+

Algorithm for converting Infix Expression into Postfix Expression

POSTFIX(Q,P)

Q => Arithmetic expression written in infix notation

P => Equivalent expression in postfix notation

1. Add “(“ at the beginning and “)” at the end of Q.

2. Scan Q from left to right and repeat step 3 to 6 until all symbols are scanned.

3. If an operand is encountered, add it to P.

4. If a left parenthesis is encountered, push it onto the stack.

5. If an operator ‘&’ is encountered, check TOS:

- If TOS contains left parenthesis or an operator with lower precedence, push “&” into the stack.

- If TOS contains an operator with the same or higher precedence than &, repeatedly POP from

the stack the operators and adds to P, push “&” onto the stack.

6. If right parenthesis is encountered:

- Repeatedly POP from the stack and add it to P until each operator until the left parenthesis is

encountered on the stack.

- Restore the left parenthesis.

Example: Convert the following infix expression into postfix expression showing stack status at each step:

Q = A + B * C – D / E

Solution:

References:

1. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structuresusing C and C++”

2. R. L. Kruse, B. P. Leung, C. L. Tondo, “Data Structure and Program designin C”

3. G. Brassard and P. Bratley, “Fundamentals of Algorithms”