Solution for
Programming Exercise 11.6
THIS PAGE DISCUSSES ONE POSSIBLE SOLUTION to the following exercise from this on-line Java textbook.
Exercise 11.6: The parsing programs in Section 11.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.
Discussion
Like the other expression node classes, the VariableNode class is a subclass of ExpNode, and it must implement the value() and printStackCommands() methods that it inherits from that class. The value() 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 actually 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:
class VariableNode extends ExpNode { // An expression node that represents a reference to the variable, x. 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.
The Solution
Changes from SimpleParser3.java, from Section 11.5, are shown in red.
/* This program reads standard expressions typed in by the user. The expressions can contain the variable "x", in addition to positive numbers and the operators +, -, *, and /. The program constructs an expression tree to represent the expression. It then prints the value of the tree at several values of the variable x. 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 are defined by the BNF rules: <expression> ::= [ "-" ] <term> [ [ "+" | "-" ] <term> ]... <term> ::= <factor> [ [ "*" | "/" ] <factor> ]... <factor> ::= <number> | <variable-x> | "(" <expression> ")" <variable-x> represents the variable, which can be written as either an upper case or lower case "x". 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, SimpleParser4, this program defines a set of four classes for implementing expression trees. (I know that it's not very good style to have them here...) */ //-------------------- Classes for Expression Trees ------------------------------ abstract class ExpNode { // An abstract class representing any node in an expression tree. // The following three concrete node classes are subclasses. // Two instance methods are specified, so that they can be used with // any ExpNode. The value() method returns the value of the // expression at 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 double value(double xValue); abstract void printStackCommands(); } class VariableNode extends ExpNode { // An expression node that represents a reference to the variable, x. 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"); } } class ConstNode extends ExpNode { // An expression node that holds a number. 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, // no matter what the value of the variable x. return number; } void printStackCommands() { // On a stack machine, just push the number onto the stack. TextIO.putln(" Push " + number); } } class BinOpNode extends ExpNode { // An expression node representing a binary operator, 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. 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(); TextIO.putln(" Operator " + op); } } class UnaryMinusNode extends ExpNode { // An expression node to represent a unary minus operator. ExpNode operand; // The operand to which the unary minus applies. UnaryMinusNode(ExpNode operand) { // Construct a UnaryMinusNode with the specified operand. 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"); } } //------------------------------------------------------------------------ public class SimpleParser4 { static class ParseError extends Exception { // Represents a syntax error found in the user's input. 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? "); skipBlanks(); if ( TextIO.peek() == '\n' ) break; try { ExpNode exp = expressionTree(); 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() static void skipBlanks() { // Skip past any spaces and tabs on the current line of input. // Stop at a non-blank character or end-of-line. while ( TextIO.peek() == ' ' || TextIO.peek() == '\t' ) TextIO.getAnyChar(); } static ExpNode expressionTree() throws ParseError { // Read an expression from the current line of input and // return an expression tree representing the expression. 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); 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); skipBlanks(); } return exp; } // end expressionTree() static ExpNode termTree() throws ParseError { // Read a term from the current line of input and // return an expression tree representing the term. skipBlanks(); ExpNode term; // The expression tree representing the term. term = factorTree(); 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); skipBlanks(); } return term; } // end termTree() static ExpNode factorTree() throws ParseError { // Read a factor from the current line of input and // return an expression tree representing the factor. 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. TextIO.getAnyChar(); // Read the "(" ExpNode exp = expressionTree(); 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 SimpleParser4
[ Exercises | Chapter Index | Main Index ]