COMP2502 – Assignment Two – Trees

For which I achieved 96.45 out of 100.

Specification | My Submission | My Results

Specification

Overall Goals

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

Detailed Specifications

Build a simple calculator that can perform the following functions:

Parse a space separate expression from a file and check for the following:
1. matching parentheses,
2. the appropriate number of operands (numbers) for each operator (+,-,*,/).
Store the expression in an appropriate tree.
Calculate the result of evaluating the expression. (This step can be done with preorder or postorder transversal of the tree and appropriate java code.)
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).
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.)

The following names are specified to enable testing of the code:

Input File expression.txt
Final Class Name Calculator.java

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.

Assessment Criteria

Your assignment will be assessed on the following points:

30% on reading and parsing the space separated expression
20% on the evaluation of the expression
20% on the output of the appropriate equation.
30% on the style and elegance of your code including the appropriate use of trees.

My Submission

Calculator.java

/**
 * @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

My Results

Assignment 2		Not recorded
Part A (70%)		66
Part B (30%)		25.4545454545455
Comments		Operator missing error not identified correctly
Bonus		5
Total		96.4545454545455

27-Dec-2004