Solution for Programmming Exercise 9.6
This page contains a sample solution to one of the exercises from Introduction to Programming Using Java.
Exercise 9.6:
The parsing programs in Section 9.5 work with expressions made up of numbers and operators. We can make things a little more interesting by allowing the variable "x" to occur. This would allow expression such as "3*(x-1)*(x+1)", for example. Make a new version of the sample program SimpleParser3.java that can work with such expressions. In your program, the main() routine can't simply print the value of the expression, since the value of the expression now depends on the value of x. Instead, it should print the value of the expression for x=0, x=1, x=2, and x=3.
The original program will have to be modified in several other ways. Currently, the program uses classes ConstNode, BinOpNode, and UnaryMinusNode to represent nodes in an expression tree. Since expressions can now include x, you will need a new class, VariableNode, to represent an occurrence of x in the expression.
In the original program, each of the node classes has an instance method, "double value()", which returns the value of the node. But in your program, the value can depend on x, so you should replace this method with one of the form "double value(double xValue)", where the parameter xValue is the value of x.
Finally, the parsing subroutines in your program will have to take into account the fact that expressions can contain x. There is just one small change in the BNF rules for the expressions: A <factor> is allowed to be the variable x:
<factor> ::= <number> | <x-variable> | "(" <expression> ")"
where <x-variable> can be either a lower case or an upper case "X". This change in the BNF requires a change in the factorTree() subroutine.
Like the other expression node classes, the VariableNode class is a subclass of ExpNode, and it must implement the value(x) and printStackCommands() methods that it inherits from that class. The value(x) method has been modified to have a parameter of type double, which gives the value of the variable x. Since a VariableNode represents an occurrence of the variable x, the value of the node is simply the value of x. As for the stack commands to evaluate the node: When we encounter an x in an expression, we need to push the value of x onto the stack, just as we would push a constant value onto the stack. I represent this with a stack operation "Push X". Note that x can have different values at different times, so we can't say what value will be pushed. We are generating instructions for a stack machine. At the time when the stack machine evaluates the expression, it has to know the value of x. The "Push X" command tells it to push a copy of that value onto the stack. The VariableNode class is defined as:
/**
* 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.
TextIO.putln(" Push X");
}
}
One curious thing about this class is that it doesn't have any instance variables. A VariableNode represents an occurrence of x. There is no other information to record. It's not like a ConstNode where we need an instance variable to tell us which numerical constant has been found. There is only one "x". Of course, if we expanded our definition of expression to allow other variables such as y and z, we might add an instance variable to VariableNode to say which of the possible variables is represented.
The factorTree() subroutine from SimpleParser3.java has to be modified to check for an x. If it finds one, it has to return a new VariableNode. This change and the others you have to make are fairly straightforward. They are shown in red in the solution that follows.
/*
This program reads standard expressions typed in by the user.
The program constructs an expression tree to represent the
expression. It then prints the value of the tree. It also uses
the tree to print out a list of commands that could be used
on a stack machine to evaluate the expression.
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 addtion to the main program class, SimpleParser4, this program
defines a set of five nested classes for implementing expression trees.
*/
public class SimpleParser4 {
// -------------------- Nested classes for Expression Trees ------------------------------
/**
* An abstract class representing any node in an expression tree.
* The three 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).
*/
abstract private static class ExpNode {
abstract double value(double xValue);
abstract void printStackCommands();
}
/**
* Represents en 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.
TextIO.putln(" Push " + number);
}
}
/**
* 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 evalute 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();
TextIO.putln(" Operator " + op);
}
}
/**
* 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();
TextIO.putln(" Unary minus");
}
}
/**
* 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.
TextIO.putln(" Push X");
}
}
// -------------------------------------------------------------------------------
/**
* 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) {
TextIO.putln("\n\nEnter an expression, or press return to end.");
TextIO.put("\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();
TextIO.putln("\nValue at x = 0 is " + exp.value(0));
TextIO.putln("Value at x = 1 is " + exp.value(1));
TextIO.putln("Value at x = 2 is " + exp.value(2));
TextIO.putln("Value at x = 3 is " + exp.value(3));
TextIO.putln("\nOrder of postfix evaluation is:\n");
exp.printStackCommands();
}
catch (ParseError e) {
TextIO.putln("\n*** Error in input: " + e.getMessage());
TextIO.putln("*** Discarding input: " + TextIO.getln());
}
}
TextIO.putln("\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 SimpleParser3