Solution for Programming Exercise 9.7
This page contains a sample solution to one of the exercises from Introduction to Programming Using Java.
Exercise 9.7:
This exercise builds on the previous exercise, Exercise 9.6. To understand it, you should have some background in Calculus. The derivative of an expression that involves the variable x can be defined by a few recursive rules:
- The derivative of a constant is 0.
- The derivative of x is 1.
- If A is an expression, let dA be the derivative of A. Then the derivative of -A is -dA.
- If A and B are expressions, let dA be the derivative of A and let dB be the derivative of B. Then the derivative of A+B is dA+dB.
- The derivative of A-B is dA-dB.
- The derivative of A*B is A*dB + B*dA.
- The derivative of A/B is (B*dA - A*dB) / (B*B).
For this exercise, you should modify your program from the previous exercise so that it can compute the derivative of an expression. You can do this by adding a derivative-computing method to each of the node classes. First, add another abstract method to the ExpNode class:
abstract ExpNode derivative();
Then implement this method in each of the four subclasses of ExpNode. All the information that you need is in the rules given above. In your main program, instead of printing the stack operations for the original expression, you should print out the stack operations that define the derivative. Note that the formula that you get for the derivative can be much more complicated than it needs to be. For example, the derivative of 3*x+1 will be computed as (3*1+0*x)+0. This is correct, even though it's kind of ugly, and it would be nice for it to be simplified. However, simplifying expressions is not easy.
As an alternative to printing out stack operations, you might want to print the derivative as a fully parenthesized expression. You can do this by adding a printInfix() routine to each node class. It would be nice to leave out unnecessary parentheses, but again, the problem of deciding which parentheses can be left out without altering the meaning of the expression is a fairly difficult one, which I don't advise you to attempt.
(There is one curious thing that happens here: If you apply the rules, as given, to an expression tree, the result is no longer a tree, since the same subexpression can occur at multiple points in the derivative. For example, if you build a node to represent B*B by saying "new BinOpNode('*',B,B)", then the left and right children of the new node are actually the same node! This is not allowed in a tree. However, the difference is harmless in this case since, like a tree, the structure that you get has no loops in it. Loops, on the other hand, would be a disaster in most of the recursive tree-processing subroutines that we have written, since it would lead to infinite recursion. The type of structure that is built by the derivative functions is technically referred to as a directed acyclic graph.)
The solution to Exercise 9.6 already allows the variable x to occur in expressions. Since we are building on that solution, no changes are needed in the parsing routines. There are a few easy changes in the main() routine, since it must take the derivative of the expression entered by the user and then work with that derivative. The changes are shown in the solution that is given below.
Aside from that, we only need to add the "ExpNode derivative()" method to each of the node classes. Since I want to print out the derivative in fully parenthesized infix form, I also add another method, "void printInfix()". Since this is not a required part of the exercise—and since it's fairly simple to do—I won't discuss the printInfix() method further.
All the information that is needed for writing the derivative() methods is given in the derivative rules that are listed in the exercise. The first three rules are pretty simple:
- Since the derivative of a constant is 0, the derivative() method in the ConstNode class has to return an ExpNode that represents the expression "0". That's easy. We just need a constant node that contains the number 0. The definition of derivative() in the ConstNode class is just: "return new ConstNode(0);".
- Similarly, the derivative of x is 1, so the definition of derivative() in the VariableNode class is "return new ConstNode(1);".
- The derivative of -A is -dA, that is, it consists of a unary minus operator applied to the derivative of the operand A. So, in the UnaryMinusNode class, we have to compute the derivative of the operand and then create an ExpNode that applies a unary minus to that derivative. The derivative of operand is operand.derivative(), so we only need to "return new UnaryMinusNode(operand.derivative());".
In the BinOpNode class, the derivative rule that we need to apply depends on the value of the binary operator, +, -, *, or /. The rules for A+B and A-B are easy to implement. Let's look at the case of *, where the rule is that the derivative of A*B is A*dB+B*dA. In the BinOpNode class, A is the left operand and B is the right operand. We can compute the derivatives dA and dB as left.derivative() and right.derivative(). We then have to build an expression tree to represent A*dB+B*dA. We need one node to represent the + operation and two more nodes to represent the two * operations. We can create the tree step-by-step:
ExpNode dA = left.derivative();
ExpNode dB = right.derivative();
ExpNode firstHalf = new BinOpNode('*', left, dB); // A*dB
ExpNode secondHalf = new BinOpNode('*', right, dA); // B*dA
ExpNode answer = new BinOpNode('+', firstHalf, secondHalf);
return answer; // This is the derivative we want!
In my solution, however, I did the same thing in one statement:
return new BinOpNode( '+',
new BinOpNode('*', left, right.derivative()),
new BinOpNode('*', right, left.derivative()) );
This uses the fact that a constructor call is an expression and can be used as an actual parameter in a subroutine. This statement returns a node that represents the sum of two things. The first thing is a node that represents the product of left and right.derivative(), and the second is a node that represents the product of right and left.derivative(). This is exactly the same thing that is returned by the previous sequence of six statements. There are reasonable arguments for doing things either way.
The rule for A/B is even more complicated: (B*dA-A*dB)/(B*B). Nevertheless, using left for A and right for B, I can compute the value with a single statement:
return new BinOpNode( '/',
new BinOpNode('-',
new BinOpNode('*', right, left.derivative()),
new BinOpNode('*', left, right.derivative())),
new BinOpNode('*', right, right) );
As an exercise, you might try doing the same thing with a sequence of simple statements.
import textio.TextIO;
/*
This program reads standard expressions typed in by the user.
The program constructs an expression tree to represent the
expression. It computes the derivative of the expression and
prints out the derivative and the value of the derivative at
several values of x. It also prints out a list of commands
that could be used on a stack machine to evaluate the derivative.
The expressions can use the variable "x", positive real numbers, and
the binary operators +, -, *, and /. The unary minus operation
is supported. The expressions are defined by the BNF rules:
<expression> ::= [ "-" ] <term> [ [ "+" | "-" ] <term> ]...
<term> ::= <factor> [ [ "*" | "/" ] <factor> ]...
<factor> ::= <number> | <x-variable> | "(" <expression> ")"
A number must begin with a digit (i.e., not a decimal point).
A line of input must contain exactly one such expression. If extra
data is found on a line after an expression has been read, it is
considered an error.
In addition to the main program class, SimpleParser5, this program
defines a set of five nested classes for implementing expression trees.
*/
public class SimpleParser5 {
// -------------------- Nested classes for Expression Trees ------------------------------
/**
* An abstract class representing any node in an expression tree.
* The four concrete node classes are concrete subclasses.
* Two instance methods are specified, so that they can be used with
* any ExpNode. The value() method returns the value of the
* expression for a specified value of the variable, x.
* The printStackCommands() method prints a list
* of commands that could be used to evaluate the expression on
* a stack machine (assuming that the value of the expression is
* to be left on the stack).
* The derivative() method returns an expression tree for the derivative
* of the expression (with no attempt at simplification). Actually,
* this might not be a tree, but it is a "directed acyclic graph",
* with no loops, so it's OK for our purposes. The printInfix()
* method prints the expression in fully parenthesized form.
*/
abstract private static class ExpNode {
abstract double value(double xValue);
abstract void printStackCommands();
abstract void printInfix();
abstract ExpNode derivative();
}
/**
* Represents an expression node that holds a number.
*/
private static class ConstNode extends ExpNode {
double number; // The number.
ConstNode(double val) {
// Construct a ConstNode containing the specified number.
number = val;
}
double value(double xValue) {
// The value of the node is the number that it contains.
return number;
}
void printStackCommands() {
// On a stack machine, just push the number onto the stack.
System.out.println(" Push " + number);
}
void printInfix() {
System.out.print(number);
}
ExpNode derivative() {
// The derivative of a constant is zero.
return new ConstNode(0);
}
}
/**
* An expression node representing a binary operator,
*/
private static class BinOpNode extends ExpNode {
char op; // The operator.
ExpNode left; // The expression for its left operand.
ExpNode right; // The expression for its right operand.
BinOpNode(char op, ExpNode left, ExpNode right) {
// Construct a BinOpNode containing the specified data.
assert op == '+' || op == '-' || op == '*' || op == '/';
assert left != null && right != null;
this.op = op;
this.left = left;
this.right = right;
}
double value(double xValue) {
// The value is obtained by evaluating the left and right
// operands and combining the values with the operator.
double x = left.value(xValue);
double y = right.value(xValue);
switch (op) {
case '+': return x + y;
case '-': return x - y;
case '*': return x * y;
case '/': return x / y;
default: return Double.NaN; // Bad operator!
}
}
void printStackCommands() {
// To evaluate the expression on a stack machine, first do
// whatever is necessary to evaluate the left operand, leaving
// the answer on the stack. Then do the same thing for the
// second operand. Then apply the operator (which means popping
// the operands, applying the operator, and pushing the result).
left.printStackCommands();
right.printStackCommands();
System.out.println(" Operator " + op);
}
void printInfix() {
// Print the expression, in parentheses.
System.out.print('(');
left.printInfix();
System.out.print(" " + op + " ");
right.printInfix();
System.out.print(')');
}
ExpNode derivative() {
// Apply the derivative formulas.
switch (op) {
case '+':
return new BinOpNode('+', left.derivative(), right.derivative());
case '-':
return new BinOpNode('-', left.derivative(), right.derivative());
case '*':
return new BinOpNode( '+',
new BinOpNode('*', left, right.derivative()),
new BinOpNode('*', right, left.derivative()) );
case '/':
return new BinOpNode( '/',
new BinOpNode('-',
new BinOpNode('*', right, left.derivative()),
new BinOpNode('*', left, right.derivative())),
new BinOpNode('*', right, right) );
default:
return null;
}
}
}
/**
* An expression node to represent a unary minus operator.
*/
private static class UnaryMinusNode extends ExpNode {
ExpNode operand; // The operand to which the unary minus applies.
UnaryMinusNode(ExpNode operand) {
// Construct a UnaryMinusNode with the specified operand.
assert operand != null;
this.operand = operand;
}
double value(double xValue) {
// The value is the negative of the value of the operand.
double neg = operand.value(xValue);
return -neg;
}
void printStackCommands() {
// To evaluate this expression on a stack machine, first do
// whatever is necessary to evaluate the operand, leaving the
// operand on the stack. Then apply the unary minus (which means
// popping the operand, negating it, and pushing the result).
operand.printStackCommands();
System.out.println(" Unary minus");
}
void printInfix() {
// Print the expression, in parentheses.
System.out.print("(-");
operand.printInfix();
System.out.print(')');
}
ExpNode derivative() {
// The derivative of -A is -(derivative of A).
return new UnaryMinusNode(operand.derivative());
}
}
/**
* An expression node that represents a reference to the variable, x.
*/
private static class VariableNode extends ExpNode {
VariableNode() {
// Construct a VariableNode. (There is nothing to do!)
}
double value(double xValue) {
// The value of the node is the value of x.
return xValue;
}
void printStackCommands() {
// On a stack machine, just push the value of X onto the stack.
System.out.println(" Push X");
}
void printInfix() {
System.out.print("x");
}
ExpNode derivative() {
// The derivative of x is the constant 1.
return new ConstNode(1);
}
}
// -------------------------------------------------------------------------------
/**
* An object of type ParseError represents a syntax error found in
* the user's input.
*/
private static class ParseError extends Exception {
ParseError(String message) {
super(message);
}
} // end nested class ParseError
public static void main(String[] args) {
while (true) {
System.out.println("\n\nEnter an expression, or press return to end.");
System.out.print("\n? ");
TextIO.skipBlanks();
if ( TextIO.peek() == '\n' )
break;
try {
ExpNode exp = expressionTree();
TextIO.skipBlanks();
if ( TextIO.peek() != '\n' )
throw new ParseError("Extra data after end of expression.");
TextIO.getln();
ExpNode deriv = exp.derivative();
System.out.println("\nA fully parenthesized expression for the derivative is:");
System.out.print(" ");
deriv.printInfix();
System.out.println();
System.out.println("\nValue of derivative at x = 0 is " + deriv.value(0));
System.out.println("Value of derivative at x = 1 is " + deriv.value(1));
System.out.println("Value of derivative at x = 2 is " + deriv.value(2));
System.out.println("Value of derivative at x = 3 is " + deriv.value(3));
System.out.println("\nOrder of postfix evaluation for derivative is:\n");
deriv.printStackCommands();
}
catch (ParseError e) {
System.out.println("\n*** Error in input: " + e.getMessage());
System.out.println("*** Discarding input: " + TextIO.getln());
}
}
System.out.println("\n\nDone.");
} // end main()
/**
* Reads an expression from the current line of input and builds
* an expression tree that represents the expression.
* @return an ExpNode which is a pointer to the root node of the
* expression tree
* @throws ParseError if a syntax error is found in the input
*/
private static ExpNode expressionTree() throws ParseError {
TextIO.skipBlanks();
boolean negative; // True if there is a leading minus sign.
negative = false;
if (TextIO.peek() == '-') {
TextIO.getAnyChar();
negative = true;
}
ExpNode exp; // The expression tree for the expression.
exp = termTree(); // Start with the first term.
if (negative)
exp = new UnaryMinusNode(exp);
TextIO.skipBlanks();
while ( TextIO.peek() == '+' || TextIO.peek() == '-' ) {
// Read the next term and combine it with the
// previous terms into a bigger expression tree.
char op = TextIO.getAnyChar();
ExpNode nextTerm = termTree();
exp = new BinOpNode(op, exp, nextTerm);
TextIO.skipBlanks();
}
return exp;
} // end expressionTree()
/**
* Reads a term from the current line of input and builds
* an expression tree that represents the expression.
* @return an ExpNode which is a pointer to the root node of the
* expression tree
* @throws ParseError if a syntax error is found in the input
*/
private static ExpNode termTree() throws ParseError {
TextIO.skipBlanks();
ExpNode term; // The expression tree representing the term.
term = factorTree();
TextIO.skipBlanks();
while ( TextIO.peek() == '*' || TextIO.peek() == '/' ) {
// Read the next factor, and combine it with the
// previous factors into a bigger expression tree.
char op = TextIO.getAnyChar();
ExpNode nextFactor = factorTree();
term = new BinOpNode(op,term,nextFactor);
TextIO.skipBlanks();
}
return term;
} // end termValue()
/**
* Reads a factor from the current line of input and builds
* an expression tree that represents the expression.
* @return an ExpNode which is a pointer to the root node of the
* expression tree
* @throws ParseError if a syntax error is found in the input
*/
private static ExpNode factorTree() throws ParseError {
TextIO.skipBlanks();
char ch = TextIO.peek();
if ( Character.isDigit(ch) ) {
// The factor is a number. Return a ConstNode.
double num = TextIO.getDouble();
return new ConstNode(num);
}
else if ( ch == 'x' || ch == 'X' ) {
// The factor is the variable x.
TextIO.getAnyChar(); // Read the X.
return new VariableNode();
}
else if ( ch == '(' ) {
// The factor is an expression in parentheses.
// Return a tree representing that expression.
TextIO.getAnyChar(); // Read the "("
ExpNode exp = expressionTree();
TextIO.skipBlanks();
if ( TextIO.peek() != ')' )
throw new ParseError("Missing right parenthesis.");
TextIO.getAnyChar(); // Read the ")"
return exp;
}
else if ( ch == '\n' )
throw new ParseError("End-of-line encountered in the middle of an expression.");
else if ( ch == ')' )
throw new ParseError("Extra right parenthesis.");
else if ( ch == '+' || ch == '-' || ch == '*' || ch == '/' )
throw new ParseError("Misplaced operator.");
else
throw new ParseError("Unexpected character \"" + ch + "\" encountered.");
} // end factorTree()
} // end class SimpleParser5