Solution for
Programming Exercise 12.6
THIS PAGE DISCUSSES ONE POSSIBLE SOLUTION to
the following exercise from this on-line
Java textbook.
Exercise 12.6:
The sample program SimpleParser5.java
from Section 12.4 can handle expressions that contain
variables, numbers, operators, and parentheses. Extend this program so that
it can also handle the standard mathematical functions sin, cos,
tan, abs, sqrt, and log. For example, the program should
be able to evaluate an expression such as sin(3*x-7)+log(sqrt(y)),
assuming that the variables x and y have been given values.
In the original program, a symbol table holds a value for each variable that
has been defined. In your program, you should add another type of symbol to
the table to represent standard functions. You can use objects belonging
to the following class:
class StandardFunction {
// An object of this class represents
// one of the standard functions.
static final int SIN = 0, COS = 1, // Code numbers for each
TAN = 2, ABS = 3, // of the functions.
SQRT = 4, LOG = 5;
int functionCode; // Tells which function this is.
// The value is one of the above codes.
StandardFunction(int code) {
// Constructor creates the standard function specified
// by the given code, which should be one of the
// above code numbers.
functionCode = code;
}
double evaluate(double x) {
// Finds the value of this function for the
// specified parameter value, x.
switch(functionCode) {
case SIN:
return Math.sin(x);
case COS:
return Math.cos(x);
case TAN:
return Math.tan(x);
case ABS:
return Math.abs(x);
case SQRT:
return Math.sqrt(x);
default:
return Math.log(x);
}
}
} // end class StandardFunction
Add a symbol to the symbol table to represent each function.
The key is the name of the function and the value is an object
of type StandardFunction that represents the function.
For example:
symbolTable.put("sin", new StandardFunction(StandardFunction.SIN));
In your parser, when you encounter a word, you have to be able to
tell whether it's a variable or a standard function. Look up the
word in the symbol table. If the associated value is non-null
and is of type Double, then the word is a variable.
If it is of type StandardFunction, then
the word is a function. Remember that you can test the type
of an object using the instanceof operator.
For example: if (obj instanceof Double)
Discussion
The changes that must be made to SimpleParser5.java are remarkably
small, aside from defining the StandardFunction class. In my
solution, I included this class as a static nested class in my main
program class. It would also make sense to define it as a separate
class.
I added six lines of code at the beginning of the main() routine
to add the six standard functions to the main routine. These lines are
all similar to the one given in the exercise.
The only other change is in the parsing routines. (The use of the
symbol table has changed conceptually, since now it contains standard
fucntions as well as variables. However, this does not require any
change in the programming.) The change is in the primaryValue()
method. When a word is encountered, the computer must check whether
the word is a variable or a standard fucntion. This is done, as suggested
in the exercise, by looking up the word in the symbol table and
checking the type of the associated value. If the word is a standard
function, then we have to read and evaluate the argument of the
fucntion:
else if ( Character.isLetter(ch) ) {
// The factor is a variable. Read its name and
// look up its value in the symbol table. If the
// variable is not in the symbol table, an error
// occurs. (Note that the values in the symbol
// table are objects of type Double.)
String name = readWord();
Object symbolTableEntry = symbolTable.get(name);
if (symbolTableEntry == null)
throw new ParseError("Unknown symbol \"" + name + "\"");
if (symbolTableEntry instanceof Double) {
// The symbol is a variable. The value of the
// variable is the double number containd in the
// symbolTableEntry
Double val = (Double)symbolTableEntry;
return val.doubleValue();
}
else {
// The only other possibility is a standard function.
// We have to evaluate the argument of the function,
// and then apply the function to that argument.
StandardFunction func = (StandardFunction)symbolTableEntry;
skipBlanks();
if ( TextIO.peek() != '(' ) {
// The function name should have been followed
// by the argument of the function, in parentheses.
throw new ParseError("Missing left parenthesis after function name.");
}
TextIO.getAnyChar(); // Read the '('
double argumentValue = expressionValue();
skipBlanks();
if ( TextIO.peek() != ')' ) {
// There must be a right parenthesis after the argument.
throw new ParseError("Missing right parenthesis after function argument.");
}
TextIO.getAnyChar(); // Read the ')'
return func.evaluate(argumentValue);
}
}
There is one additional change that I might have made. As the
program stands, it allows the user to use a "let" command to assign
a value to one of the standard fucntion names. For example:
"let sin = 42". This effectively changes
the name so that it is a variable, and the standard function is no longer
available for use in expressions. It might be better to give an error
message if the user tries to assign a value to a standard function name.
This could be done in the doLetCommand() method:
static void doLetCommand() throws ParseError {
// Process a command of the form let <variable> = <expression>.
// When this method is called, the word "let" has already
// been read. Read the variable name and the expression, and
// store the value of the variable in the symbol table.
skipBlanks();
if ( ! Character.isLetter(TextIO.peek()) )
throw new ParseError("Expected variable name after 'let'.");
String name = readWord(); // The name of the variable.
Object symbol = symbolTable.get(name);
if (symbol != null && symbol instanceof StandardFunction)
throw new ParseError("Can't assign a value to a standard function name.");
skipBlanks();
if ( TextIO.peek() != '=' )
throw new ParseError("Expected '=' operator for 'let' command.");
TextIO.getChar();
double val = expressionValue(); // The value of the variable.
skipBlanks();
if ( TextIO.peek() != '\n' )
throw new ParseError("Extra data after end of expression.");
symbolTable.put(name, new Double(val)); // Add to symbol table.
TextIO.putln("ok");
}
The Solution
Changes from SimpleParser5.java are shown in red.
/*
This program can evaluate expressions that can include
numbers, variables, parentheses, and the operators +,
-, *, /, and ^ (where ^ indicates raising to a power).
It can also use the standard mathematical functions
sin, cos, tan, abs, log, and sqrt.
A variable name must consist of letters and digits,
beginning with a letter. Names are case-sensitive.
This program accepts commands of two types from the user.
For a command of the form print <expression> , the expression
is evaluated and the value is output. For a command of
the form let <variable> = <expression> , the expression is
evaluated and the value is assigned to the variable.
If a variable is used in an expression before it has been
assigned a value, an error occurs. A number must begin with
a digit (i.e., not a decimal point).
Commands are formally defined by the BNF rules:
<command> ::= "print" <expression>
| "let" <variable> "=" <expression>
<expression> ::= [ "-" ] <term> [ [ "+" | "-" ] <term> ]...
<term> ::= <factor> [ [ "*" | "/" ] <factor> ]...
<factor> ::= <primary> [ "^" <primary> ]...
<primary> ::= <number> | <variable>
| "(" <expression> ")"
| <function-name> "(" <expression> ")"
A line of input must contain exactly one such command. If extra
data is found on a line after an expression has been read, it is
considered an error. The variables "pi" and "e" are defined
when the program starts to represent the usual mathematical
constants.
This program demonstrates the use of a HashMap as a symbol
table.
SimpleParser6.java is based on the program SimpleParser5.java.
It requires a non-standard class, TextIO.
*/
import java.util.HashMap;
public class SimpleParser6 {
static class ParseError extends Exception {
// Represents a syntax error found in the user's input.
ParseError(String message) {
super(message);
}
} // end nested class ParseError
static class StandardFunction {
// An object of this class represents
// one of the standard functions.
static final int SIN = 0, COS = 1, // Code numbers for each
TAN = 2, ABS = 3, // of the functions.
SQRT = 4, LOG = 5;
int functionCode; // Tells which function this is.
// The value is one of the above codes.
StandardFunction(int code) {
// Constructor creates the standard function specified
// by the given code, which should be one of the
// above code numbers.
functionCode = code;
}
double evaluate(double x) {
// Finds the value of this function for the
// specified parameter value, x.
switch(functionCode) {
case SIN:
return Math.sin(x);
case COS:
return Math.cos(x);
case TAN:
return Math.tan(x);
case ABS:
return Math.abs(x);
case SQRT:
return Math.sqrt(x);
default:
return Math.log(x);
}
}
} // end nested class StandardFunction
static HashMap symbolTable = new HashMap();
// The symbolTable contains information about symbols
// that can be used in expressions. These symbols
// include variables and the names of the standard
// functions. The names of the symbols are used as
// keys in the hash table. For a variable, the associated
// value is an object of type Double that contains the
// value of the variable. For a function, the
// associated value is an object belonging to the
// nested class StandardFunction.
public static void main(String[] args) {
// To start, add variables named "pi" and "e" to the
// symbol tables. Their values are the usual
// mathematical constants.
symbolTable.put("pi", new Double(Math.PI));
symbolTable.put("e", new Double(Math.E));
// Add objects to the symbol table to represent each
// of the six standard functions.
symbolTable.put("sin", new StandardFunction(StandardFunction.SIN));
symbolTable.put("cos", new StandardFunction(StandardFunction.COS));
symbolTable.put("tan", new StandardFunction(StandardFunction.TAN));
symbolTable.put("abs", new StandardFunction(StandardFunction.ABS));
symbolTable.put("log", new StandardFunction(StandardFunction.LOG));
symbolTable.put("sqrt", new StandardFunction(StandardFunction.SQRT));
// Read and process commands from the user.
TextIO.putln("\n\nEnter commands; press return to end.");
TextIO.putln("Commands must have the form:\n");
TextIO.putln(" print <expression>");
TextIO.putln(" or");
TextIO.putln(" let <variable> = <expression>");
while (true) {
TextIO.put("\n? ");
skipBlanks();
if ( TextIO.peek() == '\n' )
break;
try {
String command = TextIO.getWord();
if (command.equalsIgnoreCase("print"))
doPrintCommand();
else if (command.equalsIgnoreCase("let"))
doLetCommand();
else
throw new ParseError("Command must begin with 'print' or 'let'.");
TextIO.getln();
}
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 void doLetCommand() throws ParseError {
// Process a command of the form let <variable> = <expression>.
// When this method is called, the word "let" has already
// been read. Read the variable name and the expression, and
// store the value of the variable in the symbol table.
skipBlanks();
if ( ! Character.isLetter(TextIO.peek()) )
throw new ParseError("Expected variable name after 'let'.");
String name = readWord(); // The name of the variable.
skipBlanks();
if ( TextIO.peek() != '=' )
throw new ParseError("Expected '=' operator for 'let' command.");
TextIO.getChar();
double val = expressionValue(); // The value of the variable.
skipBlanks();
if ( TextIO.peek() != '\n' )
throw new ParseError("Extra data after end of expression.");
symbolTable.put(name, new Double(val)); // Add to symbol table.
TextIO.putln("ok");
}
static void doPrintCommand() throws ParseError {
// Process a command of the form print <expression>.
// When this method is called, the word "print" has already
// been read. Evaluate the expression and print the value.
double val = expressionValue();
skipBlanks();
if ( TextIO.peek() != '\n' )
throw new ParseError("Extra data after end of expression.");
TextIO.putln("Value is " + val);
}
static double expressionValue() throws ParseError {
// Read an expression from the current line of input and
// return its value.
skipBlanks();
boolean negative; // True if there is a leading minus sign.
negative = false;
if (TextIO.peek() == '-') {
TextIO.getAnyChar();
negative = true;
}
double val; // Value of the expression.
val = termValue(); // An expression must start with a term.
if (negative)
val = -val; // Apply the leading minus sign
skipBlanks();
while ( TextIO.peek() == '+' || TextIO.peek() == '-' ) {
// Read the next term and add it to or subtract it from
// the value of previous terms in the expression.
char op = TextIO.getAnyChar();
double nextVal = termValue();
if (op == '+')
val += nextVal;
else
val -= nextVal;
skipBlanks();
}
return val;
} // end expressionValue()
static double termValue() throws ParseError {
// Read a term from the current line of input and
// return its value.
skipBlanks();
double val; // The value of the term.
val = factorValue(); // A term must start with a factor.
skipBlanks();
while ( TextIO.peek() == '*' || TextIO.peek() == '/' ) {
// Read the next factor, and multiply or divide
// the value-so-far by the value of this factor.
char op = TextIO.getAnyChar();
double nextVal = factorValue();
if (op == '*')
val *= nextVal;
else
val /= nextVal;
skipBlanks();
}
return val;
} // end termValue()
static double factorValue() throws ParseError {
// Read a factor from the current line of input and
// return its value.
skipBlanks();
double val; // Value of the factor.
val = primaryValue(); // A factor must start with a primary.
skipBlanks();
while ( TextIO.peek() == '^' ) {
// Read the next primary, and exponentiate
// the value-so-far by the value of this primary.
TextIO.getChar();
double nextVal = primaryValue();
val = Math.pow(val,nextVal);
if (Double.isNaN(val))
throw new ParseError("Illegal values for ^ operator.");
skipBlanks();
}
return val;
} // end termValue()
static double primaryValue() throws ParseError {
// Read a primary from the current line of input and
// return its value. A primary must be a number,
// a variable, an expression enclosed in parentheses,
// or a standard function name followed by an expression
// in parentheses.
skipBlanks();
char ch = TextIO.peek();
if ( Character.isDigit(ch) ) {
// The factor is a number. Read it and
// return its value.
return TextIO.getDouble();
}
else if ( Character.isLetter(ch) ) {
// The factor is a variable. Read its name and
// look up its value in the symbol table. If the
// variable is not in the symbol table, an error
// occurs. (Note that the values in the symbol
// table are objects of type Double.)
String name = readWord();
Object symbolTableEntry = symbolTable.get(name);
if (symbolTableEntry == null)
throw new ParseError("Unknown symbol \"" + name + "\"");
if (symbolTableEntry instanceof Double) {
// The symbol is a variable. The value of the
// variable is the double number containd in the
// symbolTableEntry
Double val = (Double)symbolTableEntry;
return val.doubleValue();
}
else {
// The only other possibility is a standard function.
// We have to evaluate the argument of the function,
// and then apply the function to that argument.
StandardFunction func = (StandardFunction)symbolTableEntry;
skipBlanks();
if ( TextIO.peek() != '(' ) {
// The function name should have been followed
// by the argument of the function, in parentheses.
throw new ParseError("Missing left parenthesis after function name.");
}
TextIO.getAnyChar(); // Read the '('
double argumentValue = expressionValue();
skipBlanks();
if ( TextIO.peek() != ')' ) {
// There must be a right parenthesis after the argument.
throw new ParseError("Missing right parenthesis after function argument.");
}
TextIO.getAnyChar(); // Read the ')'
return func.evaluate(argumentValue);
}
}
else if ( ch == '(' ) {
// The factor is an expression in parentheses.
// Return the value of the expression.
TextIO.getAnyChar(); // Read the "("
double val = expressionValue();
skipBlanks();
if ( TextIO.peek() != ')' )
throw new ParseError("Missing right parenthesis.");
TextIO.getAnyChar(); // Read the ")"
return val;
}
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.");
}
static String readWord() {
// Reads a word from input. A word is any sequence of
// letters and digits, starting with a letter. When
// this subroutine is called, it should already be
// known that the next character in the input is
// a letter.
String word = ""; // The word.
char ch = TextIO.peek();
while (Character.isLetter(ch) || Character.isDigit(ch)) {
word += TextIO.getChar(); // Add the character to the word.
ch = TextIO.peek();
}
return word;
}
} // end class SimpleParser6
[ Exercises
| Chapter Index
| Main Index
]
