Stacks and the "Brackets" examples

Note, the material in these notes will not be covered in the exam

Stacks as mutable lists

In the list example we saw an immutable data structure which stored an ordered collection of data in such a way that you had access only to the first element (via the head method), and had to access the later ones indirectly (via the tail method). The tail method produced a new list, which had the same contents as all of the old list with the first element dropped. But calling the tail did not actually change the value that was stored in a list object.

In some cases this behaviour is exactly what we want. We want to be able to construct new list values without destroying the old ones we already have. In other cases, however, we may want a structure which is mutable, that is what it stores actually does change when methods are applied to it.

We can get this sort of behaviour using assignment. For example 

L=L.tail();
has the result of changing what the variable L refers to so that it refers to the list consisting of everything except the first element of what is originally referred to. So if L originally refers to the list [a,b,c,d], executing the statement L=L.tail(); makes it refer to the list [b,c,d]. Note, however, that 
L.tail();
does not have this effect. In fact L.tail(); on its own as a statement does not even make sense. The method tail() in the class List is defined as returning a List value, therefore to call this method but not do anything with the list it returns does not make sense (the list returned is not automatically assigned to variable L, for example). It only makes sense to have a method call on its own as a statement if the method has return type void and is designed to do something (maybe print something, or change a value in the object the method is attached) rather than return a value.

In a similar, way, we can change what a list variable refers to by 

L=L.cons(Obj);
which will have the effect of adding the value referred to by variable Obj to the front of the list referred to by L. For example, if Obj refers to the x and L refers to [a,b,c,d] the effect of executing L=L.cons(Obj) will be to change L to refer to [x,a,b,c,d]. But 
L.cons(Obj);
does not have the same effect, and in fact like L.tail() doesn't make sense as a statement on its own.

It is, however, inefficient to use assignment to create a mutable effect indirectly. If we are really sure we want something that is like a list but we are only ever going to change what it stores, never keep it, it is better to use a separate abstract data type which has destructive methods on it. The destructive form of a list is a stack (or maybe the constructive form of a stack is a list). The operations that may be done on a stack are: pop, push, top, and isempty. The operation pop is like tail on a list, but it changes the stack so that it loses its first element, whereas list tail gives a new list which is all but the first element of the old list. The operation push is a destructive form of list cons. It takes an object and changes the stack so that the object is put in front of the list of objects stored in the stack. The operation top is not actually destructive - it returns the object at the front of the list forming the stack without changing the stack. As the name "top" suggests, stacks are often thought of as storing their data vertically. It may help thinking about stacks to picture them as literally a stack like a stack of books, where you can look only at the top book, take the top book off the stack (the "pop" operation), or put another book on top of the stack making it the new top book (the "push" operation). Of course, you can also look to see if the place where your stack of books should be is empty (the "isempty" operation), and if so it would be possible to put a new book in the place, but a mistake to try and take a book off the empty state or determine what book was on the top of it.

A Java implementation of stacks

As before, we shall emphasise the abstract nature of stacks by defining what a stack is through a Java interface: 
interface Stack
{
 public boolean isempty();
 public Object top();
 public void pop();
 public void push(Object obj);
}
Note the methods pop and push have return type void. As this is only an interface, there is nothing to say how stacks are actually stored in the computer, or how the methods are implemented.

It is possible to implement stacks using linked lists, just like lists. Here is how it would be done: 

class LinkedStack implements Stack
{
 private Cell myList;

 LinkedStack()
 {
  myList=null;
 }

 private LinkedStack(Cell list)
 {
  myList=list;
 }

 public boolean isempty()
 {
  return myList==null;
 }

 public Object top()
 {
  return myList.first;
 }

 public void pop()
 {
  myList=myList.rest;
 }

 public void push(Object obj)
 {
  myList = new Cell(obj,myList);
 }

 public static Stack empty()
 {
  return new LinkedStack(null);
 }

 private static class Cell
 {
  Object first;
  Cell rest;

  Cell(Object h,Cell t)
  {
   first=h;
   rest=t;
  }
 }

}
An empty method is provided to create new empty stacks. It just calls the constructor for LinkedStack. It is static because a call empty() is not attached to any particular object, but rather to the class LinkedStack, as in: 
Stack s = LinkedStack.empty();

