CS 112 Summer 2, 2017-- Homework Four

Due Monday, July 17th at midnight.

 

Introduction

This homework has two parts: in Part A you will write up answers to analytical problems related to the lectures in the past week, both to confirm and extend your understanding of the abstract principles discussed; in Part B you will write code to implement this understanding, and to practice your Java coding skills. I suggest you read this whole assignment carefully and for Part B, it is definitely worth thinking about your solution for a bit before launching Eclipse and beginning to type. In addition to the requirements for the Java problems, you must observe the following requirements (for all homework submitted in this course):

 

Part A: Analytical Problems (10 points)

The questions below are designed to reinforce the material exposed to you at lecture and from assigned readings. Please submit your answers as a file hw04.txt.

  1. Manipulating a stack

    Given the following stack, depicted here from top to bottom:

     +   +
     | 6 |
     | 8 |
     | 1 |
     | 3 |
     | 7 |
    -+---+-
    

    What would the stack look like after the following sequence of pushes and pops?

    pop();      // assume you simply throw away the value after popping it
    push(2);
    push(9);
    push(0);
    pop();
    push(7);
    
  2. Manipulating a queue

    Given the following queue, depicted here from the back of the queue (left) to the front (right):

    +-------------------+
    | 3 | 8 | 1 | 5 | 2 |
    +-------------------+
    

    What would the queue look like after the following sequence of enqueues and dequeues?

    dequeue();     // assume you simply throw away the value after dequeueing it
    dequeue();
    enqueue(9);
    enqueue(3);
    dequeue();
    
  3. Manipulating a priority queue

    Given the following Priority Queue, depicted here from the back of the queue (left) to the front (right):

    +-------------------+
    | 1 | 4 | 6 | 7 | 9 |
    +-------------------+
    

    Assuming that this is a "MaxQueue," where elements are kept in increasing order, such that larger items leave the queue before smaller items, what would the queue look like after the following sequence of enqueues and dequeues?

    getMax();         // assume you simply throw away the value after dequeueing it
    insert(5);
    getMax();
    insert(12);
    insert(2);
    getMax(); 
  4. Suppose a number of push() and pop() operations are performed on a stack S. The push() operations put the integers 0 through 9 onto S in order, and the pop() operations print the return value. That is, the sequence looks like this:
      push(0);
      pop() and print 0 or more times;
      push(1);
      pop() and print 0 or more times;
      push(2);
      pop() and print 0 or more times;;
      ....
      push(9);
      pop() and print 0 or more times;

    The question is. what possible sequences of values could be produced by such a sequence? For example, we could produce

         0 1 2 3 4 5 6 7 8 9
         
    by pushing 0, popping it, pushing 1, popping it, and so on. Or, we could produce
    
         9 8 7 6 5 4 3 2 1 0 
         
    by pushing 0, pushing 1, etc. up to 9, then popping all of them off. Or, we could do
    
         5 4 3 2 1 0 9 8 7 6
         
    by pushing 0 through 5, popping them all off, then pushing
    6 through 9 and popping them all of. 
    

    Ok, your turn! For each of the following sequences, state whether or not they could occur as a result of such a sequence of stack operations.

    1. 9 8 7 6 5 4 3 2 1 0
    2. 8 7 6 5 4 3 2 1 0 9
    3. 4 3 2 1 0 5 6 7 8 9
    4. 4 6 8 7 5 3 2 9 0 1
  5. This problem considers the same problem as (5) but for MaxQueues. Suppose a number of insert() and getMax() operations are performed on a MaxQueue M. The put() operations put the integers 0 through 9 onto M in order, and the getMax() operations print the return value. That is, the sequence looks like this:
      insert(0);
      getMax and print 0 or more times;
      insert(1);
      getMax and print 0 or more times;
      insert(2);
      getMax and print 0 or more times;;
      ....
      insert(9);
      getMax and print 0 or more times;

    For each of the following sequences, state whether or not they could occur as a result of such a sequence of MaxQueue operations.

    1. 9 8 7 6 5 4 3 2 1 0
    2. 0 1 2 3 4 5 6 9 8 7
    3. 5 4 3 7 6 9 8 2 1 0
    4. 1 2 3 4 5 0 9 7 8 6
  6. Suppose we consider the same problem as in (5) and (6) for standard queues. Of course one sequence of numbers that could be produced is the numbers in order:
         0 1 2 3 4 5 6 7 8 9
      
    Is this the only sequence that you can produce, or is there is another sequence that is possible? Explain your answer by giving another sequence or explaining why the one given is the only possible sequence.
  7. Suppose you have a queue Q and a stack S and you perform the following operations:
              while(! Q.isEmpty() )            // push every element of Q onto the stack
                  S.push( Q.dequeue() );
              while(! S.isEmpty() )            // Enqueue every element popped off the stack
                  Q.enqueue( S.pop() ); 
    How would you describe what you have done to the queue?
     
      
  8. Now suppose you have a stack S and a MaxQueue M, and you perform the following operations:
              while(! M.isEmpty() )            // push every element of M onto the stack
                  S.push( M.getMax() );
              while(! S.isEmpty() )            // Insert every element popped off the stack
                  M.insert( S.pop() ); 
    How would you describe what you have done to the priority queue? You may assume there are no duplicate numbers involved.
     
      
  9. Now suppose you have a priority queue M, a normal queue Q, and a stack S; M and S are initially empty, but Q has elements in it. You perform the following operations:
              while( !Q.isEmpty() )             
                  M.insert( Q.dequeue() );
              while( !M.isEmpty )             
                  S.push( M.getMax() );
              while( !S.isEmpty() )            
                  Q.enqueue( S.pop() ); 
    How would you describe what you have done to the queue Q? You may assume there are no duplicate numbers involved.
  10.  
      
  11. This is an exercise in the use of reference types. Recall that Strings are reference types, and the name of a String object can be changed, just as arrays can. What would the following code fragment print out?
      String s = "Hithere";
      String t = "Folks";
      String u = "CS112";
      String v = s;
      s = t;
      t = v;
      u = s;
      System.out.println(s.charAt(0)); 
      System.out.println(t.charAt(1));
      System.out.println(u);
      System.out.println(v);
      
