Week 11, 11/6

Prelab Exercises

1. Complete UnionFind exercises

Lab Exercises

1. Evaluate the following postfix expressions, none result in an error.

   1. 3 8 7 + * 5 /
   2. 6 4 * 20 - 12 +
   3. 8 6 + 4 + 2 *
   4. 5 4 3 2 1 + + + +

2. For the last expression above, explain which re-arrangements of the numbers 1, 2, 3, 4, 5, and four plus-signs do not result in the value 15 and why. Use English to describe the characteristics of the expressions whose value is not 15.

   ---

   The questions below refer to the Postfix.java program. Here's a capture of one run of the program. The user entered input is in italics.

   3 5 8 + *
   value of 3 5 8 + * = 39
   5 3 -
   value of 5 3 - = 2
   5 3 + +
   error: java.lang.RuntimeException: empty stack error java.util.EmptyStackException
   3 a +
   error: java.lang.RuntimeException: badly formed postfix expression java.lang.NumberFormatException: For input string: "a"
   9 +
   error: java.lang.RuntimeException: empty stack error java.util.EmptyStackException
   5 7 %
   error: java.lang.NumberFormatException: For input string: "%"
   
   

3. The StringTokenizer class splits a string into a sequence of tokens separated by some character in the String DELIMS, but also returns the character separating the tokens. Explain the purpose of the if (t.equals(" ")) continue; statement in the method evaluate (note that there is a space as the last character of DELIMS).

4. As shown in the run above, the postfix expression 5 3 + + generates an error. Explain the error and how the exceptions are caught and rethrown in the code.

5. As shown in the run above, the postfix expression 3 a + generates an error. Explain the error and how the exceptions are caught and rethrown in the code -- in particular, when does the error occur in the processing and evaluation of the expression?

6. The postfix expression "5 3 %" generates an error as shown above -- note that this is not a RunTimeException. Why is a NumberFormatException generated --- when does the error occur. Explain how to modify DELIMS so that the IllegalArgumentException about unrecognized operators is generated (and why/how modifying DELIMS will generate the error).

   ---

   Stack/Queue Questions

   These questions don't refer to the postfix evaluation code.

7. Describe the contents of stack s after the method convert below executes. (describe the contents in a general manner based on what's in s before the code executes.) public void convert(Stack<Object> s){ ArrayList<Object> list = new ArrayList<Object>(); while (s.size() > 0) { list.add(s.pop()); } for(Object o : list) { s.push(o); } }
8. What happens if a queue is used instead of a stack in the code above, e.g., public void convert(Queue<Object> q){ ArrayList<Object> list = new ArrayList<Object>(); while (q.size() > 0) { list.add(q.remove()); } for(Object o : list) { q.add(o); } }

9. Consider loading a stack and queue using the code below, this is the load method (we'll consider the stack and queue to be instance variables). Stack<String> stack = new Stack<String>(); Queue<String> queue = new LinkedList<String>(); public void load(){ for(int k=0; k < 10; k++) { stack.push(""+k); queue.add(""+k); } }

   What is printed by the following after loading the stack using the load method.

   while (stack.size() > 0) { System.out.println(stack.pop()); }

10. What is printed by the following after loading the queue using the load method. while (queue.size() > 0) { System.out.println(queue.remove()); }

    Consider the function popFromTo below.

    Stack<Object> popFromTo(Stack<Object> from) { Stack<Object> to = new Stack<Object>(); while (from.size() > 0) { to.push(from.pop()); } return to; }
11. What happens when the statement below executes? s = popFromTo(s);

12. If stack s is loaded with 10 values using the load method, what are the contents of s after executing: Stack<Object> s2; s2 = popFromTo(s); s = popFromTo(s2);

13. Suppose the statements below are executed (when queue contains 10 values from the load method), what are the contents of q2 after the 11 is added to queue? Queue<Object> q2 = queue; queue.add(""+11);