( x + y - 24 ) * ( zone - ace / ( 25 + ci ) )
1. The value of the expression 20 35 - 5 / 10 7 * + is . Show the contents of the
operand stack just before each operator is processed and just after all tokens are scanned.
Review Questions
1. Show the effect of each of the following operations on stack s. Assume that y (type Character) contains the character 'Si'. What are the final values of x and success and the contents of the stack s?
Stack s = new Stack0 ;
char x;
s.push('+');
try {
x = s.pop();
success = true;
}
catch (EmptyStackException e) { success - false;
}
try {
x = s.pop();
success - true;
}
catch (EmptyStackException e) { success = false;
}
s.push('(');
s.push(y);
try {
x - s.pop();
success = true;
}
catch (EmptyStackException e) success - false;
}
2. Write a toSt ri ng method for class Ar rayStack.
3. Write a toSt ri ng method for class Li nkedStack.
4. Write an infix expression that would convert to the postfix expression in Quick-Check.
5. Write a constructor for class H nkedStack that loads the stack from an array parameter. The last array element should be at the top of the stack.
6. Write a client that removes all negative numbers from a stack of Integer objects. If the original stack contained the integers 30, -15, 20, -25 (top of stack), the new stack should contain the integers 30, 20.
7. Write a statement that uses a pseudorandom number to assign a value of 1 through 6 to a variable di e, where each number is equally likely.
Review Questions
1. Show the effect of each of the following operations on queue q. Assume that y (type Character) contains the character '&'. What are the final values of x and success (type boolean) and the contents of queue q?
Queue q new ArrayQueue();
boolean success - true; char x;
q.offer(.4.1);
try {
x - q.remove();
x = q.removeO;
success - true;
catch(NoSuchElementException e) {
success - false;
}
q.offerC(');
q.offer(y);
try (
x q remove() ;
success - true;
) catch(NoSuchElcmcntException c) success - false;
2. Write a new queue method called noveToRear that moves the element currently at the front of the queue to the rear of the queue. The element that was second in line will be the new front element. Do this using methods Queue.offer and Queue. renove.
3. Answer Question 2 without using methods Queue offer or Queue. remove for a single-linked list implementation of Queue. You will need to manipulate the queue internal data fields directly.
4. Answer Question 2 without using methods Queue .offer or Queue. remove for a circular array implementation of Queue. You will need to manipulate the queue internal data fields directly.
and bi narySearch?
11. Why did you need to provide a wrapper method for recursive methods in the Li nkedLi stRec class?
Review Questions
1. Explain the use of the run-time stack and activation frames in processing recursive method calls.
2. What is a recursive data structure? Give an example of one.
3. For class Li nkedLi stRec, write a recursive search method that returns true if its target argument is found and false otherwise. If you need a wrapper method, provide one.
4. For class Li nkedLi stRec, write a recursive repl aceFi rst method that replaces the first occurrence of a reference to its first argument with a reference to its second argument. If you need a wrapper method, provide one.
5. For Towers of Hanoi, show the output string that would be created by the method call Stacks
5. Write a client program that uses the Stack abstract data type to simulate a session with a bank teller. Unlike most banks, this one has decided that the last customer to arrive will always be the first to be served. Create classes that represent information about a bank customer and a transaction. For each customer, you need to store a name, current balance, and a reference to the transaction. For each transaction, you need to store the transaction type (deposit or withdrawal) and the amount of the transaction. After every five customers are processed, display the size of the stack and the name of the customer who will be served next.
6. Write a program to handle the flow of widgets into and out of a warehouse. The warehouse will have numerous deliveries of new widgets and orders for widgets. The widgets in a filled order are billed at a profit of 50 percent over their cost. Each delivery of new widgets may have a different cost associated with it. The accountants for the firm have instituted a last-in, first-out system for filling orders. This means that the newest widgets are the first ones sent out to fill an order. Also, the most recent orders are filled first. This method of inventory can be represented using two stacks: orders-to-be-filled and widgets-on-hand. When a delivery of new widgets is received, any unfilled orders (on the orders-to-be-filled stack) are processed and filled. After all orders are filled, if there are widgets remaining in the new delivery, a new element is pushed onto the widgets-onhand stack. When an order for new widgets is received, one or more objects are popped from the widgets-on-hand stack until the order has been filled. If the order is completely filled and there are widgets left over in the last object popped, a modified object with the quantity updated is pushed onto the widgets-on-hand stack. If the order is not completely filled, the order is pushed onto the orders-to-be-filled stack with an updated quantity of widgets to be sent out later. If an order is completely filled, it is not pushed onto the stack.
Write a class with methods to process the shipments received and to process orders. After an order is filled, display the quantity sent out and the total cost for all widgets in the order. Also indicate whether there are any widgets remaining to be sent out at a later time. After a delivery is processed, display information about each order that was filled with this delivery and indicate how many widgets, if any, were stored in the object pushed onto the widgets-on-hand stack.
7. You can combine the algorithms for converting between infix to postfix and for evaluating postfix to evaluate an infix expression directly. To do so you need two stacks: one to contain operators and the other to contain operands. When an operand is encountered, it is pushed onto the operand stack. When an operator is encountered, it is processed as described in the infix to postfix algorithm. When an operator is popped off the operator stack, it is processed as described in the postfix evaluation algorithm: The top two operands are popped off the operand stack, the operation is performed, and the result is pushed back onto the operand stack. Write a program to evaluate infix expressions directly using this combined algorithm.
8. Write a client program that uses the Stack abstract data type to compile a simple arithmetic expression without parentheses. For example, the expression list implementation of Queue.
7. Answer Question 5 without using methods Queue. offer or Queue. remove for a circu¬lar array implementation of Queue.
Programming Projects
1. Redo Programming Project 6 from Chapter 3, assuming that widgets are shipped using a first-in, first-out inventory system.
2. Write a class myArrayDeque that extends class ArrayQueue. Class MyArrayDeque should implement the Deque interface. Test your new class by comparing its operation to that of the ArrayDeque class in the Java Collections Framework.
3. Write a program that reads in a sequence of characters and stores each character in a deque. Display the deque contents. Then use a second deque to store the characters in reverse order. When done, display the contents of both deques.
4. Write a program that simulates the operation of a busy airport that has only two run¬ways to handle all takeoffs and landings. You may assume that each takeoff or landing takes 15 minutes to complete. One runway request is made during each five-minute time interval, and the likelihood of a landing request is the same as for a takeoff request.
Programming Projects
1. Download and run class BlobTest. Try running it with a data file made up of lines consisting of Os and is with no spaces between them. Also run it without a data file.
2. Download and run class MazeTest. Try running it with a data file made up of lines consisting of Os and is with no spaces between them. Also run it without a data file.
3. Write a recursive method that converts a decimal integer to a binary swing. Write a recursive method that converts a binary string to a decimal integer.
4. Write a Li nkedli stRec class that has the following methods: size, empty, nserthefore, i nsertAfter, addAtHead, addAtEnd, remove, repl ace, peekFront, peekEnd, removeFront, removeEnd, toSt ring. Use recursion to implement most of these methods.
5. A palindrome is a word that reads the same left to right as right to left. Write a recursive method that determines whether its argument string is a palindrome.
6. Write a program that will read a list of numbers and a desired sum.