Homework 2 - A Class as an ADT

Reading: Chapter 6.

Due (NOTE THIS HAS CHANGED): At 8:00am, January 22, 2001, submit is turned off automatically. Work turned in after that time will not be accepted for grading.

Program Description - Derivative Arithmetic

(This program is slightly modified from a program used in a regional ACM Programming Contest competition.)

In mathematical modelling, it is often convenient to have the derivative df/dx of a function as well as the function f itself. Numerical differentiation evaluates f twice, to compute (f(x+v)-f(x))/v for some small value of v. Program differentiation computes the derivative symbolically. Derivative arithmetic, on the other hand, works simply and efficiently without the problems involved in symbolic differentiation. For this we augment an expression with its derivative, i.e. we represent it by the ordered pair (e, de/dx). Thus we have:

A constant c is represented by (c, 0)
The variable x is represented by (x, 1)
Any other variable y is represented by (y, 0)
(a, b) + (c, d) = (a+c, b+d)
(a, b) – (c, d) = (a–c, b–d)
(a, b) * (c, d) = (a* c, b* c+a* d)
(0, b) / (0, d) = (b / d, 0) (using L'Hopital's rule. The unknown derivative is approximated by zero.)
(a, b) / (0, d) is undefined.
(a, b) / (c, d) = (a / c, (b * c - a* d)/ (c*c))

Write a program to simulate a Reverse Polish pocket calculator using this arithmetic (see Section 12.6 of JBD for a review of Polish notation). If any operation is undefined, clear the stack and continue from that point.

Input

Input will be a series of characters representing instructions chosen from the following set. Blanks and line breaks may be inserted arbitrarily to enhance readability, except within a and b. In addition, a value to be pushed on the stack will all appear on a single line. That is, there will be no line breaks in the middle of (a, b) from the first item below.

(a , b ) Push this number onto the stack.

+, -, *, / The topmost element of the stack is the right operand for this operator, and the one immediately below it is the left operand. Remove them, perform the operation, and push the result.

W Remove the top element of the stack and write it on a new line. See sample output below

D Push a copy of the top element of the stack onto the stack.

Q Stop. This will always be the last character.

Output

Output consists of one line for each W command, consisting of a left parenthesis, the central value e, a comma, the derivative de/dx, and a right parenthesis. There may be spaces before and/or after either number.

Sample Input

(2,1)(2,1)*(2,1)/W
(3,2)(1,0)+DW(1.5,2.3)(10,20)/*W
Q

Sample Output

(2.0, 1.0)
(4.0, 2.0)
(0.6, 0.019999999999999962)

A simplifying assumption

You might consider making the following simplifying assumption. Assume that the numbers in the input are always followed by at least one white space character. In this case the sample input would be:

(2 ,1 )(2 ,1 )*(2 ,1 )/W
(3 ,2 )(1 ,0 )+DW(1.5 ,2.3 )(10 ,20 )/*W
Q

In this case you can use Console.in.readCharNonwhite() and Console.in.readDouble() to do all of your input. Console.in.readDouble() assumes that the number is terminated by a white space character, hence the assumption.

To get full credit for this assigment your program will have to work WITHOUT making use of this assumption.

Hints

You are required to create a new ADT to represent the ordered pair (e, de/dx) described above. In addition, I suggest you also create a new class (ADT) to represent the input buffer, from which you can read characters, and doubles. This input buffer class can read lines using Console.in.readLineNonwhite(), storing the result in a character array. (readLineNonwhite() has been recently added to tio. The version in ~mcdowell/java/public contains the new method. You can obtain a copy of the new tio from here.

There is a static method, Double.parseDouble(), that will parse a String into a double. The String must consist of just the characters representing the number. In particular, there cannot be any leading or trailing white space. Given a String, the method trim() returns a new String, with all leading and trailing white space removed.

This page maintained by Charlie McDowell. Email regarding this site.