Lab 12: Stacks, Queues and Trees

Task 0: Prepare for lab

Download the following zip file: lab12.zip

Unzip this archive, and you should find a folder named lab12, and within it the files you will need for this lab.

Task 1: Use a stack to check for balanced delimiters

In lecture, we discussed how you could use a stack to check if the delimiters in an expression (i.e., the parentheses, brackets, and curly braces) are properly balanced. In this task, you will complete code that does this.

1. We’ve given you some starter code in Lab12Task1.java. However, it includes a syntax error. Compile the file to see the error.

2. The error stems from the fact that generic classes in Java require you to use reference types – types that represent objects. Therefore, we can’t use a primitive type like char when we declare or create an instance of a generic collection.

   Instead, Java provides a “wrapper class” for each primitive type that allows us to treat primitive values as if they were objects. In the case of char, the corresponding wrapper class is called Character.

   Change the code so that it uses this wrapper class when declaring and creating the stack that we’re using in this task. Feel free to ask for help as needed.

3. We have given you three helper methods: isLeftDelim(), isRightDelim(), and matches().

   Review these methods, reading the comments that accompany them and examining how they work.

   At the moment, they each support two types of delimiters but not the third. Extend each method so that it supports all three types of delimiters. Here are some test cases:

   System.out.println(Lab12Task1.isLeftDelim('('));
   System.out.println(Lab12Task1.isLeftDelim('{'));
   System.out.println(Lab12Task1.isLeftDelim(']'));
   System.out.println(Lab12Task1.isRightDelim(']'));
   System.out.println(Lab12Task1.isRightDelim('}'));
   System.out.println(Lab12Task1.isRightDelim('('));
   System.out.printkn(Lab12Task1.matches('[', ']'));
   System.out.println(Lab12Task1.matches('{', '}'));
   System.out.println(Lab12Task1.matches('(', '}'));
   

   which would produce the following results:

   true
   true
   false
   true
   true
   false
   true
   true
   false
   

4. The key method for delimiter checking is called isBalanced(). We have given you a partial implementation, and you should complete it. Consult the lecture notes on delimiter checking as needed to remind yourself of how we can use a stack for this purpose.

   In particular, you will need to:

   • Add code that properly handles right delimiters. As you do so, take advantage of the helper methods.

   • Make whatever other changes are needed so that the method returns true when the delimiters are balanced and false when they are not.

   Here are some test calls:

   System.out.println( Lab12Task1.isBalanced("[(3 + 2) * 7] / 2") );
   System.out.println( Lab12Task1.isBalanced("[(3 + 2] * 7) / 2") );
   System.out.println( Lab12Task1.isBalanced("[(({}))]") );
   System.out.println( Lab12Task1.isBalanced("[(({))]}") );
   System.out.println( Lab12Task1.isBalanced("((((())") );
   System.out.println( Lab12Task1.isBalanced("(())))") );
   

   which would produce the following results:

   true
   false
   true
   false
   false
   false
   

Task 2: Use collection objects to divide numbers into subgroups

Suppose that we have an array containing integers between 0 and 999, and that we want to divide these integers into subgroups based on how many digits they have. In Lab12Task2.java, you will complete a method that does this.

The method is called divideByLength(). In takes an array of integers called values that we will assume contains integers between 0 and 999. It should return a list (either an ArrayList or LLList) in which:

• all of the one-digit numbers from values come first, followed by all of the two-digit numbers, followed by all of the three-digit numbers

• the numbers in a given subgroup (e.g., the one-digit numbers) are in the same order with respect to each other as they were in the original array.

For example:

int[] vals = {7, 300, 55, 3, 213, 24, 78, 8, 411};
List results = Lab12Task2.divideByLength(vals);
System.out.println( results );

would output:

{7, 3, 8, 55, 24, 78, 300, 213, 411}

Note that the method does not sort the numbers in increasing order by value. Rather, it reorders them based on how many digits they have.

Requirements:

• Your method must use one or more stacks or queues to assist it in dividing up the numbers, and it must return some type of list that contains the reordered numbers. Use instances of the classes in the lab12 folder.

• Choose your data structures (including what type of list to use for the final results) in a way that allows you to maximize the time efficiency of the method.

• Your method must perform only one iteration over the original array. After that one iteration, any additional manipulations of the integers should be done using the collection object(s) that you have chosen to use.

Two other notes:

• We have given you a helper method called numDigits() that you may find helpful.

• We strongly encourage you to map out your algorithm before you begin coding. Choose which collection classes you will use from the lab12 folder, and decide how you will put them to use.

  Feel free to discuss your design with your TA and/or CA before you begin coding!

Task 3: Binary-tree basics

Your work for this task should be done on paper.

Consider the following binary tree in which the keys are letters:

1. What is the depth of node E? Of node A?

2. What is the height of the tree?

3. If a preorder traversal were used to print the keys, what would the output be?

4. What would be the output of an inorder traversal?

5. What would be the output of a postorder traversal?

6. What would be the output of a level-order traversal?