This lab exercise consists of two problems similar to the problems you will see on the midterm exam coming up on Friday. These problems are a little more difficult than the exam problems, but are very similar in character. Both problems have solutions attached that you can compare your work to.

Creating a class

A stack is a structure that stores a list of elements in a vertical stack. New elements can be added to the top of the stack via the stack's push() method, and elements can be removed from the stack via a pop() method. Here is the outline of a Java class that implements a stack structure designed to hold characters.

public class CharacterStack {
  private char[] elements;
  private int topPosition;

  public CharacterStack(){} // Create a new, empty stack
  public boolean isEmpty() {} // Return true if the stack is empty
  public void push(char ch) {} // Push ch on the stack
  public char top() {} // Return the character at the top of the stack
  public void pop() {} // Remove the top element from the stack
}

The stack is implemented internally as an array of chars. The elements array typically has more room than is needed to store the chars on the stack: the topPosition variable indicates which position in the elements array represents the last item stored on the stack.

The stack typically starts with a relatively small elements array (8 is a good size to start with). When new items are pushed on the stack, we attempt to store them at index topPosition+1 in the elements array and then increment topPosition by 1. To pop items off the stack, we simply decrement topPosition by 1. When topPosition is about to run past the end of the elements array, we replace the array with a new array twice as large as the original and copy the old characters over to it before proceeding with the push.

Fill in the methods for this class.

Solution

Using the class

Here is a problem that we can solve with a stack of characters. Consider an arithmetic expression that uses parentheses. To be properly formed, the pairs of left and right parentheses have to balance in the appropriate way. For example, the expression

((a + b)*(c + d) - (e + f))

is properly balanced, while the expression

((a + b)*(c + d)) - (e + f))

has an unbalanced pair of parentheses.

Here is an algorithm that uses a character stack to determine whether or not an expression has its parentheses properly balanced.

• Create an empty character stack.
• Read the expression into a String.
• Scan the String from left to right. For each character you encounter, do the following:
• If you encounter a '(' character, push it on the stack.
• If you encounter a ')' character and the stack is not empty, pop the top '(' off the stack.
• If you encounter a ')' character and the stack is empty, stop and print an error message.
• If you reach the end of the String and the stack is not empty, print an error message. Otherwise, print a message saying that the parentheses are properly balanced.

Use the CharacterStack class you just created to implement this algorithm.

Solution