UQ Students should read the Disclaimer & Warning
Note: This page dates from 2005, and is kept for historical purposes.
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<!--
Copyright © 2004 Ned Martin
http://copyright.the-i.org/
Magic.
-->
<title>COMP2502 – Assignment 2 – Trees</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
</head>
<body>
<h1>COMP2502 – Assignment Two – Trees </h1>
<p>For which I achieved 96.45 out of 100. </p>
<p><a href="#spec">Specification</a> | <a href="#subm">My Submission</a> | <a href="#results">My
Results</a></p>
<h2 id="spec">Specification</h2>
<h3>Overall Goals</h3>
<p> The main focus of this assignment is the understanding of trees and the underlying
data structures and algorithms including the influence of preorder, inorder
and postorder traversal of trees.</p>
<p> The primary goal of this assignment is the programming of a simple integer
calculator. This calculator should read from a file, expression.txt, a simple
integer arithmetic expression where all of the input values are separated by
spaces. An example is the following expression:</p>
<textarea cols="82" rows="1" readonly="readonly"> ( 4 + 3 ) * 5 − ( 2 * 15 )</textarea>
<p> The expression should be parsed and simple mistakes detected. For example
if a ) is missing an error notice should be printed. The information contained
in the expression should be stored in an appropriate tree. The program should
then evaluate the expression and store the resulting value in the same tree
by using the equals sign as a binary operator. Finally the program should then
print out the equation that results from the evalution of the expression in
infix notation with all the appropriate symbols and parentheses included. For
our given example the appropriate equation would be:</p>
<textarea cols="82" rows="1" readonly="readonly"> ( ( ( 4 + 3 ) * 5 ) − ( 2 * 15 ) ) = 5</textarea>
<h3> Detailed Specifications</h3>
<p> Build a simple calculator that can perform the following functions:</p>
<ol>
<li> Parse a space separate expression from a file and check for the following:
<ol>
<li> matching parentheses,</li>
<li> the appropriate number of operands (numbers) for each operator (+,-,*,/).</li>
</ol>
</li>
<li> Store the expression in an appropriate tree.</li>
<li> Calculate the result of evaluating the expression. (This step can be done
with preorder or postorder transversal of the tree and appropriate java code.)</li>
<li> Store the equals sign as a binary operator in the tree and the result of
the evaluation as a leaf in the already constructed tree in (2).</li>
<li> Output the equation that results from the evaluation of the expression
in a fully-parenthesised version. (This can best be done with inorder transversal
of the tree.)</li>
</ol>
<p> The following names are specified to enable testing of the code:</p>
<textarea cols="82" rows="2" readonly="readonly">Input File expression.txt
Final Class Name Calculator.java</textarea>
<p> You are expected to submit the file Calculator.java and any other files that
your program needs to work. Your calculator will be tested with several different
expression.txt files to see if it satisfies the requirements of the assignment. </p>
<h3> Assessment Criteria</h3>
<p> Your assignment will be assessed on the following points:</p>
<ul>
<li> 30% on reading and parsing the space separated expression</li>
<li> 20% on the evaluation of the expression</li>
<li> 20% on the output of the appropriate equation.</li>
<li> 30% on the style and elegance of your code including the appropriate use
of trees.</li>
</ul>
<h2 id="subm">My Submission</h2>
Calculator.java<br />
<textarea cols="82" rows="599" readonly="readonly">/**
* @author Ned Martin.
* @version 30-SEP-2004-FINAL.
* @copyright Copyright (c) 2004 Ned Martin.
*
* @see http://nedmartin.org/uni/
*
* DESCRIPTION:
* Created for COMP2502 Assignment 2 at the University of
* Queensland by Ned Martin, #40529927.
*
* The main focus of this assignment is the understanding of trees
* and the underlying data structures and algorithms including the
* influence of preorder, inorder and postorder traversal of trees.
*
* The primary goal of this assignment is the programming of a
* simple integer calculator. This calculator should read from a
* file, expression.txt, a simple integer arithmetic expression
* where all of the input values are separated by spaces. An
* example is the following expression:
* ( 4 + 3 ) * 5 - ( 2 * 15 )
* The expression should be parsed and simple mistakes detected.
* For example if a ')' is missing an error notice should be
* printed. The information contained in the expression should be
* stored in an appropriate tree. The program should then evaluate
* the expression and store the resulting value in the same tree by
* using the equals sign as a binary operator. Finally the program
* should then print out the equation that results from the
* evalution of the expression in infix notation with all the
* appropriate symbols and parentheses included. For our given
* example the appropriate equation would be:
* ( ( ( 4 + 3 ) * 5 ) - ( 2 * 15 ) ) = 5
*
* NOTES:
* I have liberally handled whitespace. This program will accept
* input with or without one or more spaces, and attempt to parse
* it.
*
* USAGE:
* java Calculator [String filename | String expression]
*
* The program will attempt to read a file "expression.txt" if no
* commandline arguments are specified, otherwise it will atttempt
* to read the file given as an argument. If more than one argument
* is specified, the arguments will be assumed to be an expression
* and this program will attempt to parse them. Commandline
* expressions require 'x' to be used instead of '*' for
* multiplication.
*/
import java.io.BufferedReader;
import java.io.FileReader;
/**
* Provides methods next and peek to view characters from input.
*
* @author Ned Martin.
* @version 30-SEP-2004-FINAL.
*/
class InputReader
{
// buffer to hold input string.
private static String buffer = null;
// current position in input buffer.
private static int bufferPosition = 0;
/**
* Constructor accepting a String and storing it.
*
* @param String string to store.
*/
public InputReader(String input)
{
buffer = input;
}
/**
* Returns the next character from the input buffer without advancing
* the buffer position.
*
* @return char next character from input buffer.
*/
public static char peek()
{
// if we are at the end of the buffer.
if (bufferPosition == buffer.length())
{
return '\n';
}
// skip any leading white space.
while (buffer.charAt(bufferPosition) == ' ' ||
buffer.charAt(bufferPosition) == '\t')
{
// advance the buffer position.
bufferPosition++;
// if we are at the end of the buffer.
if (bufferPosition == buffer.length())
{
return '\n';
}
}
return buffer.charAt(bufferPosition);
} // end peek
/**
* Returns the next character from the input buffer and advances the
* buffer position.
*
* @return char next character from input buffer.
*/
public static char next()
{
char temp = peek();
// advance the buffer position.
bufferPosition++;
return temp;
} // end next
/**
* Get the current buffer value as a double.
* This function assumes that the next value is a double and should only
* be called after testing with peek().
*
* @return double next value in the buffer.
*/
public static double nextDouble()
{
String temp = "";
// build a string of consecutive integers.
while (bufferPosition < buffer.length() &&
Character.isDigit(buffer.charAt(bufferPosition)))
{
// concatenate current character to the previous one.
temp += buffer.charAt(bufferPosition);
// advance the buffer position.
bufferPosition++;
}
// return the double value of the concatenated characters.
return Double.valueOf(temp).doubleValue();
} // end nextDouble
} // end InputReader
/**
* An expression node used to make an expression tree.
*
* @author Ned Martin.
* @version 30-SEP-2004-FINAL.
*/
abstract class ExpressionNode
{
/**
* A method for finding the value held by a node.
*
* @return double value held by node.
*/
protected abstract double value();
} // end ExpressionNode
/**
* An expression node that holds a number value.
*
* @author Ned Martin.
* @version 30-SEP-2004-FINAL.
*/
class NumberNode extends ExpressionNode
{
private double number; // value held by this node.
/**
* Constructor that accepts a double value and stores it.
*
* @param double number value to store.
*/
NumberNode
(
double number // value to be stored in this node.
)
{
this.number = number;
} // end NumberNode
/**
* Returns the value held by this node.
*
* @return double value held by this node.
*/
protected double value()
{
return number;
} // end value
/**
* Returns a string representation of the value held by this node.
* The value is converted to an integer as we assume only integers are
* input.
*
* @return String representation of the value held by this node.
*/
public String toString()
{
// number is an integer value so print as an integer.
if ((number % 1) == 0)
{
return (int)number + "";
}
// number is not an integer value so print as a double.
else
{
return number + "";
}
} // end toString
} // end NumberNode
/**
* An expression node that holds a binary operator and pointers to child nodes.
*
* @author Ned Martin.
* @version 30-SEP-2004-FINAL.
*/
class BinaryOperatorNode extends ExpressionNode
{
char binaryOperator; // this node's operator.
ExpressionNode leftChild; // pointer to the left child node.
ExpressionNode rightChild; // pointer to the right child node.
/**
* Constructor that accepts a binary operator and two operands and
* stores them.
*
* @param char operator to store.
* @param ExpressionNode left child.
* @param ExpressionNode right child.
*/
BinaryOperatorNode
(
char binaryOperator, // the operator to store.
ExpressionNode leftChild, // pointer to the left child.
ExpressionNode rightChild // pointer to the right child.
)
{
this.binaryOperator = binaryOperator;
this.leftChild = leftChild;
this.rightChild = rightChild;
} // end BinaryOperatorNode
/**
* Returns the value of the left and right children after applying the
* binary operator of this node to them.
*
* @return double value held by this node.
*/
protected double value()
{
// value of the left child node.
double leftChildValue = leftChild.value();
// value of the right child node.
double rightChildValue = rightChild.value();
// apply this node's binary operator to the left and right
// children.
switch (binaryOperator)
{
case '+':
return leftChildValue + rightChildValue;
case '-':
return leftChildValue - rightChildValue;
case '*':
return leftChildValue * rightChildValue;
case '/':
return leftChildValue / rightChildValue;
// used for the root-level binary operator node
// as the result of the left child node is stored in the
// right child node so we could conceivably return
// either left or right child value here.
case '=':
return leftChildValue;
default:
// we should never get here but if we do,
// we die.
System.err.println("Invalid stored operator \""
+ binaryOperator + "\" found");
System.exit(1);
// we never get here.
return 0;
}
} // end value
/**
* Return a string representation of this node's operator and the values
* of its child nodes.
*
* @return String representation of the value of this node.
*/
public String toString()
{
// don't print brackets on the root-level equals binary
// operator node.
if (binaryOperator == '=')
{
return leftChild.toString() + " " + binaryOperator +
" " + rightChild.toString();
}
return "( " + leftChild.toString() + " " + binaryOperator +
" " + rightChild.toString() + " )";
} // end toString
} // end BinaryOperatorNode
/**
* Reads integers and binary operators and creates a binary parse tree, then
* calculates the mathetmatical value of the expression, stores that in the
* tree, and prints it out in infix order.
*
* @author Ned Martin.
* @version 30-SEP-2004-FINAL.
*/
public class Calculator {
/**
* Provides methods for reading input.
*/
private static InputReader inputReader;
/**
* Creates a new ParseError exception.
*
* @author Ned Martin
* @version 30-SEP-2004-FINAL
*/
private static class ParseError extends Exception
{
/**
* Creates and throws a new exception.
*
* @param String message to throw.
*/
ParseError(String message)
{
super(message);
}
} // end ParseError
/**
* Create and return an expression tree.
*
* @throws ParseError on invalid input.
*/
private static ExpressionNode expressionTree() throws ParseError
{
ExpressionNode expressionNode;
// create a term tree.
expressionNode = termTree();
// if there's any addition or subtraction operators.
while (inputReader.peek() == '+' || inputReader.peek() == '-')
{
// read the addition or subtraction operator.
char operator = inputReader.next();
// make a term tree for the right child of this node.
ExpressionNode rightChild = termTree();
// store the new term tree as the right child of a
// binary operator node with the original term tree as
// the left child.
expressionNode = new BinaryOperatorNode(operator,
expressionNode, rightChild);
}
// return the binary operator node.
return expressionNode;
} // end expressionTree
/**
* Create and return a term tree.
*
* @throws ParseError on invalid input.
*/
private static ExpressionNode termTree() throws ParseError
{
ExpressionNode expressionNode;
// create a number tree.
expressionNode = numberTree();
// if there's any multiplication or division operators.
while (inputReader.peek() == '*' || inputReader.peek() == '/')
{
// read the addition or multiplication operator.
char operator = inputReader.next();
// make a number tree for the right child of this node.
ExpressionNode rightChild = numberTree();
// store the new number tree as the right child of a
// binary operator node with the original number tree as
// the left child.
expressionNode = new BinaryOperatorNode(operator,
expressionNode, rightChild);
}
// return the binary operator node.
return expressionNode;
} // end termTree
/**
* Creates a final number node for the tree or recursively creates a new
* expression tree if it encounters a bracketed term.
*
* @throws ParseError on invalid input.
*/
private static ExpressionNode numberTree() throws ParseError
{
// if character is a digit, make and return a number node.
if (Character.isDigit(inputReader.peek()))
{
// return a number node.
return new NumberNode(inputReader.nextDouble());
}
switch (inputReader.peek())
{
// the term is a bracketed expression.
case '(':
// get the '(' and throw it out.
inputReader.next();
// make a new expression tree.
ExpressionNode expressionNode =
expressionTree();
// expect a closing right bracket to close the
// starting left bracket.
if (inputReader.peek() != ')')
{
throw new ParseError("Missing right " +
"bracket.");
}
// get the ')' and throw it out.
inputReader.next();
// return the expression tree.
return expressionNode;
// unexpected new line found.
case '\n':
throw new ParseError("Unexpected line end " +
"found.");
// unexpected right bracket found.
case ')':
throw new ParseError("Unexpected right " +
"bracket found.");
// unexpected operator found.
case '+':
case '-':
case '*':
case '/':
throw new ParseError("Unexpected operator " +
"found.");
// unexpected character found.
default:
throw new ParseError("Unexpected character \"" +
inputReader.peek() + "\" found.");
}
} // end numberTree
/**
* Main method.
*
* @param [String filename to read
* | String expression to evalulate]
*/
public static void main(String[] args)
{
String fileName = "expression.txt", // default filename.
input = ""; // holds input.
switch (args.length)
{
// reading from specified file or standard in.
case 1:
fileName = args[0];
// reading from default file.
case 0:
try
{
// get a line from a file.
input = new BufferedReader(new
FileReader(fileName)).readLine()
;
}
catch (Exception e)
{
System.err.println("Unable to open " +
"input file \""+ fileName +
"\" for reading.");
System.exit(1);
}
break;
// reading from command line.
default:
// loop through the arguments and turn
// them into a string.
for (int ii = 0; ii < args.length; ii++)
{
if (args[ii].equals("x"))
{
// replace 'x' with '*'.
input += "* ";
}
else
{
input += args[ii] + " ";
}
}
break;
}
// create a new input reader to parse input.
inputReader = new InputReader(input);
try
{
ExpressionNode expressionNode = expressionTree();
ExpressionNode answerNode =
new NumberNode(expressionNode.value());
// create a root level binary tree.
// [expression_tree] [= operator] [answer_node]
ExpressionNode rootNode = new BinaryOperatorNode('=',
expressionNode, answerNode);
// test for extra unexpected data after end of
// expression.
if (inputReader.peek() != '\n')
{
throw new ParseError("Unexpected data \"" +
inputReader.peek() + "\" found.");
}
// print a string representation of an infix parse
// through the expression tree.
System.out.println(rootNode);
}
catch (ParseError e)
{
System.err.println("Invalid input: " +
e.getMessage() +
" Discarding \"" + input + "\"");
}
} // end main
} // end class Calculator</textarea>
<h2 id="results">My Results</h2>
<table cellspacing="0" cellpadding="0">
<tr>
<td colspan="2"><strong>Assignment 2 </strong></td>
<td>Not recorded </td>
</tr>
<tr>
<td colspan="2"><strong>Part A (70%) </strong></td>
<td>66 </td>
</tr>
<tr>
<td colspan="2"><strong>Part B (30%) </strong></td>
<td>25.4545454545455 </td>
</tr>
<tr>
<td colspan="2"><strong>Comments </strong></td>
<td>Operator missing error not identified correctly </td>
</tr>
<tr>
<td colspan="2"><strong>Bonus </strong></td>
<td>5 </td>
</tr>
<tr>
<td colspan="2"><strong>Total </strong></td>
<td>96.4545454545455 </td>
</tr>
</table>
<p>27-Dec-2004</p>
</body>
</html>