However, stacks are more commonly implemented using arrays. Since stacks are a destructive type, the disadvantage of using arrays we had with lists - the fact that it required a lot of copying - no longer applies. Here is an implementation using an array: 

   1  class ArrayStack implements Stack
   2  {
   3   public final int MAX = 20;
   4   private Object[] array;
   5   private int size;
   6
   7   private ArrayStack()
   8   {
   9    size=0;
  10    array = new Object[MAX];
  11   }
  12
  13   public boolean isempty()
  14   {
  15    return (size==0);
  16   }
  17
  18   public Object top()
  19   {
  20    return array[size-1];
  21   }
  22
  23   public void pop()
  24   {
  25    size--;
  26   }
  27
  28   public void push(Object obj)
  29   {
  30    array[size]=obj;
  31    size++;
  32   }
  33
  34   public static Stack empty()
  35   {
  36    return new ArrayStack();
  37   }
  38  }
When a new stack is created, a new array of the maximum size it is thought a stack might be is created. Here the maximum size is declared as a constant on line 3. It is made public so that code in other classes could check on what the maximum stack size is. The array is created in the constructor on line 10. Note the constructor is private, so that new stacks have to be created by the public static method empty on lines 34-37.

The pop and push methods are very easy to implement. push just puts its object argument into the next available free space in the array, and increases the sizepush just decreases size by one. There is no need even to overwrite the array cell it indexes - that will be done if the stack increases in size again when a new object is stored in that cell.

Note that a more robust implementation would throw an exception if an attempt were made to increase the size of the stack above the maximum set on line 3, and also throw an exception if an attempt were made to apply a top or pop method to an empty stack.

Use of stacks

Stacks are commonly used in computing. The reason is that they are a way of enabling us to deal with tasks that get interrupted by other tasks. If we stack a record of each task we're doing on some stack of tasks, when we finish some task we pop it off the task stack and the task now left at the top of the stack tells us where we should go back to. When a computer is running a program where method A calls method B, method B calls method C, and method C calls method D, a stack recording the mechanism in the computer which actually runs your code builds up a stack of method calls, so that when D finishes, it knows to go back to C (the record for C will also store the values of the variables in C at the point D was called and the point in C's execution where D was called, so that execution goes back to exactly where it was). If you use the web, you are probably familiar with the way clicking on links takes you further away from your home page, but you can go back one link at a time by clicking the "Back" button. This works because a stack of web pages links is kept, clicking on a link adds the next page you link into to the stack, clicking on "Back" pops the web page stack and puts you back to the new top (the existence of a "Forward" button, however, shows you that it is a data structure a little more complex than a stack - maybe as an exercise you could think about exactly what data structure would be needed to store a list of web sites manipulable with a "Forward" and "Backward" button).

A simple example of a program that uses a stack is a bracket-checker. Suppose a piece of text is read one character at a time. If an opening bracket is found, it is pushed onto a stack. If a closing bracket is found, the opening bracket at the top of the stack is popped off. If a closing bracket is found but the stack is empty, the text is incorrectly bracketed - the closing bracket must be a mistake as there was no opening bracket to match it. If the end of the text is reached, but the stack is not empty, the text is also incorrectly bracketed - there are no closing brackets to match the opening brackets put on the stack. The stack serves as a memory of how deep we are in the bracketing as we read the characters one by one. Here is a program which works this way: 

  1  import java.io.*;
  2
  3  class Brackets0
  4  {
  5
  6   public static void main(String [] args) throws IOException
  7   {
  8    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  9    Stack stack = ArrayStack.empty();
 10    String str;
 11    Character Ch;
 12    char ch;
 13    int n;
 14    System.out.print("Enter string : ");
 15    str=in.readLine();
 16    for(int i=0; i<str.length();i++)
 17       {
 18        ch=str.charAt(i);
 19        if(ch=='(')
 20           stack.push(new Character(ch)); 
 21        else if(ch==')') 
 22           if(stack.isempty())
 23              System.out.println("Extra ) at position "+(i+1));
 24           else
 25              stack.pop();
 26       }
 27    while(!stack.isempty())
 28       {
 29        System.out.println("Missing ) at end");
 30        stack.pop();
 31       }
 32   }
 33
 34  }
