9 Applications of Stacks – I

T.V. Geetha

Welcome to the e-PG Pathshala Lecture Series on Data Structures. In this module we will talk about some of the applications of the Stack ADT.

Learning Objectives

The learning objectives of the introductory module are as follows:

•  To discuss some important applications of Stacks

•  To explain the handling of Algebraic expressions by stacks

•  To outline the conversion of infix to postfix using stacks

•  To explain the evaluation of postfix expression using stacks

9.1 Stacks

The stack is the simplest of all ADTs and understanding how a stack works is easy. The application of a stack, however, requires the creation of a design which allows the use of a stack and therein lies the challenge. We will look at reverse Polish, parsing, function calls, and other interesting applications.

Two types of applications of stacks are applications that require keeping track of the last state processed and the checking for balancing symbols. Recursion type of Applications that use stacks are implementation of recursive calls and applications where there is a need to keep track of the state we are in such as searching networks, traversing trees (keeping a track where we are).etc. One important group of examples that use stacks is the evaluation of algebraic expressions, checking balanced expressions and recognizing palindromes. Let us first look at the use of stacks to handle algebraic expressions.

9.2 Algebraic Expressions

Before we go into the details of how to use stacks, let us understand the three different types of expressions:

• Infix expressions – in this case an operator appears between its operands. This is the conventional way of writing algebraic expressions.

A simple example: a + b

• Prefix expressions – in this case the operator appears before its operands.

Example: + a b

• Postfix expressions – in this the operator appears after its operand

                      Example: a b +

More interesting examples of all types of expressions are given in  Figure 9.1.

Both prefix and postfix expressions do not need precedence rules, association rules or parentheses and have simple grammar expressions and straightforward recognition and evaluation algorithms. This is the reason why they are generally used during computation.

9.2.1 Reverse Polish (Postfix) Notation

As already discussed an infix expression can be converted by placing the operands first, followed by the operator rather than in between as in the case of infix expression.

Example:

Infix — (3 + 4) ×  5 – 6

Postfix– 3  4  + 5  × 6  –

Parsing reads left-to-right and performs operation on two operands

Example

3  4 +  5  × 6  –

7    5  × 6  –

35     6  –

29

This method of representing the expression is called reverse-Polish notation after the mathematician Jan Łukasiewicz (Figure 9.2) and the method forms the basis of the recursive stack used on all processors. Jan Łukasiewicz also made significant contributions to logic and other fields of computer science.

Now let us summarize the benefits of the reverse-Polish notation from the perspective of computing.

•  no ambiguity and no brackets are required
•  this is the same process used by a computer to perform computations:
•  operands must be loaded into registers before operations can be performed on them.
•  reverse-Polish can be processed using stacks

    Reverse-Polish notation is used with some programming languages, examples include postscript, pdf, and HP calculators. This processing is similar to the thought process required for writing assembly language code, where you cannot perform an operation until you have all of the operands loaded into registers.

9.2.2 Algebraic Expression Operations using Stacks

When the ADT stack is used to solve a problem, the use of the ADT’s operations should not depend on its implementation. In this section we discuss the following functions that use stacks namely that conversion of an infix expression to postfix form and evaluation of the postfix expression. Now let us look at each of these functions in detail.

9.2.2.1 Conversion of Infix to Postfix

Here are some facts to be considered when converting from infix expression to postfix expression. Operands always stay in the same order with respect to one another. An operator will move only “to the right” with respect to the operands. All parentheses are removed. In other words when we analyze the conversion process we discover that

•  Operands are in same order in infix and postfix

•  Operators occur later in the case of postfix

The basic strategy is to send operands straight to output, output higher precedence operators first before outputting lesser precedence operators. If operators have same precedence, send them to the output in left to right order. The stack is used to hold pending operators that are yet to be given as output.

Before we discuss the steps in detail let us give the table (Table 9.1) for the incoming priority (ICP) and in stack priority (ISP) of the different operators

   The steps and simulation of conversion of infix to postfix are shown in Figure 9.3 and Figure 9.4 respectively.

1. Figure 9.4(a) shows the initial state with Stack empty and the infix expression A*(B+C) –D/E yet to be processed. Then we scan the Infix expression from left to right for tokens. 

2. Figure 9.4 (b) shows the first token which is A given as output (as per step 2 of the algorithm)

3. Figure 9.4 (c) shows the pushing of the operator * into the stack according to step 4 (b).

4. Then the open parenthesis ( is pushed onto the stack as per step 3 of the algorithm.

5. Similarly the next token the operand B is given as output and the operator + is pushed onto the stack as shown in Figure 9.4 (e ) and 9.4 (f).

 6. Next token we see is a ) which means all entries in the stack up to and including open parenthesis is removed from the stack as shown in Figure 9.4 (g).

 7. However neither ( or ) form part of the output. As per step 4 (a) * is popped out and – is pushed onto the stack (Figure 9.4 (h)).

 8. Now the operand D is output (Figure 9.4(i)) and then the operator / is pushed into the stack ( Figure 9.4 (j)).

9. Figure 9.4 (k) shows E being  the next output token and

10. Finally operators left in the stack are popped out in the last in first out order (Figure 9.4 (l)).

