There are two parts to this assignment: problems from the G&T text and a program that uses stacks and exceptions.

1) [15 points] Do the following problems in Goodrich and Tamassia:

a) R-2.2, pg. 58

b) R-2.3, pg. 58

c) R-2.12, pg. 59

d) R-2.13, pg. 59

e) C-2.8, pg. 62

2) [35 points total] This programming task involves stacks, calculators, and exceptions. It may be beneficial to read and understand the entire assignment before writing code. Much of the implementation is described in the text book or in lecture or supplied in ~lorenz/cs35-2/hw2/; you are free to use such code with proper documentation of the source. You may not use pre-existing class libraries (such as for stacks, for example).

a) [10 points] Implement an IntStack class using an array that maintains a stack of integers. Provide the standard stack methods

      public void push(int i);
    

      public int pop();
    

      public boolean isEmpty();
    

      public int top();
    

and a field that holds the size of the stack:

      public int size;
    

b) [15 points] Using the integer stack, implement a postfix calculator for integers. Typically, humans deal with expressions in infix notation where the operators (e.g. +, /) are written between the operands as in (3+8)/2. Writing the operators after the operands gives postfix: e.g., 3 8 + 2 /. Postfix has the nice property that parentheses are unnecessary. Furthermore, postfix expressions can be evaluated readily with a stack: scan the expression string left to right, push integers onto the stack as they are encountered, apply arithmetic operators -- when encountered -- to the two topmost elements of the stack and push the result, and return the top stack element as the answer upon reaching the end of the string.

Using your IntStack of 2a, implement a postfix calculator. Your calculator should provide addition, subtraction, multiplication and division. To get you started, the class Parse is provided (~lorenz/cs35-2/hw2/parse.java); it breaks a string into tokens (integers and arithmetic operators). This class provides the following constructor, method, and field:

  public Parse(String s);  
  /* constructs a Parse object for expression string s */
    

  public char getToken();
  /* returns the next token from the expression string 
   *     If the token is an integer, 'i' is returned and the value
   *     of the integer is placed in the "the_int" field;
   *     Otherwise, the next non-whitespace character in the string
   *     is returned.  
   *     Upon end-of-string, the null character '\0' is returned.
   */
    

  public int the_int;
  /* value of the last integer parsed */

A Parse object p constructed as new Parse("3 8 + 2 /"), for example, will return the tokens 'i', 'i', '+', 'i', '/', '\0' on invocations of getToken(). When an 'i' is returned, the integer value is in the p.the_int field.

Take the first argument to your calculator program as the expression string to evaluate; that is,

  $ java Main "3 8 + 2 /"

should print the value 5. Your main dispatch loop might be as follows:

  public static void main(String[] args) {
    /* declarations for calculator/stack objects might go here */ 
    Parse p = new Parse(args[0]);
    char c;

    while ((c = p.getToken()) != '\0') {
      switch (c) {
      case 'i': 
        /* place integer on calculator's stack */
	break;
      case '+':
        /* add the calculator's two top stack elements and push result */
	break;
      /* cases for '-', '*', and '/' go here */
      default:
	/* found an unknown token character; report error */
	break;
      }
    }
    /* print calculation answer */
  }

c) [5 points] Since stack operations may fault (overflow, underflow), use Java's exception mechanism to declare and throw a StackException. For a divide-by-zero fault in calculator division, Java will throw an ArithmeticException. Enclose your main loop in a try block and catch relevant exceptions; print an error message before exiting.

d) [5 points] Retrofit your IntStack as a more general (polymorphic) Stack class that holds elements of type Object (instead of just int). Modify your calculator to use the Stack class. To get this to work, you must push objects of type Integer instead of type int onto the stack and cast them back to Integer upon a pop. See java.lang.Integer for methods to convert from Integer to int, among other things. (Since this part of the programming assignment subsumes 2a, you may skip 2a entirely and use just the Object stack for 2b -- debugging the calculator is then a bit more tricky though due to Integer-int conversions.)

Hand in: answers for (1), the complete code and comments for (2), and a script demonstrating that your calculator correctly evaluates expressions and that it gracefully exits on stack and arithmetic error conditions.
instructions on how to submit