9.3 Stack Applications

The Stack ADT is required by a number of applications encountered in computer science. In this section, we examine two basic applications that traditionally are presented in a data structures course.

Balanced Delimiters

A number of applications use delimiters to group strings of text or simple data into subparts by marking the beginning and end of the group. Some common examples include mathematical expressions, programming languages, and the HTML markup language used by web browsers. There are typically strict rules as to how the delimiters can be used, which includes the requirement of the delimiters being paired and balanced. Parentheses can be used in mathematical expressions to group or override the order of precedence for various operations. To aide in reading complicated expressions, the writer may choose to use different types of symbol pairs, as illustrated here:

 {A + (B * C) - (D / [E + F])}

The delimiters must be used in pairs of corresponding types: {}, [], and (). They must also be positioned such that an opening delimiter within an outer pair must be closed within the same outer pair. For example, the following expression would be invalid since the pair of braces [] begin inside the pair of parentheses () but end outside.

 (A + [B * C)] - {D / E}

Another common use of the three types of braces as delimiters is in the C++ programming language. Consider the following code segment, which implements a function to compute and return the sum of integer values contained in an array:

 int sumList( int theList[], int size )
 {
   int sum = 0;
   int i = 0;
   while( i < size ) {
     sum += theList[ i ];
     i += 1;
   }
   return sum;
 }

As with the arithmetic expression, the delimiters must be paired and balanced. However, there are additional rules of the language that dictate the proper placement and use of the symbol pairs.

We can design and implement an algorithm that scans an input text file containing C++ source code and determines if the delimiters are properly paired. The algorithm will need to remember not only the most recent opening delimiter but also all of the preceding ones in order to match them with closing delimiters. In addition, the opening delimiters will need to be remembered in reverse order with the most recent one available first. The Stack ADT is a perfect structure for implementing such an algorithm.

Consider the C++ code segment from earlier. As the file is scanned, we can push each opening delimiter onto the stack. When a closing delimiter is encountered, we pop the opening delimiter from the stack and compare it to the closing delimiter. For properly paired delimiters, the two should match. Thus, if the top of the stack contains a left bracket [, then the next closing delimiter should be a right bracket ]. If the two delimiters match, we know they are properly paired and can continue processing the source code. But if they do not match, then we know the delimiters are not correct and we can stop processing the file. Table 9.3.1 shows the steps performed by our algorithm and the contents of the stack after each delimiter is encountered in our sample code segment.

So far, we have assumed the delimiters are balanced with an equal number of opening and closing delimiters occurring in the proper order. But what happens if the delimiters are not balanced and we encounter more opening or closing delimiters than the other? For example, suppose the programmer introduced a typographical error in the function header:

 int sumList( int theList)], int size )

Our algorithm will find the first set of parentheses correct. But what happens when the closing bracket ] is scanned? The result is illustrated in the top part of Table 9.3.2. You will notice the stack is empty since the left parenthesis was popped and matched with the preceding right parenthesis. Thus, unbalanced delimiters in which there are more closing delimiters than opening ones can be detected when trying to pop from the stack and we detect the stack is empty.

Delimiters can also be out of balance in the reverse case where there are more opening delimiters than closing ones. Consider another version of the function header, again containing a typographical error:

 int sumList( int (theList[], int size )

The result of applying our algorithm to this code fragment is illustrated in the bottom chart in Table 9.3.2. If this were the complete code segment, you can see we would end up with the stack not being empty since there are opening delimiters yet to be paired with closing ones. Thus, in order to have a complete algorithm, we must check for both of these errors.

A Python implementation for the validation algorithm is provided in the listing below. The function isValidSource accepts a file object, which we assume was previously opened and contains C++ source code. The file is scanned one line at a time and each line is scanned one character at a time to determine if it contains properly paired and balanced delimiters.

A stack is used to store the opening delimiters and either implementation can be used since the implementation is independent of the definition. Here, we have chosen to use the linked list version. As the file is scanned, we need only examine the characters that correspond to one of the three types of delimiter pairs. All other characters can be ignored. When an opening delimiter is encountered, we push it onto the stack. When a closing delimiter occurs, we first check to make sure the stack is not empty. If it is empty, then the delimiters are not properly paired and balanced and no further processing is needed. We terminate the function and return False. When the stack is not empty, the top item is popped and compared to the closing delimiter. The two delimiters do match corresponding opening and closing delimiters; we again terminate the function and return False. Finally, after the entire file is processed, the stack should be empty when the delimiters are properly paired and balanced. For the final test, we check to make sure the stack is empty and return either True or False, accordingly.