As you can see an important part of the algorithm is the comparison of the precedence of the operators that are scanned and those that are in the stack. If the operators in the stack have higher precedence than the precedence of the incoming operator then they are outputted in reverse order to which they were pushed into the stack. Then the lower precedence operator is pushed into the stack. The other important part of the algorithm is the handling of parenthesis. When a right parenthesis is encountered, we pop all operators in the stack up to and including the matching left parenthesis. However neither the open or closing parenthesis is given as output. When this step is carried out when we say matching parenthesis we mean that the type of parenthesis should also match.

9.2.2.2  Evaluating Postfix Expression

    The next application of stack that we discuss is the evaluation of postfix expression.

The basic concept is as follows:

• Whenever an operand is encountered, push it onto the stack

• Whenever an operator is encountered, pop required number of arguments from operand stack and evaluate

• Push result back onto stack

The algorithm considers two cases – namely when the operator is binary or when it is unary where the number of operands popped out of the stack depends on the type of operator. Figure 9.6 shows a running example of the use of stack for evaluating a postfix expression. In the figure we have numbered the operators in order to explain the process. Please note that the stack is a single stack. The first column shown in the Figure 9.6 is the stack. However the second column is used to show the progress of the evaluation and does not form part of the stack.

The detail steps of the algorithm are given in Figure 9.5.

Algorithm for Evaluation 1. Empty the operand stack 2.while there are more tokens – Get the next token 3.If the first character of the token is an operand Push it onto the stack 4. else if the token is a binary operator a. Pop the right operand off the stack b. Pop the left operand off the stack c. Evaluate the operation d. Push the result onto the stack 5. else if the token is an unary operator a. Pop the top operand off the stack b. Evaluate the operation c. Push the result onto the stack 6. Pop the stack and return the result

Figure 9.5 Algorithm for Evaluation of Postfix Expression

Figure 9.6 A Running Example for Evaluating Postfix Expression

Figure 9.6(a) shows the initially empty stack and the input postfix expression with 8 operators (given below) which we wish to evaluate. The expression will be read one by one, left to right until the end of the expression is reached.

3  6 3  +  5  5 6  ×  +  8  ×  –  8  6  ×  + +

   1. As long as the tokens from left to right are operands (3,6,3) the elements are pushed onto the stack one by one ( Figure 9.6 (a) –(c)) – step 3 of the algorithm.

2. The next token is a binary + operator (1) (operators are identified by numbers in Figure 9.6) and therefore we pop the top two elements from the stack 3 & 6, perform the operation and push the result 9 back on to the stack (Figure 9.6 (d)) – step 4 of the algorithm.

3. The next three tokens are operands and they are pushed onto the stack (Figure 9.6 (e)–(g)) – step 3 of the algorithm.

4. Now the next token is a binary x operator (2) and therefore we pop the top two elements from the stack 6 & 5, perform the operation and push the result 30 back on to the stack (Figure 9.6 (h)) – step 4 of the algorithm

5. Now we again see a binary + operator (3) and therefore we pop the top two elements from the stack 30 & 5, perform the operation and push the result 35 back on to the stack (Figure 9.6 (i)) – step 4 of the algorithm.

6.The next token is the operand 8, which we push onto the stack (Figure 9.6 (j))  step 3 of the algorithm.

7. Now we again see a binary x operator (4) and therefore we pop the top two elements from the stack 8 & 35, perform the operation and push the result 280 back on to the stack (Figure 9.6 (k)) – step 4 of the algorithm.

8. Again we see a binary – operator (5) and therefore we pop the top two elements from the stack 280 & 9, perform the operation and push the result – 271 back on to the stack (Figure 9.6 (l)) – step 4 of the algorithm.

9. The next two tokens are the operands 8 & 6, which we push onto the stack (Figure 9.6 (m)) – step 3 of the algorithm.

10. The next token is a binary x operator (6) and therefore we pop the top two elements from the stack 8 & 6 perform the operation and push the result 48 back on to the stack (Figure 9.6 (n)) – step 4 of the algorithm.

11. The next token is a binary + operator (7) and therefore we pop the top two elements from the stack 48 & -271 perform the operation and push the result – 223 back onto the stack (Figure 9.6 (o)) – step 4 of the algorithm.

12. The next token is again a binary + operator (8) and therefore we pop the top two elements from the stack -223 & 3 perform the operation and push the result -220 back onto the stack (Figure 9.6 (p)) – step 4 of the algorithm.

13. Finally we see that all tokens have been handled, and the stack is empty, therefore the result -220 is on top of the stack (Figure 9.6 (q)) – step 6 of the algorithm.

In this example we have not considered an unary operator but in that case only one operand will be taken from the stack processed and pushed onto the stack. The algorithm finishes only when all tokens of the input have been handled and the stack is empty.

As you have seen in both these applications stacks are used to keep track of the elements that are to be processed. While in the first application the stack is used to store operators to keep track of precedence, in the second application the stack stores the operands to ensure the recent operands are used with the associated operator.

Summary

• Discussed some important applications of Stacks
• Explained the handling of Algebraic expressions by stacks
• Outlined the conversion of infix to postfix using stacks
• Discussed the evaluation of postfix expression using stacks