Write your answers to these questions as a file hw04.txt and hand in as part of your homework submission into the hw04 folder in Websubmit.

Again, do these by hand to verify understanding, and don't just type them into Eclipse for the answers. If you do so, then you will be unable to do such problems on tests!

Part B: Programming Problems (90 points)

Problem B.1: A Big Integer Calculator using Two Stacks (45 points)

For this problem, you are going to use a clever algorithm for evaluating arithmetic expressions which uses two stacks to do the computation. The algorithm uses two stacks: one, Ops, containing Strings which represent the operators "+" and "*" and another, Nums, which stores the number operands, in this case, BigInt objects. For the purpose of understanding the algorithm, we will just show these BigInt objects as normal integers and the operators and parentheses as Strings. A token is a String representing an operator (here just + and - ), left parenthesis, right parenthesis, or a positive integer (which represents a BigInt). The input is an array of tokens representing an arithmetic expression. The pseudo-code for this algorithm is as follows:

Both stacks Op and Nums are initially empty;

Let [T1, T2, ...., Tk] be the array of tokens:

For each token in the list, from T1 to Tk:

     1. If the token is a left parenthesis "(" do nothing;
     2. If the token is an operator "+" or "*", push it on the Op stack;
     3. If the token is a right parenthesis ")", 
           (a)  Pop the Nums stack twice to get the two operands,
           (b)  Pop the Ops stack once to get the operator, 
           (c)  Apply the appropriate operation to the two operands, and push the result back on the Nums stack;
     4. Otherwise, assume the token is a number, convert it to a BigInt, and push it on the Nums stack

After you have processed all the tokens in this way, if the expression was correct there
will be a single BigInt on the Nums stack; pop it off and print this out as the result of the expression. 

Here is an example (assume the parentheses and operators are Strings and the ints are strings when they are
in the array of tokens, and BigInts when they are on the Nums stack):