To show how stacks let us do things which would otherwise have to be done using recursion, here is a program which does the same as the above one, but uses recursion to do it: 
   1  import java.io.*;
   2
   3  class Brackets1
   4  {
   5
   6   public static void main(String [] args) throws IOException
   7   {
   8    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   9    String str;
  10    char ch;
  11    int n;
  12    System.out.print("Enter string : ");
  13    str=in.readLine();
  14    readTillEnd(0,str);
  15   }
  16
  17   private static void readTillEnd(int place,String str)
  18   {
  19    for(int i=place;i<str.length();i++)
  20      {
  21       char ch=str.charAt(i);
  22       if(ch=='(')
  23          i=readTillClose(i+1,str);
  24       else if(ch==')')
  25          System.out.println("Extra ) at position "+(i+1));       
  26      }
  27   }
  28
  29   private static int readTillClose(int place,String str)
  30   {
  31    for(int i=place;i<str.length();i++)
  32       {
  33        char ch=str.charAt(i);
  34        if(ch==')')
  35           return i;
  36        else if(ch=='(')
  37           i=readTillClose(i+1,str);
  38       }
  39    System.out.println("Missing ) at end");
  40    return str.length();
  41   }
  42
  43  }
In the recursive program, a call of the method readTillClose is made every time an opening bracket is met, this method returns the position of the matching closing bracket in the string. So exiting the method readTillClose when a closing bracket is found (this exiting is actually done on line 35) is the equivalent of popping the stack when a closing bracket is found. if the method readTillClose actually gets to the end of its for loop without returning a value (and hence breaking the loop) on line 35, it must be because it has got right to the end of the string without finding a closing bracket, so it prints an error message.

When we are only using one sort of bracket (rounded ones), the above approaches are unnecessarily complex. We could just use an integer to count how deep we are in brackets. The need for a stack comes when we start dealing with the three different sorts of brackets found on a conventional computer keyboard - rounded brackets, square brackets and curly brackets. Now the stack has the useful property of remembering the last unmatched bracket read. When we encounter an opening bracket, we put it on the stack. When we encounter a closing bracket we check the top of the stack. If the top of the stack matches the closing bracket, we have found the match and we pop the stack. Otherwise, since the last unmatched bracket does not match the closing bracket found, there is an error in bracketing. Here is the code: 

   1   import java.io.*;
   2
   3   class Brackets2
   4   {
   5
   6    public static void main(String [] args) throws IOException
   8    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   9    Stack stack = ArrayStack.empty();
  10    String str;
  11    Character Ch;
  12    char ch;
  13    int n;
  14    System.out.print("Enter string : ");
  15    str=in.readLine();
  16    for(int i=0; i<str.length();i++)
  17       {
  18        ch=str.charAt(i);
  19        switch(ch)
  20           {
  21            case '(': case '[': case '{': 
  22              stack.push(new Character(ch)); 
  23              break;
  24            case ')': case ']': case '}':
  25              if(stack.isempty())
  26                 System.out.println("Extra "+ch+" at position "+(i+1));
  27              else
  28                 {
  29                  Ch=(Character)stack.top();
  30                  if(ch==match(Ch.charValue()))
  31                     stack.pop();
  32                  else
  33                     System.out.println("Extra "+ch+" at position "+(i+1));
  34                 }
  35           }
  36       }
  37    while(!stack.isempty())
  38       {
  39        Ch=(Character)stack.top();
  40        System.out.println("Missing "+match(Ch.charValue())+" at end");
  41        stack.pop();
  42       }
  43   }
  44
  45   private static char match(char ch)
  46   {
  47    switch(ch)
  48       {
  49        case '(': return ')';
  50        case '[': return ']';
  51        case '{': return '}';
  52       }
  53    return ch;
  54   }
  55
  56  }
Note that since we have a general class Stack which stores stacks of Objects, we have to put not chars in our stack, but the objects of the wrapper class Character. On line 22, the char from the input string is converted to the equivalent Character as it is pushed on the stack. The method top() returns a value of type Object, so it is necessary to use type conversion to convert it back to the Character object that was pushed on the stack. This type conversion is done where top is used, on lines 29 and 39.

