{"id":186,"date":"2021-01-02T16:57:46","date_gmt":"2021-01-02T16:57:46","guid":{"rendered":"https:\/\/bhiggs.x10hosting.com\/practical-java-programming\/?page_id=186"},"modified":"2021-01-02T17:34:05","modified_gmt":"2021-01-02T17:34:05","slug":"assignment-6","status":"publish","type":"page","link":"https:\/\/bhiggs.x10hosting.com\/PracticalJavaProgramming\/assignments\/assignment-6\/","title":{"rendered":"Assignment 6"},"content":{"rendered":"<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_85 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Table of Contents<\/p>\n<label for=\"ez-toc-cssicon-toggle-item-6a6d453e2082b\" class=\"ez-toc-cssicon-toggle-label\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/label><input type=\"checkbox\"  id=\"ez-toc-cssicon-toggle-item-6a6d453e2082b\"  aria-label=\"Toggle\" \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/bhiggs.x10hosting.com\/PracticalJavaProgramming\/assignments\/assignment-6\/#Abstract_Syntax_Trees\" >Abstract Syntax Trees<\/a><ul class='ez-toc-list-level-4' ><li class='ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/bhiggs.x10hosting.com\/PracticalJavaProgramming\/assignments\/assignment-6\/#Description\" >Description<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/bhiggs.x10hosting.com\/PracticalJavaProgramming\/assignments\/assignment-6\/#The_Assignment\" >The Assignment<\/a><ul class='ez-toc-list-level-4' ><li class='ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/bhiggs.x10hosting.com\/PracticalJavaProgramming\/assignments\/assignment-6\/#Part_1_Integer_UnaryMinus_Plus_and_Times\" >Part 1: Integer,&nbsp;UnaryMinus,&nbsp;Plus&nbsp;and&nbsp;Times<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/bhiggs.x10hosting.com\/PracticalJavaProgramming\/assignments\/assignment-6\/#Part_2_Adding_More_Node_Types\" >Part 2: Adding More Node Types<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/bhiggs.x10hosting.com\/PracticalJavaProgramming\/assignments\/assignment-6\/#Part_3_Teaching_walk_to_correctly_parenthesize\" >Part 3: Teaching\u00a0walk()\u00a0to correctly parenthesize<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/bhiggs.x10hosting.com\/PracticalJavaProgramming\/assignments\/assignment-6\/#Part_1_Integer_UnaryMinus_Plus_and_Times-2\" >Part 1: Integer, UnaryMinus, Plus and Times<\/a><ul class='ez-toc-list-level-4' ><li class='ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/bhiggs.x10hosting.com\/PracticalJavaProgramming\/assignments\/assignment-6\/#Sequence_of_steps_to_perform\" >Sequence of steps to perform:<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/bhiggs.x10hosting.com\/PracticalJavaProgramming\/assignments\/assignment-6\/#Part_2_Adding_More_Node_Types-2\" >Part 2: Adding More Node Types<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-10\" href=\"https:\/\/bhiggs.x10hosting.com\/PracticalJavaProgramming\/assignments\/assignment-6\/#Part_3_Teaching_walk_to_Correctly_Parenthesize\" >Part 3: Teaching\u00a0walk()\u00a0to Correctly Parenthesize<\/a><\/li><\/ul><\/nav><\/div>\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Abstract_Syntax_Trees\"><\/span>Abstract Syntax Trees<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<h4 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Description\"><\/span>Description<span class=\"ez-toc-section-end\"><\/span><\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Various programs (such as compilers and calculators), use a data structure called an&nbsp;<strong><em>Abstract Syntax Tree (AST)<\/em><\/strong>&nbsp;to represent syntax that has been recognized by the program.<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p><em><strong><u>Note:<\/u><\/strong><\/em> An Abstract Syntax Tree is&nbsp;<strong>not&nbsp;<\/strong>the same as a Binary Search Tree.<br>In a Binary Search Tree, both interior and leaf nodes can contain data, and the nodes are ordered in such a way that the data can be found by searching the tree in a prescribed order. In an Abstract Syntax Tree, the interior nodes contain&nbsp;<em>operator&nbsp;<\/em>information, while the leaf nodes contain&nbsp;<em>operand&nbsp;<\/em>information.<br>The order of the nodes within a Binary Search Tree is determined by the contents of each node. The order of the nodes in an AST is determined by the expression that the AST represents, and by the precedence of the expression&#8217;s components.<\/p><\/blockquote>\n\n\n\n<p class=\"wp-block-paragraph\">For example, the arithmetic expression:<\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>-5+12*4<\/strong><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">would be represented in Abstract Syntax Tree form as:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"alignleft size-large\"><img fetchpriority=\"high\" decoding=\"async\" width=\"346\" height=\"188\" src=\"https:\/\/bhiggs.x10hosting.com\/practical-java-programming\/wp-content\/uploads\/2021\/01\/expr1.gif\" alt=\"\" class=\"wp-image-190\"\/><\/figure><\/div>\n\n\n\n<div style=\"height:18px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p><em><strong><u>Note:<\/u><\/strong><\/em>&nbsp;Conventionally, trees in Computer Science are drawn upside down when compared to trees in the real world. Thus, the&nbsp;<em>root<\/em>&nbsp;of the tree is at the top, not the bottom.<\/p><\/blockquote>\n\n\n\n<p class=\"wp-block-paragraph\">An arithmetic expression uses a&nbsp;<em>convention&nbsp;<\/em>to distinguish between the different possible interpretations. For example, the expression:<\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>-5+12*4<\/strong><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">could be interpreted as either:<\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>(-5+12)*4<\/strong><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">or:<\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>-5+(12*4)<\/strong><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">The latter is the conventionally correct interpretation, because the multiplication operator conventionally has&nbsp;<em>higher precedence<\/em>&nbsp;than the addition operator. However, the Abstract Syntax Tree representation is&nbsp;<em>inherently unambiguous<\/em>, which is one of the reasons it is so popular.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">In the above AST diagram, each element in the tree is connected to other items in the tree by lines. An element in an Abstract Syntax Tree is usually called a&nbsp;<em>Node<\/em>. Nodes can either be&nbsp;<em><u>interior<\/u><\/em><em>&nbsp;nodes<\/em>&nbsp;or&nbsp;<em><u>leaf<\/u><\/em><em>&nbsp;nodes<\/em>. Interior nodes are those that have one or more lines connecting them with other nodes further down the tree. Leaf nodes have no such connections; they are the lowest nodes in that particular branch of the tree. We say that interior nodes have&nbsp;<em>child<\/em>&nbsp;nodes, while leaf nodes do not.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">In this example, interior nodes are used to represent the&nbsp;<em>arithmetic operators<\/em>&nbsp;(<code><strong>+<\/strong><\/code>,&nbsp;<strong><code>-<\/code><\/strong>,&nbsp;<strong><code>*<\/code><\/strong>,&nbsp;<strong><code>\/<\/code><\/strong>, etc.). Arithmetic operators can be&nbsp;<em>unary<\/em>&nbsp;(operating on a single operand), or&nbsp;<em>binary<\/em>&nbsp;(operating on two operands). A unary operator has exactly one child node, while a binary operator has exactly two child nodes. For example, the minus sign in the above expression represents the&nbsp;<em>unary minus<\/em>&nbsp;operator, while the asterisk represents the&nbsp;<em>binary multiplication<\/em>&nbsp;operator, and the plus sign represents the&nbsp;<em>binary addition<\/em>&nbsp;operator.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">A node below an operand in the tree can represent a&nbsp;<em>value<\/em>&nbsp;such as&nbsp;5&nbsp;or&nbsp;12&nbsp;(in the above diagram, all values are integer values). If the node represents a simple value, then it must be a leaf node. If it represents an expression (consisting of some combination of operators and operands), then the node must represent an operator, and therefore must be an interior node.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">For example, imagine you wish to modify the original expression to look like this:<\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>-(5\/23)+12*(4-2)<\/strong><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">The Abstract Syntax Tree for this new expression looks like:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"alignleft size-large\"><img decoding=\"async\" width=\"381\" height=\"244\" src=\"https:\/\/bhiggs.x10hosting.com\/practical-java-programming\/wp-content\/uploads\/2021\/01\/expr2.gif\" alt=\"\" class=\"wp-image-191\"\/><\/figure><\/div>\n\n\n\n<div style=\"height:22px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">Note that we have replaced the original leaf nodes for <strong>5<\/strong>&nbsp;and <strong>4<\/strong> by<em> subtrees<\/em> which represent the new&nbsp;<em>subexpressions<\/em>. The top node in each of these subexpressions represents an operator; which operator depends on the relative precedence of the operators in the subexpression.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">A program can&nbsp;<em>evaluate<\/em>&nbsp;such a tree by&nbsp;<em>walking<\/em>&nbsp;the tree in a prescribed order: at each interior node it determines the value from each subtree, and applies the operator to those values to produce a value for the tree represented by that interior node. A leaf node provides a value directly. A program can also walk the tree in the same fashion to produce a printout of the equivalent arithmetic expression (although it would have to insert parentheses appropriately to maintain the operator precedence).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"The_Assignment\"><\/span>The Assignment<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Your job is to write a set of classes which will allow you to construct such an abstract syntax tree, and then walk it, and evaluate it. Here&#8217;s an abstract&nbsp;<strong>Node&nbsp;<\/strong>class to start with:<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: java; auto-links: false; title: ; quick-code: false; notranslate\" title=\"\">\npackage abstractSyntaxTree;\n\n\/**\n *  A class to represent a node in an Abstract Syntax Tree.\n *  &lt;p&gt;\n *  @author: Bryan J. Higgs, 5 September 1998\n *  &lt;p&gt;\n *  @version 1.0\n *\/\n\npublic abstract class Node\n{\n    public abstract double evaluate();\n    public abstract void walk();\n}\n<\/pre><\/div>\n\n\n<p class=\"wp-block-paragraph\">This class is to be used as a base class for a family of node classes which can be used to construct an AST and then evaluate and walk it. Copy it from this web page and paste it into your editor.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The&nbsp;<strong><code>evaluate()<\/code><\/strong>&nbsp;method returns the value for the (sub)tree, starting from that node on down. (Notice that it returns a&nbsp;<code><strong>double<\/strong><\/code>, not an&nbsp;<code><strong>int<\/strong><\/code>. This is because we would like to be able to evaluate expressions that contain more than integer values &#8212; see later.) For example, calling&nbsp;<strong><code>evaluate()<\/code><\/strong>&nbsp;for the node that represents the binary multiplication operator,&nbsp;<strong><code>*<\/code><\/strong>, in the original expression, will return a value of&nbsp;<strong>48.0<\/strong>&nbsp;(<strong>12*4<\/strong>). Calling&nbsp;<strong><code>evaluate()<\/code><\/strong>&nbsp;for the node at the top of the tree will return the value of the entire expression.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The&nbsp;<strong><code>walk()<\/code><\/strong>&nbsp;method prints out (on&nbsp;<strong><code>System.out<\/code><\/strong>) the arithmetic expression represented by that (sub)tree. In the original example expression, calling&nbsp;<strong><code>walk()<\/code><\/strong>&nbsp;for the node that represents the unary minus operator will print out:<\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>-5<\/strong><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">while calling&nbsp;<strong><code>walk()<\/code><\/strong>&nbsp;for the node that represents the binary multiplication operator will print out:<\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>12 * 4<\/strong><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">Calling&nbsp;<strong>walk()<\/strong>&nbsp;for the node at the top of the tree will print out the entire expression:<\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>-5 + 12 * 4<\/strong><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">We will break the assignment into three parts:<\/p>\n\n\n\n<h4 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Part_1_Integer_UnaryMinus_Plus_and_Times\"><\/span><a href=\"#part-1\">Part 1: <code><strong>Integer<\/strong><\/code>,&nbsp;<code><strong>UnaryMinus<\/strong><\/code>,&nbsp;<code><strong>Plus<\/strong><\/code>&nbsp;and&nbsp;<code><strong>Times<\/strong><\/code><\/a><span class=\"ez-toc-section-end\"><\/span><\/h4>\n\n\n\n<h4 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Part_2_Adding_More_Node_Types\"><\/span><a href=\"#part-2\">Part 2: Adding More Node Types<\/a><span class=\"ez-toc-section-end\"><\/span><\/h4>\n\n\n\n<h4 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Part_3_Teaching_walk_to_correctly_parenthesize\"><\/span><a href=\"#part-3\">Part 3: Teaching\u00a0<code><strong>walk()<\/strong><\/code>\u00a0to correctly parenthesize<\/a><span class=\"ez-toc-section-end\"><\/span><\/h4>\n\n\n\n<hr class=\"wp-block-separator is-style-wide\"\/>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"part-1\"><span class=\"ez-toc-section\" id=\"Part_1_Integer_UnaryMinus_Plus_and_Times-2\"><\/span>Part 1: Integer, UnaryMinus, Plus and Times<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">The first task is to write a set of classes:&nbsp;<strong><code><strong>Integer<\/strong><\/code><\/strong>,&nbsp;<strong><code><strong>UnaryMinus<\/strong><\/code><\/strong>,&nbsp;<strong><code><strong>Plus<\/strong><\/code><\/strong>&nbsp;and&nbsp;<strong><code><strong>Times<\/strong><\/code><\/strong>, which use&nbsp;<em>inheritance<\/em>&nbsp;and&nbsp;<em>polymorphism<\/em>, and which can be used in the following program:<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: java; auto-links: false; title: ; quick-code: false; notranslate\" title=\"\">\npackage abstractSyntaxTree;\n\n\/**\n *  A class to represent an Abstract Syntax Tree.\n *  &lt;p&gt;\n *  @author: Bryan J. Higgs, 5 September 1998\n *  &lt;p&gt;\n *  @version 1.0\n *\/\n\npublic abstract class Tree\n{\n    public static void main(String&#x5B;] args)\n    {\n        Node expression = \n            new Plus(\n                  new UnaryMinus(\n                        new Integer(5)\n                        ),\n                  new Times(\n                        new Integer(12),\n                        new Integer(4)\n                        )\n                  );\n        double result = expression.evaluate();\n        \n        System.out.print(&quot;Result of &quot;);\n        expression.walk();\n        System.out.println(&quot; = &quot; + result);\n    }\n}\n<\/pre><\/div>\n\n\n<h4 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Sequence_of_steps_to_perform\"><\/span><em>Sequence of steps to perform:<\/em><span class=\"ez-toc-section-end\"><\/span><\/h4>\n\n\n\n<ol class=\"wp-block-list\"><li>Write a class&nbsp;<strong><code><strong>Integer<\/strong><\/code>,&nbsp;<\/strong>in package&nbsp;<strong><code>abstractSyntaxTree<\/code><\/strong>, which extends class&nbsp;<strong><code><strong>Node<\/strong><\/code><\/strong>, with a data member that will contain the integer value for an instance of&nbsp;<strong><code>Integer<\/code><\/strong>, with a constructor that allows an&nbsp;<code><strong>int<\/strong><\/code>&nbsp;value to be passed in, and functions&nbsp;<strong><code>evaluate()<\/code><\/strong>&nbsp;and&nbsp;<strong><code>walk()<\/code><\/strong>. Instances of class&nbsp;<strong><code>Integer<\/code><\/strong>&nbsp;will be leaf nodes in the Abstract Syntax Tree.<\/li><li>Now it&#8217;s time to look at interior (non-leaf) nodes. As mentioned before, these break down into two subclasses &#8212;&nbsp;<em>unary<\/em>&nbsp;and&nbsp;<em>binary<\/em>. However, all operators share some degree of commonality, so, first, let us create an&nbsp;<em>abstract<\/em>&nbsp;class&nbsp;<strong><code><strong>Operator<\/strong><\/code>,&nbsp;<\/strong>in package&nbsp;<strong><code>abstractSyntaxTree<\/code><\/strong>, which&nbsp;<em>extends<\/em>&nbsp;<strong><code><strong>Node<\/strong><\/code><\/strong>, and which contains nothing but a single&nbsp;<em>protected method<\/em>:<\/li><\/ol>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>protected abstract String name(); <\/strong><\/pre>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>This will force every non-abstract class that extends the&nbsp;<strong><code><strong>Operator<\/strong><\/code>&nbsp;<\/strong>class to implement a method with this signature. The&nbsp;<strong><code>name()<\/code><\/strong>&nbsp;method is used to output the operator&#8217;s symbol (<strong><code>+<\/code><\/strong>,&nbsp;<strong><code>-<\/code><\/strong>,<strong>&nbsp;<code>*<\/code><\/strong>, etc.). The&nbsp;<strong><code>name()<\/code><\/strong>&nbsp;function will be called from the&nbsp;<strong><code>walk()<\/code><\/strong>&nbsp;function (see later).<\/p><\/blockquote>\n\n\n\n<ol class=\"wp-block-list\" start=\"3\"><li>All unary operators share some common attributes. Naturally, every unary operator is an&nbsp;<strong><code><strong>Operator<\/strong><\/code><\/strong>. In particular, each unary operator needs only a&nbsp;<em>single<\/em>&nbsp;operand (child) node. Create an&nbsp;<em>abstract<\/em>&nbsp;class,&nbsp;<strong><code><strong>UnaryOperator<\/strong><\/code>,&nbsp;<\/strong>in package&nbsp;<strong><code>abstractSyntaxTree<\/code><\/strong>, that extends class&nbsp;<strong><code><strong>Operator<\/strong><\/code><\/strong>. This&nbsp;<strong><code>UnaryOperator<\/code><\/strong>&nbsp;class will serve as the&nbsp;<em>base class for all unary operators<\/em>. It will contain data members and methods common to all unary operators.<\/li><\/ol>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>The&nbsp;<strong><code><strong>UnaryOperator<\/strong><\/code>&nbsp;<\/strong>class should have a single data member, representing the unary operator&#8217;s operand.&nbsp;<em>[What type should this be?]<\/em>&nbsp;Make this data member&nbsp;<strong><code>private<\/code><\/strong>! Provide a <strong><code>protected<\/code><\/strong> method, <strong><code>getOperand()<\/code><\/strong>, to allow derived classes to&nbsp;<em>access<\/em>, but not&nbsp;<em>modify<\/em>&nbsp;this data member. Make the constructor for&nbsp;<strong><code><strong>UnaryOperator<\/strong><\/code>&nbsp;<\/strong>be&nbsp;<strong><code>protected<\/code><\/strong>.<\/p><\/blockquote>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>Implement the&nbsp;<strong><code>walk()<\/code><\/strong>&nbsp;method in the&nbsp;<strong><code><strong>UnaryOperator<\/strong><\/code><\/strong>&nbsp;class.&nbsp;<em>[Why there?]<\/em><\/p><\/blockquote>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p><strong><em>Hint:&nbsp;<\/em><\/strong>This&nbsp;<code><strong>walk()<\/strong><\/code>&nbsp;method will make recursive calls to itself and other virtual&nbsp;<code><strong>walk()<\/strong><\/code>&nbsp;member functions.<\/p><\/blockquote>\n\n\n\n<ol class=\"wp-block-list\" start=\"4\"><li>Create the non-abstract class&nbsp;<strong><code><strong>UnaryMinus<\/strong><\/code>,&nbsp;<\/strong>in package <strong><code>abstractSyntaxTree<\/code><\/strong>, which extends <strong><code><strong>UnaryOperator<\/strong><\/code><\/strong>. It should have a very simple&nbsp;<strong><code>public<\/code><\/strong>&nbsp;constructor (<strong><em>with what for arguments?<\/em><\/strong>). Implement the&nbsp;<strong><code>evaluate()<\/code><\/strong>&nbsp;and&nbsp;<strong><code>name()<\/code><\/strong>&nbsp;methods for this class.<\/li><li>All binary operators share some common attributes. Naturally, every binary operator is an&nbsp;<strong><code><strong>Operator<\/strong><\/code><\/strong>. In addition, each binary operator needs&nbsp;<em>two data members<\/em>&#8212; one its left operand (child) node, and the other its right operand (child) node. Create an <em>abstract<\/em> class, <strong><code><strong>BinaryOperator<\/strong><\/code>,<\/strong> in package&nbsp;<strong><code>abstractSyntaxTree<\/code><\/strong>, which extends&nbsp;<strong><code><strong>Operator<\/strong><\/code><\/strong>. This class will serve as the base class for all binary operators. It will contain data members and methods common to all binary operators.<\/li><\/ol>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>The&nbsp;<strong><code><strong>BinaryOperator<\/strong><\/code>&nbsp;<\/strong>class should have a two data members.&nbsp;<strong><em>What type should each one be?&nbsp;<\/em><\/strong>Make these data members&nbsp;<strong><code>private<\/code><\/strong>! Provide&nbsp;<strong><code>protected<\/code><\/strong>&nbsp;access member functions,&nbsp;<strong><code>getLeftOperand()<\/code><\/strong>&nbsp;and&nbsp;<strong><code>getRightOperand()<\/code>,&nbsp;<\/strong>to allow derived classes to&nbsp;<em>access<\/em>, but not&nbsp;<em>modify<\/em>&nbsp;them. Make the constructor for&nbsp;<strong><code><strong>BinaryOperator<\/strong><\/code>&nbsp;<\/strong>be&nbsp;<strong><code>protected<\/code><\/strong>.<\/p><\/blockquote>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>Implement the&nbsp;<strong><code>walk()<\/code><\/strong>&nbsp;virtual member function in the&nbsp;<strong><code><strong>BinaryOperator<\/strong><\/code><\/strong>&nbsp;class.&nbsp;<\/p><\/blockquote>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p><strong><em>Hint:&nbsp;<\/em><\/strong>This&nbsp;<code><strong>walk()<\/strong><\/code>&nbsp;method will make recursive calls to itself and other virtual&nbsp;<code><strong>walk()<\/strong><\/code>&nbsp;member functions.<\/p><\/blockquote>\n\n\n\n<ol class=\"wp-block-list\" start=\"6\"><li>Create the classes&nbsp;<strong><code><strong>Plus<\/strong><\/code>&nbsp;<\/strong>and&nbsp;<strong><code><strong>Times<\/strong><\/code>,&nbsp;<\/strong>in package&nbsp;<strong><code>abstractSyntaxTree<\/code><\/strong>, each extending&nbsp;<strong><code><strong>BinaryOperator<\/strong><\/code><\/strong>. They should have a very simple&nbsp;<strong><code>public<\/code><\/strong>&nbsp;constructor (<strong><em>with what for arguments?<\/em><\/strong>) Implement the&nbsp;<strong><code>evaluate()<\/code><\/strong>&nbsp;and&nbsp;<strong><code>name()<\/code><\/strong>&nbsp;methods for these classes.<\/li><li>By now, you should be able to build the entire&nbsp;<strong><code>Tree<\/code><\/strong>&nbsp;class, and run it.<br>My version produced the following output:<\/li><\/ol>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Result of -5 + 12 * 4 = 43.0<\/strong><\/pre>\n\n\n\n<hr class=\"wp-block-separator is-style-wide\"\/>\n\n\n\n<div style=\"height:45px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"part-2\"><span class=\"ez-toc-section\" id=\"Part_2_Adding_More_Node_Types-2\"><\/span>Part 2: Adding More Node Types<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p><em><u><strong>Requirement:<\/strong><\/u><\/em>&nbsp;For Part B, consider all the classes you developed in Part A&nbsp;<strong><em>locked<\/em><\/strong>. This means that&nbsp;<strong><em><u>you cannot add or change anything in those files<\/u><\/em><\/strong>.&nbsp; Of course, if you find this rule impossible to abide by, then you probably didn&#8217;t implement Part A correctly, or perhaps you don&#8217;t understand something.&nbsp; If the latter, don&#8217;t hesitate to ask questions!<\/p><\/blockquote>\n\n\n\n<p class=\"wp-block-paragraph\">Create the following classes, all in package&nbsp;<strong><code>abstractSyntaxTree<\/code><\/strong>:<\/p>\n\n\n\n<ol class=\"wp-block-list\" start=\"8\"><li>A&nbsp;<strong><code><strong>Real<\/strong><\/code>&nbsp;<\/strong>class that will hold floating point (<strong><code>double<\/code><\/strong>) values. This will, like the&nbsp;<strong><code>Integer<\/code><\/strong>&nbsp;class, be a leaf class in the abstract syntax tree.<\/li><li>A&nbsp;<strong><code><strong>UnaryPlus<\/strong><\/code>&nbsp;<\/strong>class. This, of course, will look very similar to the&nbsp;<strong><code>UnaryMinus<\/code><\/strong>&nbsp;class.<\/li><li>A&nbsp;<strong><code><strong>Minus<\/strong><\/code>&nbsp;<\/strong>class. This, of course, will look very similar to the&nbsp;<strong><code>Plus<\/code><\/strong>&nbsp;class.<\/li><li>A&nbsp;<strong><code><strong>DividedBy<\/strong><\/code>&nbsp;<\/strong>class. This, of course, will look very similar to the&nbsp;<strong><code>Times<\/code><\/strong>&nbsp;class.<\/li><\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">Here&#8217;s an enhanced&nbsp;<code>Tree<\/code>&nbsp;class to test your work:<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: java; auto-links: false; title: ; quick-code: false; notranslate\" title=\"\">\npackage abstractSyntaxTree;\n\n\/**\n *  A class to represent an Abstract Syntax Tree.\n *  &lt;p&gt;\n *  @author: Bryan J. Higgs, 5 September 1998\n *  &lt;p&gt;\n *  @version 1.0\n *\/\n\npublic abstract class Tree\n{\n    public static void main(String&#x5B;] args)\n    {\n        Node expression = \n            new Plus(\n                  new UnaryMinus(\n                        new Integer(5)\n                        ),\n                  new Times(\n                        new Integer(12),\n                        new Integer(4)\n                        )\n                  );\n        double result = expression.evaluate();\n        \n        System.out.print(&quot;Result of &quot;);\n        expression.walk();\n        System.out.println(&quot; = &quot; + result);\n        \n        expression = \n            new Minus(\n                  new DividedBy(\n                        new Real(53.5),\n                        new Integer(45)\n                        ),\n                  new Times(\n                        new Real(73.54),\n                        new Plus(\n                              new UnaryPlus(\n                                    new Integer(3)\n                                    ),\n                              new Integer(8)\n                              )\n                        )\n                   );\n        result = expression.evaluate();\n        System.out.print(&quot;Result of &quot;);\n        expression.walk();\n        System.out.println(&quot; = &quot; + result);\n        \n        expression = \n            new Times(\n                  new Minus(\n                        new Real(53.5),\n                        new Integer(45)\n                        ),\n                  new Plus(\n                        new Real(73.54),\n                        new Plus(\n                              new UnaryMinus(\n                                    new Integer(3)\n                                    ),\n                              new Integer(8)\n                              )\n                        )\n                   );\n        result = expression.evaluate();\n        System.out.print(&quot;Result of &quot;);\n        expression.walk();\n        System.out.println(&quot; = &quot; + result);\n    }\n}\n<\/pre><\/div>\n\n\n<p class=\"wp-block-paragraph\">When you have completed the additional classes, build this new\u00a0<strong>Tree<\/strong>\u00a0class and run it to get the results of the three expressions. (Copy the above code from this webpage and paste it into your editor.)<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p><em><strong><u>Note:<\/u><\/strong><\/em> You may notice that the second and third expressions in the above class are not correctly parenthesized when printed. Don&#8217;t worry about that for now; we&#8217;ll fix that later, in Part C.<\/p><\/blockquote>\n\n\n\n<p class=\"wp-block-paragraph\"><strong><em>How hard was it to add these classes?<\/em><\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong><em>What did you learn from this exercise?<\/em><\/strong><\/p>\n\n\n\n<hr class=\"wp-block-separator is-style-wide\"\/>\n\n\n\n<div style=\"height:50px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"part-3\"><span class=\"ez-toc-section\" id=\"Part_3_Teaching_walk_to_Correctly_Parenthesize\"><\/span>Part 3: Teaching\u00a0<code><strong>walk()<\/strong><\/code>\u00a0to Correctly Parenthesize<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">You probably noticed in Part B that there are certain expressions (such as the second and third expressions in our enhanced&nbsp;<strong><code>Tree<\/code><\/strong>&nbsp;class) where the output isn&#8217;t quite right &#8212; it needed extra parentheses to represent the correct operator precedence.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Let&#8217;s fix this. Here are the steps we&#8217;ll follow:<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>Modify the\u00a0<strong><code>Operator<\/code><\/strong>\u00a0class as follows:<ul><li>Add a set of\u00a0<strong><code>public static final<\/code><\/strong>\u00a0data members (why\u00a0<strong><code>static<\/code><\/strong>\u00a0and\u00a0<strong><code>final<\/code><\/strong>?) of type\u00a0<strong><code>int<\/code><\/strong>, to indicate various operator precedence levels:<br><strong>PREC_HIGHEST, PREC_HIGHER, PREC_MEDIUM, PREC_LOWER, PREC_LOWEST<br><\/strong>Note that the actual values of these data members don&#8217;t matter, except that the values should represent the relative precedence values appropriately. I suggest that\u00a0<strong>PREC_LOWEST<\/strong>\u00a0be assigned a value of 0, and that you increase the value by 5 or 10 for each precedence level above that. That way, if you later needed to insert an additional precedence level, you have room to do so.<\/li><li>Add a\u00a0<strong><code>protected abstract<\/code><\/strong>\u00a0method\u00a0<strong><code>getPrecedence()<\/code><\/strong>\u00a0to force every class that extends the\u00a0<strong><code>Operator<\/code><\/strong>\u00a0class to implement this method.<\/li><\/ul><\/li><li>At this point, if you build your classes again, you&#8217;ll find that they won&#8217;t build &#8212; they generate errors. To solve this, you&#8217;ll have to add an implementation of the\u00a0<strong><code>getPrecedence()<\/code><\/strong>\u00a0method to every concrete class that extends\u00a0<strong><code>Operator<\/code><\/strong>.<ul><li>Have each method return one of the values defined in <strong><code>Operator<\/code><\/strong> (and remember that\u00a0<strong><code>Operator<\/code><\/strong>\u00a0is a superclass)<\/li><li>The\u00a0<code>UnaryPlus<\/code>\u00a0and\u00a0<strong><code>UnaryMinus<\/code><\/strong>\u00a0classes should return\u00a0<strong>PREC_HIGHEST<\/strong>, the\u00a0<strong><code>Times<\/code><\/strong>\u00a0and\u00a0<strong><code>DividedBy<\/code><\/strong>\u00a0classes should return\u00a0<strong>PREC_HIGHER<\/strong>, and the\u00a0<strong>Plus<\/strong>\u00a0and\u00a0<strong>Minus<\/strong>\u00a0classes should return\u00a0<strong>PREC_MEDIUM<\/strong><\/li><\/ul><\/li><li>Once you&#8217;ve implemented all these\u00a0<strong><code>getPrecedence()<\/code><\/strong>\u00a0methods, the entire thing should build again. However, we haven&#8217;t actually used the methods anywhere, so the behavior of our classes will be as it was before. So, let&#8217;s finish the job:<ul><li>In each of the\u00a0<strong><code>walk()<\/code><\/strong>\u00a0methods you&#8217;ll have to do the following:<ul><li>For each operand, find out whether the operand is an\u00a0<code><strong>Operator<\/strong><\/code>. How?\u00a0<br><strong><em>Hint:<\/em><\/strong>\u00a0There&#8217;s a convenient operator to do this.<\/li><\/ul><ul><li>If it is an\u00a0<code><strong>Operator<\/strong><\/code>, compare its precedence level with the precedence level of the current operator.<\/li><li>If the precedence level of the operand operator is lower than that of the current operator, insert parentheses around the\u00a0<strong><code>walk()<\/code><\/strong>\u00a0call for that operand.<\/li><\/ul><\/li><\/ul><\/li><li>That should do it! Rebuild, and try it.<br>In my implementation, the second and third expressions printed out as:<\/li><\/ol>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Result of 53.5 \/ 45 - 73.54 * (+3 + 8) = -807.7511111111112\nResult of (53.5 - 45) * (73.54 + -3 + 8) = 667.59<\/strong><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">Hurray! You&#8217;re done! (with Assignment 6, at least)<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Abstract Syntax Trees Description Various programs (such as compilers and calculators), use a data structure called an&nbsp;Abstract Syntax Tree (AST)&nbsp;to represent syntax that has been recognized by the program. Note: An Abstract Syntax Tree is&nbsp;not&nbsp;the same as a Binary Search Tree.In a Binary Search Tree, both interior and leaf nodes can contain data, and the [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":102,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_eb_attr":"","_uag_custom_page_level_css":"","ocean_front_end_style_editor":"no","ocean_post_layout":"left-sidebar","ocean_both_sidebars_style":"","ocean_both_sidebars_content_width":0,"ocean_both_sidebars_sidebars_width":0,"ocean_sidebar":"ocs-assignments-sidebar","ocean_second_sidebar":"0","ocean_disable_margins":"enable","ocean_add_body_class":"","ocean_shortcode_before_top_bar":"","ocean_shortcode_after_top_bar":"","ocean_shortcode_before_header":"","ocean_shortcode_after_header":"","ocean_has_shortcode":"","ocean_shortcode_after_title":"","ocean_shortcode_before_footer_widgets":"","ocean_shortcode_after_footer_widgets":"","ocean_shortcode_before_footer_bottom":"","ocean_shortcode_after_footer_bottom":"","ocean_display_top_bar":"default","ocean_display_header":"default","ocean_header_style":"","ocean_center_header_left_menu":"0","ocean_custom_header_template":"0","ocean_custom_logo":0,"ocean_custom_retina_logo":0,"ocean_custom_logo_max_width":0,"ocean_custom_logo_tablet_max_width":0,"ocean_custom_logo_mobile_max_width":0,"ocean_custom_logo_max_height":0,"ocean_custom_logo_tablet_max_height":0,"ocean_custom_logo_mobile_max_height":0,"ocean_header_custom_menu":"0","ocean_menu_typo_font_family":"0","ocean_menu_typo_font_subset":"","ocean_menu_typo_font_size":0,"ocean_menu_typo_font_size_tablet":0,"ocean_menu_typo_font_size_mobile":0,"ocean_menu_typo_font_size_unit":"px","ocean_menu_typo_font_weight":"","ocean_menu_typo_font_weight_tablet":"","ocean_menu_typo_font_weight_mobile":"","ocean_menu_typo_transform":"","ocean_menu_typo_transform_tablet":"","ocean_menu_typo_transform_mobile":"","ocean_menu_typo_line_height":0,"ocean_menu_typo_line_height_tablet":0,"ocean_menu_typo_line_height_mobile":0,"ocean_menu_typo_line_height_unit":"","ocean_menu_typo_spacing":0,"ocean_menu_typo_spacing_tablet":0,"ocean_menu_typo_spacing_mobile":0,"ocean_menu_typo_spacing_unit":"","ocean_menu_link_color":"","ocean_menu_link_color_hover":"","ocean_menu_link_color_active":"","ocean_menu_link_background":"","ocean_menu_link_hover_background":"","ocean_menu_link_active_background":"","ocean_menu_social_links_bg":"","ocean_menu_social_hover_links_bg":"","ocean_menu_social_links_color":"","ocean_menu_social_hover_links_color":"","ocean_disable_title":"default","ocean_disable_heading":"default","ocean_post_title":"","ocean_post_subheading":"","ocean_post_title_style":"","ocean_post_title_background_color":"","ocean_post_title_background":0,"ocean_post_title_bg_image_position":"","ocean_post_title_bg_image_attachment":"","ocean_post_title_bg_image_repeat":"","ocean_post_title_bg_image_size":"","ocean_post_title_height":0,"ocean_post_title_bg_overlay":0.5,"ocean_post_title_bg_overlay_color":"","ocean_disable_breadcrumbs":"default","ocean_breadcrumbs_color":"","ocean_breadcrumbs_separator_color":"","ocean_breadcrumbs_links_color":"","ocean_breadcrumbs_links_hover_color":"","ocean_display_footer_widgets":"default","ocean_display_footer_bottom":"default","ocean_custom_footer_template":"0","footnotes":""},"class_list":["post-186","page","type-page","status-publish","hentry","entry"],"uagb_featured_image_src":{"full":false,"thumbnail":false,"medium":false,"medium_large":false,"large":false,"1536x1536":false,"2048x2048":false,"ocean-thumb-m":false,"ocean-thumb-ml":false,"ocean-thumb-l":false},"uagb_author_info":{"display_name":"Bryan Higgs","author_link":"https:\/\/bhiggs.x10hosting.com\/PracticalJavaProgramming\/author\/bryan\/"},"uagb_comment_info":0,"uagb_excerpt":"Abstract Syntax Trees Description Various programs (such as compilers and calculators), use a data structure called an&nbsp;Abstract Syntax Tree (AST)&nbsp;to represent syntax that has been recognized by the program. Note: An Abstract Syntax Tree is&nbsp;not&nbsp;the same as a Binary Search Tree.In a Binary Search Tree, both interior and leaf nodes can contain data, and the&hellip;","_links":{"self":[{"href":"https:\/\/bhiggs.x10hosting.com\/PracticalJavaProgramming\/wp-json\/wp\/v2\/pages\/186","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/bhiggs.x10hosting.com\/PracticalJavaProgramming\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/bhiggs.x10hosting.com\/PracticalJavaProgramming\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/bhiggs.x10hosting.com\/PracticalJavaProgramming\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/bhiggs.x10hosting.com\/PracticalJavaProgramming\/wp-json\/wp\/v2\/comments?post=186"}],"version-history":[{"count":6,"href":"https:\/\/bhiggs.x10hosting.com\/PracticalJavaProgramming\/wp-json\/wp\/v2\/pages\/186\/revisions"}],"predecessor-version":[{"id":200,"href":"https:\/\/bhiggs.x10hosting.com\/PracticalJavaProgramming\/wp-json\/wp\/v2\/pages\/186\/revisions\/200"}],"up":[{"embeddable":true,"href":"https:\/\/bhiggs.x10hosting.com\/PracticalJavaProgramming\/wp-json\/wp\/v2\/pages\/102"}],"wp:attachment":[{"href":"https:\/\/bhiggs.x10hosting.com\/PracticalJavaProgramming\/wp-json\/wp\/v2\/media?parent=186"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}