Tokens:   ( 4 * ( 8 + 9 ) )             // assume these are in an array

To process, let us look at the two stacks (drawn sideways, with bottom to the left) and the remaining unprocessed tokens:

Tokens: ( 4 * ( 8 + 9 ) )
Ops:
Nums:

Tokens: 4 * ( 8 + 9 ) )      // Case 1
Ops:
Nums:

Tokens: * ( 8 + 9 ) )        // Case 4
Ops:
Nums: 4

Tokens:  ( 8 + 9 ) )         // Case 2
Ops: * 
Nums: 4

Tokens:  8 + 9 ) )           // Case 1
Ops: *
Nums: 4

Tokens:   + 9 ) )            // Case 4
Ops: *
Nums: 4 8 

Tokens:   9 ) )              // Case 2
Ops: * +
Nums: 4 8

Tokens: ) )                  // Case 4
Ops: * +
Nums: 4 8 9

Tokens:  )                   // Case 3
Ops: * 
Nums: 4 17

Tokens:                      // Case 3
Ops: 
Nums: 68

Since there are no tokens left and a single BigInt on the Nums stack, the result is correct. Print out the 68 as the result.

The starter template code is here: BigIntCalculator.java. I have already included some code to input the expressions, you should not change this.

Using the BigInt code: I am providing you with another version of the BigInt code, but designed as an ADT, that is, a BigInt is a (non-static) object (not simply an array of ints) containing a representation of a big integer, and methods associated with it, including add(..) and mult(....). The big integers are represented as linked lists, which we will begin to study this week. You may download it here: BigInt.java and by examining the main method tests, you will see how it works.

You MUST do the following for this problem:

Big Hint: Before writing the StringStack and BigIntStack code, ask yourself the question: "Hm.... do I have access to anything similar that I can rewrite?" (You might want to read to the end of the assignment before answering this question!)

You do NOT need to do any error checking for this program; you may assume the user typed in the input correctly; and the system may crash if he/she does not. We will learn the right way to deal with such errors shortly.

Test your code and verify that it performs as shown here:

Big Int Calculator:
Enter an arithmetic expression with big integers, *, and +, with 
all expressions fully parenthesized; enter -1 to end. 
(5+8)
13
(8*9)
72
(2342342342342342342342 * 0)
0
(((234 * 5434) + (243 * 98908))
25306200
(20398420938402934 * (2039842034820 * 20938402384023802))
871237636475609480275702104746923977409067760
-1
bye!

 

 

Problem B.2 Building a Queue from Two Stacks (45 points)

For this problem you will explore the relationship between stacks and queues by considering how a queue may be implemented by two stacks. This is a clever algorithm which explores the relationship between these two data structures. It is also more efficient than the naive method you explored in the lab problem, since most enqueue and dequeue operations take a fixed amount of time, and you do not have to move all the elements over every time.

Implementing a queue with two stacks

The basic of idea of the program follows from the observation that in some sense, you can consider a queue to be two stacks with their bottoms stuck together, with their tops facing in opposite directions. Let us call them InStack and OutStack; here is the queue from problem A.2 above with 3 at the rear of the queue and 2 at the front:


rear              front
+-------------------+
| 3 | 8 | 1 | 5 | 2 |
+-------------------+

There are multiple ways to represent this queue as two stacks. Here is one way:


 InStack    |  OutStack
+-----------+-------+
| 3 | 8 | 1 | 5 | 2 |
+-----------+-------+
            | 

that is,


 InStack:        OutStack:   

            
  | 3 |                      
  | 8 |             | 2 | 
  | 1 |             | 5 | 
 -+---+-           -+---+-

and here is another:


InStack |    OutStack
+-------+-----------+
| 3 | 8 | 1 | 5 | 2 |
+-------+-----------+
        | 

that is,


 InStack:        OutStack:   
            
                    | 2 |          
  | 3 |             | 5 | 
  | 8 |             | 1 | 
 -+---+-           -+---+-

and here is yet another:


     InStack        |   OutStack
+-------------------+
| 3 | 8 | 1 | 5 | 2 |
+-------------------+
                    | 

that is,


 InStack:        OutStack (empty):   

  | 3 |
  | 8 |
  | 1 |
  | 5 |
  | 2 |
 -+---+-        -+---+-

Now, the question is: how do we implement the standard queue operations using stack operations on InStack and OutStack? Let's consider this and show examples using the first representation of the queue above. Some are very easy:

To enqueue a number, simply push it on the InStack:


 InStack    |  OutStack
+-----------+-------+
| 3 | 8 | 1 | 5 | 2 |
+-----------+-------+
            | 

=>  enqueue(7)  =>

 InStack        |  OutStack
+---------------+-------+
| 7 | 3 | 8 | 1 | 5 | 2 |
+---------------+-------+
                | 

To dequeue a number, simply pop it off the OutStack (let us continue with the previous configuration):


 InStack        |  OutStack
+---------------+-------+
| 7 | 3 | 8 | 1 | 5 | 2 |
+---------------+-------+
                | 

=>  dequeue()  =>

 InStack        |  OutStack
+---------------+---+
| 7 | 3 | 8 | 1 | 5 |       =>  2
+---------------+---+
                | 

But what if, when we want to dequeue a number, the OutStack is empty? In that case, we pop all the members of the InStack off and push them all onto the OutStack. Let us do two more dequeue()'s on the previous configuration and see how this works:


=>  dequeue()  =>

 InStack        |  OutStack
+---------------+
| 7 | 3 | 8 | 1 |        =>  5
+---------------+
                | 
                
=>  dequeue()  ... Outstack empty, so pop off Instack and push on OutStack until InStack is empty:

 InStack    |  OutStack
+-----------+---+
| 3 | 8 | 1 | 7 |        
+-----------+---+
            | 

InStack |  OutStack
+-------+-------+
| 8 | 1 | 7 | 3 |        
+-------+-------+
        | 

InStack |  OutStack
    +---+-----------+
    | 1 | 7 | 3 | 8 |        
    +---+-----------+
        | 

InStack |  OutStack
        +---------------+
        | 7 | 3 | 8 | 1 |        
        +---------------+
        |                

Finally we can complete the dequeue() by popping the OutStack:


InStack |  OutStack
        +-----------+
        | 7 | 3 | 8 |      =>  1    
        +-----------+
        |                

So, the punchline is: if the OutStack is empty when you want to dequeue(), pop everything off the InStack and push its contents onto the OutStack before proceeding.

Notice how this algorithm cleverly uses the fact that if you push a list of numbers on a stack and pop them off, they come off in reverse order: since the list of numbers being enqueue()'ed must come out of the queue in the same order they came in, we reverse them twice, once as they move from the InStack to the OutStack, and once as they come out of the OutStack. (If this were a Trump Tweet, I would conclude with: Nice!)

I will leave it to you to figure out peek(), size(), and isEmpty(). Overflow will be handled by resizing in the stacks, so you don't have to worry about doing it in the IntQueue class, and as usual we will not worry about underflow for now.

The Problem

You must fill in the template code IntQueue.java, which has tests in the main method as usual. Here is the Queueable.java interface you need for this template. You must follow these requirements:

(1) You must use the IntStack.java ADT to implement the queue, as shown above (hint: the two stacks will be fields inside the IntQueue object).

(2) The IntQueue object must implement the Queueable.java interface; you will see this in the template and the Unit Test Main.

(3) The toString() method (you must provide it, though it is not in the interface) must print out the queue by rotating the queue, building up the result String by concatenating each element as it is dequeued and before it is enqueued back into the queue:

If there are N elements in the queue, do this N times:

     int n = dequeue();
     ...concatenate n and a tab ("\t") onto the result String...
     enqueue( n );

At the end of this process, you will have a String representation of the queue, in order, and the queue will be back in its original configuration.

(4) You may NOT declare an array or any other data structure (except for the two stacks) to help implement the queue;

(4) You may NOT change anything about IntStack.java or Queueable.java;

(5) All performance tests in the Unit Test Main must be satisifed.

Hand in your solution as IntQueue.java.

 

Submission Checklist