Again, a program which behaves exactly the same can be written using recursion rather than stacks. Here a separate method is given for each type of opening bracket, which returns the position of the matching closing bracket, printing an error message if it finds a closing bracket of the wrong sort or reaches the end of the string without finding a matching closing bracket. 

   1  import java.io.*;
   2  
   3  class Brackets3
   4  {
   5  
   6   public static void main(String [] args) throws IOException
   7   {
   8    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   9    String str;
  10    char ch;
  11    int n;
  12    System.out.print("Enter string : ");
  13    str=in.readLine();
  14    readTillEnd(0,str);
  15   }
  16  
  17   private static void readTillEnd(int place,String str)
  18   {
  19    for(int i=place;i<str.length();i++)
  20      {
  21       char ch=str.charAt(i);
  22       switch(ch)
  23          {
  24           case '(': i=readTillCloseRound(i+1,str); break;
  25           case ')': System.out.println("Extra ) at position "+(i+1)); break;   
  26           case '[': i=readTillCloseSquare(i+1,str); break;
  27           case ']': System.out.println("Extra ] at position "+(i+1)); break;
  28           case '{': i=readTillCloseCurly(i+1,str); break;
  29           case '}': System.out.println("Extra } at position "+(i+1)); break;
  30          }
  31      }
  32   }
  33  
  34   private static int readTillCloseRound(int place,String str)
  35   {
  36    for(int i=place;i<str.length();i++)
  37       {
  38        char ch=str.charAt(i);
  39        switch(ch)
  40          {
  41           case '(': i=readTillCloseRound(i+1,str); break;
  42           case ')': return i;
  43           case '[': i=readTillCloseSquare(i+1,str); break;
  44           case ']': System.out.println("Extra ] at position "+(i+1)); break;
  45           case '{': i=readTillCloseCurly(i+1,str); break;
  46           case '}': System.out.println("Extra } at position "+(i+1)); break;
  47          }
  48  
  49       }
  50    System.out.println("Missing ) at end");
  51    return str.length();
  52   }
  53   
  54   private static int readTillCloseSquare(int place,String str)
  55   {
  56    for(int i=place;i<str.length();i++)
  57       {
  58        char ch=str.charAt(i);
  59        switch(ch)
  60          {
  61           case '(': i=readTillCloseRound(i+1,str); break;
  62           case ')': System.out.println("Extra ) at position "+(i+1)); break;
  63           case '[': i=readTillCloseSquare(i+1,str); break;
  64           case ']': return i;
  65           case '{': i=readTillCloseCurly(i+1,str); break;
  66           case '}': System.out.println("Extra } at position "+(i+1)); break;
  67          }
  68  
  69       }
  70    System.out.println("Missing ] at end");
  71    return str.length();
  72   }
  73  
  74   private static int readTillCloseCurly(int place,String str)
  75   {
  76    for(int i=place;i<str.length();i++)
  77       {
  78        char ch=str.charAt(i);
  79        switch(ch)
  80          {
  81           case '(': i=readTillCloseRound(i+1,str); break;
  82           case ')': System.out.println("Extra ) at position "+(i+1)); break;
  83           case '[': i=readTillCloseSquare(i+1,str); break;
  84           case ']': System.out.println("Extra } at position "+(i+1)); break;
  85           case '{': i=readTillCloseCurly(i+1,str); break;
  86           case '}': return i;
  87          }
  88  
  89       }
  90    System.out.println("Missing } at end");
  91    return str.length();
  92   }
  93  
  94  }

Misleading error messages

When you compile a program, you will often find the error messages the compiler gives do not quite coincide with the error you have made. Sometimes the compiler points out where the error is, but seems to be making an assumption that the error is a different one than it the one you actually made.

The simple bracket-matching example shows how this can happen. The bracket matching program given above works on the assumption that if a closing bracket of the wrong sort is found, it must just be an extra character that was not meant to be there, so it is ignored. So it will perform fine on, say: 

[f(a), f(c})]
However, what if the string entered is, say: 
[f(a}, f(c)]
Here the error is not that an extra } has been put in, but rather that a } has been put in mistakenly for a ). The error messages are not particularly helpful. The program will go right to the end of the string looking for a ) to match the first (. Not finding one, it will report one missing, but since it never got round to closing the first ) and getting back to finding a match for [, will also report a ] missing.

