CSC234 - Exam 1

Assigned Feb 29th
Due Mar 5th Beginning of Class

Show your work on all questions for full credit. You must work on this exam individually. You may use your textbook, but not any resources on the internet except explicitly linked from this webpage and what we have coded together in class.

Postfix Calculator

Postfix notation is a way to unambiguously write a mathematical statement with the operator (+, *, -, etc) after the two operands instead of before. For example, we can write

2 + 3

as

2 3 +

To evaluate an expression in postfix notation in a calculator, we can use a Stack. When a number is entered, it is pushed onto the stack. When an operator is entered, the last two elements of the stack are popped, the operation is performed between the two items, and the result is pushed back onto the stack. When the calculation is complete, we peek at the top of the stack to see the answer.

Draw the state of the stack at each step of the calculation using our ArrayStack implementation, and show the methods you would call, when given the following input

1, 2, 3, +, +, 7, 9, +, *

Small Methods

  1. Write a method public boolean removeThird(E t) for our ArrayList that will remove the third instance of an element in the list when there are at least three of that element in the list. If the remove is successful, return true, otherwise return false.

  2. Write a method public int lastIndexOf(E t) for our ArrayList that will return the last found location of the element t. If the element is not found in the ArrayList, return -1.

  3. Write a method public boolean funky(int[] nums) that will return true if each element in the array is either at least twice as much as the sum of the elements before it, or a multiple of 7. For example [1, 2, 8, 23, 21, 120] would return true, while [3, 8, 25, 44, 200] would return false because 44 is invalid.

Building a Stack from Queues

In class, we built a Stack out of an array and an integer to denote the top of the Stack. There are many other ways to build a Stack. One of them is to use two Queues, such that when a stack operation is called, the element is instead passed to the Queues.

For example, the push method of the Stack can add the element to the first Queue. The pop method is more complicated, where you must remove elements of the Queue to find the most recently added element instead of the front element. This is where you can use the second Queue to help you out so you don't lose all these elements... but I will leave the details of this to you.

Write a class QStack<E> that will have two ArrayQueues as data members. Implement all the methods of the Stack interface using calls to your two ArrayQueue data members.

Book Objects

Write a class in Java to represent a book. A book should have four data members Include a constructor to create a book when given the name, author and number of pages.

Write a method isFinished() that will return true when the current page is on the last page of the book.

Write a method read() that will return the string "Call me Ishmael." and advance the current page by one, unless the current page is the last page, where it will output "The End." and not advance the page. This method should make use of the isFinished() method you wrote above.

Short Answer

© Mark Goadrich 2012, Centenary College of Louisiana