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 Martinhttp://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 &ndash; Assignment Two &ndash; 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.txtFinal 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 &quot;expression.txt&quot; 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 = &quot;&quot;;        // build a string of consecutive integers.        while (bufferPosition &lt; buffer.length() &amp;&amp;            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 + &quot;&quot;;        }        // number is not an integer value so print as a double.        else        {            return number + &quot;&quot;;        }    } // 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(&quot;Invalid stored operator \&quot;&quot;                    + binaryOperator + &quot;\&quot; found&quot;);                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() + &quot; &quot; + binaryOperator +                &quot; &quot; + rightChild.toString();        }        return &quot;( &quot; + leftChild.toString() + &quot; &quot; + binaryOperator +            &quot; &quot; + rightChild.toString() + &quot; )&quot;;    } // 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(&quot;Missing right &quot; +                        &quot;bracket.&quot;);                }                // get the ')' and throw it out.                inputReader.next();                // return the expression tree.                return expressionNode;            // unexpected new line found.            case '\n':                throw new ParseError(&quot;Unexpected line end &quot; +                    &quot;found.&quot;);            // unexpected right bracket found.            case ')':                throw new ParseError(&quot;Unexpected right &quot; +                     &quot;bracket found.&quot;);            // unexpected operator found.            case '+':            case '-':            case '*':            case '/':                throw new ParseError(&quot;Unexpected operator &quot; +                    &quot;found.&quot;);            // unexpected character found.            default:                throw new ParseError(&quot;Unexpected character \&quot;&quot; +                    inputReader.peek() + &quot;\&quot; found.&quot;);        }    } // end numberTree    /**     * Main method.     *     * @param    [String filename to read     *        | String expression to evalulate]     */    public static void main(String[] args)    {        String    fileName = &quot;expression.txt&quot;,    // default filename.            input = &quot;&quot;;            // holds input.        switch (args.length)        {            // reading from specified file or standard in.            case 1:                fileName = args;            // 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(&quot;Unable to open &quot; +                        &quot;input file \&quot;&quot;+ fileName +                        &quot;\&quot; for reading.&quot;);                    System.exit(1);                }                break;            // reading from command line.            default:                // loop through the arguments and turn                // them into a string.                for (int ii = 0; ii &lt; args.length; ii++)                {                    if (args[ii].equals(&quot;x&quot;))                    {                        // replace 'x' with '*'.                        input += &quot;* &quot;;                    }                    else                    {                        input += args[ii] + &quot; &quot;;                    }                }            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(&quot;Unexpected data \&quot;&quot; +                    inputReader.peek() + &quot;\&quot; found.&quot;);            }            // print a string representation of an infix parse            // through the expression tree.            System.out.println(rootNode);        }        catch (ParseError e)        {            System.err.println(&quot;Invalid input: &quot; +                e.getMessage() +                &quot; Discarding \&quot;&quot; + input + &quot;\&quot;&quot;);        }    } // 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> ```