An alternative approach deals differently with the case of finding a closing bracket which is not of the sort that matches that at the top of the stack. Instead of ignoring the wrong closing bracket, it assumes it was a mistake for the right one, so prints an error message saying so and pops the stack anyway. Here is the code for the alternative approach: 

   1  import java.io.*;
   2  
   3  class Brackets4
   4  {
   5  
   6   public static void main(String [] args) throws IOException
   7   {
   8    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   9    Stack stack = ArrayStack.empty();
  10    String str;
  11    Character Ch;
  12    char ch,ch1;
  13    int n;
  14    System.out.print("Enter string : ");
  15    str=in.readLine();
  16    for(int i=0; i<str.length();i++)
  17       {
  18        ch=str.charAt(i);
  19        switch(ch)
  20           {
  21            case '(': case '[': case '{': 
  22              stack.push(new Character(ch)); 
  23              break;
  24            case ')': case ']': case '}':
  25              if(stack.isempty())
  26                 System.out.println("Extra "+ch+" at position "+(i+1));
  27              else
  28                 {
  29                  Ch=(Character)stack.top();
  30                  stack.pop();
  31                  ch1=match(Ch.charValue());
  32                  if(ch!=ch1)
  33                      {
  34                       System.out.print("Expected "+ch1);
  35                       System.out.print(" found "+ch);
  36                       System.out.println(" at position "+(i+1));
  37                      }
  38                 }
  39           }
  40       }
  41    while(!stack.isempty())
  42       {
  43        Ch=(Character)stack.top();
  44        System.out.println("Missing "+match(Ch.charValue())+" at end");
  45        stack.pop();
  46       }
  47   }
  48  
  49   private static char match(char ch)
  50   {
  51    switch(ch)
  52       {
  53        case '(': return ')';
  54        case '[': return ']';
  55        case '{': return '}';
  56       }
  57    return ch;
  58   }
  59  
  60  }
As you can see, this version differs only from the previous version using a stack at the point where it deals with encountering a closing bracket (lines 28-38 in Brackets4 and lines 38-34 in Brackets2). If you compile this version, you will see this time it gives a sensible error message on the string [f(a}, f(c)], but not a sensible one on [f(a), f(c})]. So there isn't a way of getting every error correctly reported - the error detecting mechanism has to guess what the error is, and may get it wrong. In fact, even with our simple example bracket-matching example, we can have yet another assumption which may be correct in some cases, but incorrect in others. The version below copes badly with both the two previous example of badly-bracketed strings, but copes well with this one: 
[f(a), f(c]
while the previous versions both cope badly with it: 
   1  import java.io.*;
   2  
   3  class Brackets5
   4  {
   5  
   6   public static void main(String [] args) throws IOException
   7   {
   8    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   9    Stack stack = new LinkedStack();
  10    String str;
  11    Character Ch;
  12    char ch,ch1;
  13    int n;
  14    System.out.print("Enter string : ");
  15    str=in.readLine();
  16    for(int i=0; i<str.length();i++)
  17       {
  18        ch=str.charAt(i);
  19        switch(ch)
  20           {
  21            case '(': case '[': case '{': 
  22              stack.push(new Character(ch)); 
  23              break;
  24            case ')': case ']': case '}':
  25              while(!stack.isempty())
  26                 {
  27                  Ch=(Character)stack.top();
  28                  stack.pop();
  29                  ch1=match(Ch.charValue());
  30                  if(ch==ch1)
  31                     break;
  32                  else
  33                     System.out.println("Missing "+ch1+" at position "+(i+ 1));
  34                 }
  35              System.out.println("Extra "+ch+" at position "+(i+1));
  36           }
  37       }
  38    while(!stack.isempty())
  39       {
  40        Ch=(Character)stack.top();
  41        System.out.println("Missing "+match(Ch.charValue())+" at end");
  42        stack.pop();
  43       }
  44   }
  45  
  46   private static char match(char ch)
  47   {
  48    switch(ch)
  49       {
  50        case '(': return ')';
  51        case '[': return ']';
  52        case '{': return '}';
  53       }
  54    return ch;
  55   }
  56  
  57 }
This version works on the assumption that if a closing bracket is found which does not match the one at the top of the stack, it must be because the one to match the one at the top of the stack has been missed out. It therefore keeps reporting a missing closing bracket of the type required to match the top of the stack, and then pops the stack until it finds an opening bracket on the stack which matches the closing bracket it has found. If the stack becomes empty without a match being found, it reports the closing bracket as an extra character (done on line 35).

Note, all the programs in this web page may be found in the directory: 

/import/teaching/BSc/1st/ItP/stacks
Matthew Huntbach

These notes were produced as part of the course Introduction to Programming as it was given in the Department of Computer Science at Queen Mary, University of London during the academic years 1998-2001.

Last modified: 11 Feb 1999