{"id":37,"date":"2024-08-01T18:35:48","date_gmt":"2024-08-01T18:35:48","guid":{"rendered":"https:\/\/bhiggs.x10hosting.com\/PracticalC%2B%2BProgramming\/?page_id=37"},"modified":"2025-01-20T21:47:49","modified_gmt":"2025-01-20T21:47:49","slug":"assignment-7","status":"publish","type":"page","link":"https:\/\/bhiggs.x10hosting.com\/PracticalCPlusPlusProgramming\/index.php\/assignments\/assignment-7\/","title":{"rendered":"Assignment 7"},"content":{"rendered":"\n

<\/span>Abstract Syntax Trees<\/span><\/h3>\n\n\n\n

<\/span>Description<\/em><\/span><\/h4>\n\n\n\n

Various programs (such as compilers and calculators), use a data structure called an Abstract Syntax Tree (AST)<\/em><\/strong> to represent syntax that has been recognized by the program.<\/p>\n\n\n\n

<\/div>\n\n\n\n
\n

NOTE:<\/strong><\/p>\n\n\n\n

An Abstract Syntax Tree is not <\/strong>the same as a Binary Search Tree. <\/p>\n\n\n\n

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 operator <\/em>information, while the leaf nodes contain operand <\/em>information. <\/p>\n\n\n\n

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’s components.<\/p>\n<\/blockquote>\n\n\n\n

For example, the arithmetic expression:<\/p>\n\n\n\n

-5+12*4<\/strong><\/code><\/pre>\n\n\n\n
would be represented in Abstract Syntax Tree form as:<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\n
Note<\/strong>:<\/strong><\/em> Conventionally, trees in Computer Science are drawn upside down when compared to trees in the real world. Thus, the root<\/em> of the tree is at the top, not the bottom.<\/p>\n<\/blockquote>\n\n\n\n
An arithmetic expression uses a convention <\/em>to distinguish between the different possible interpretations. For example, the expression:<\/p>\n\n\n\n
-5+12*4<\/strong><\/code><\/pre>\n\n\n\n
could be interpreted as either:<\/p>\n\n\n\n
(-5+12)*4<\/strong><\/code><\/pre>\n\n\n\n
or:<\/p>\n\n\n\n
-5+(12*4)<\/strong><\/code><\/pre>\n\n\n\n
The latter is the conventionally correct interpretation, because the multiplication operator conventionally has higher precedence<\/em> than the addition operator. However, the Abstract Syntax Tree representation is unambiguous<\/em>, which is one of the reasons it is so popular.<\/p>\n\n\n\n
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 Node<\/em>. Nodes can either be interior nodes<\/em> or leaf 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 child<\/em> nodes, while leaf nodes do not.<\/p>\n\n\n\n
In this example, interior nodes are used to represent the arithmetic operators<\/em> (+,-,*,\/, etc.). Arithmetic operators can be unary<\/em> (operating on a single operand), or binary<\/em> (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 unary minus<\/em> operator, while the asterisk represents the binary multiplication<\/em> operator, and the plus sign represents the binary addition<\/em> operator.<\/p>\n\n\n\n
A node below an operand in the tree can represent a value<\/em> such as 5 or 12 (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
For example, imagine you wish to modify the original expression to look like this:<\/p>\n\n\n\n
-(5\/23)+12*(4-2)<\/strong><\/code><\/pre>\n\n\n\n
The Abstract Syntax Tree for this new expression looks like:<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
Note that we have replaced the original leaf nodes for 5 and 4 by subtrees<\/em> which represent the new subexpressions<\/em>. The top node in each of these subexpressions represents an operator<\/em>; which operator depends on the relative precedence of the operators in the subexpression.<\/p>\n\n\n\n
A program can evaluate<\/em> such a tree by walking<\/em> 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 proper operator precedence).<\/p>\n\n\n\n
<\/span>The Assignment<\/em><\/span><\/h3>\n\n\n\n
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’s an abstract Node <\/strong>class to start with:<\/p>\n\n\n\n
\n
\n
<\/path><\/path><\/svg><\/span>
\/\/ The Node base class<\/span><\/span>\nclass<\/span> <\/span>Node<\/span><\/span>\n{<\/span><\/span>\npublic:<\/span><\/span>\n  <\/span>virtual<\/span> <\/span>~Node<\/span>() {}<\/span><\/span>\n<\/span>\n  <\/span>virtual<\/span> <\/span>double<\/span> <\/span>Evaluate<\/span>() <\/span>const<\/span> = <\/span>0<\/span>;<\/span><\/span>\n  <\/span>virtual<\/span> <\/span>void<\/span> <\/span>Walk<\/span>() <\/span>const<\/span> = <\/span>0<\/span>;<\/span><\/span>\n};<\/span><\/span><\/code><\/pre><\/div>\n<\/div>\n\n\n\n
\n
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.  Cut it from this web page and paste it into your editor (enclosing it with the usual requirements for a header file).<\/p>\n<\/div>\n<\/div>\n\n\n\n
The member function Evaluate()<\/code><\/strong> returns the value for the (sub)tree, starting from that node on down. (Notice that it returns a double, not an int. This is because we would like to be able to evaluate expressions that contain more than integer values — see later.) <\/p>\n\n\n\n
For example, calling Evaluate()<\/code><\/strong> for the node that represents the binary multiplication operator, *<\/code><\/strong>, in the original expression, will return a value of 48.0<\/code> (12*4). Calling Evaluate()<\/code><\/strong> for the node at the top of the tree will return the value of the entire expression.<\/p>\n\n\n\n
The member function Walk()<\/code><\/strong> prints out (on cout<\/strong><\/code>) the arithmetic expression represented by that (sub)tree. In the original example expression, calling Walk()<\/code><\/strong> for the node that represents the unary minus operator will print out:<\/p>\n\n\n\n
-5<\/strong><\/code><\/pre>\n\n\n\n
while calling Walk()<\/code><\/strong> for the node that represents the binary multiplication operator will print out:<\/p>\n\n\n\n
12 * 4<\/strong><\/code><\/pre>\n\n\n\n
Calling Walk()<\/code><\/strong> for the node at the top of the tree will print out the entire expression:<\/p>\n\n\n\n
-5 + 12 * 4<\/strong><\/code><\/pre>\n\n\n\n
\n
Questions:<\/strong><\/p>\n\n\n\n
    \n
  • What makes the Node class abstract?<\/strong><\/em><\/li>\n\n\n\n
  • Why must Node::~Node() be virtual?<\/strong><\/em><\/li>\n<\/ul>\n<\/blockquote>\n\n\n\n
    <\/span>Part A: Integer, UnaryMinus, Plus and Times<\/em><\/span><\/h4>\n\n\n\n
    The first task is to write a set of classes: Integer<\/strong>, UnaryMinus<\/strong>, Plus<\/strong> and Times<\/strong>, which use single inheritance<\/em> and virtual functions<\/em>, and which can be used in the following main program:<\/p>\n\n\n\n
    \n
    \n
    <\/path><\/path><\/svg><\/span>
    \/\/<\/span><\/span>\n\/\/  Syntax.cpp<\/span><\/span>\n\/\/  Abstract Syntax Trees<\/span><\/span>\n\/\/<\/span><\/span>\n\/\/  Created by Bryan Higgs on 11\/5\/24.<\/span><\/span>\n\/\/<\/span><\/span>\n<\/span>\n#include<\/span> <\/span><iostream><\/span><\/span>\nusing<\/span> <\/span>namespace<\/span> <\/span>std<\/span>;<\/span><\/span>\n<\/span>\n#include<\/span> <\/span>"Nodes.h"<\/span><\/span>\n<\/span>\nint<\/span> <\/span>main<\/span>(<\/span>int<\/span> <\/span>argc<\/span>, <\/span>const<\/span> <\/span>char<\/span> <\/span>*<\/span> <\/span>argv<\/span>[])<\/span><\/span>\n{<\/span><\/span>\n  Node *expression =<\/span> \/\/ AST represents: -5 + 12 * 4<\/span><\/span>\n           <\/span>new<\/span> <\/span>Plus<\/span>(<\/span>                    \/\/ +<\/span><\/span>\n                 <\/span>new<\/span> <\/span>UnaryMinus<\/span>(<\/span>        \/\/   -<\/span><\/span>\n                       <\/span>new<\/span> <\/span>Integer<\/span>(<\/span>5<\/span>)<\/span>   \/\/    5<\/span><\/span>\n                       ),<\/span><\/span>\n                 <\/span>new<\/span> <\/span>Times<\/span>(<\/span>             \/\/   *<\/span><\/span>\n                       <\/span>new<\/span> <\/span>Integer<\/span>(<\/span>12<\/span>),<\/span> \/\/    12<\/span><\/span>\n                       <\/span>new<\/span> <\/span>Integer<\/span>(<\/span>4<\/span>)<\/span>   \/\/    4<\/span><\/span>\n                       )<\/span><\/span>\n                 );<\/span><\/span>\n<\/span>\n  <\/span>double<\/span> result = <\/span>expression<\/span>-><\/span>Evaluate<\/span>();<\/span><\/span>\n<\/span>\n  cout << <\/span>"Result of "<\/span>;<\/span><\/span>\n  <\/span>expression<\/span>-><\/span>Walk<\/span>();<\/span><\/span>\n  cout << <\/span>" = "<\/span> << result << endl;<\/span><\/span>\n<\/span>\n  <\/span>delete<\/span> expression;<\/span> \/\/ Clean up expression AST<\/span><\/span>\n<\/span>\n  \/\/ Test additional expression functionality<\/span><\/span>\n<\/span>\n  expression =<\/span> \/\/ AST represents: -(5 + 12 * 4)<\/span><\/span>\n    <\/span>new<\/span> <\/span>UnaryMinus<\/span>(<\/span><\/span>\n     <\/span>new<\/span> <\/span>Plus<\/span>(<\/span><\/span>\n    <\/span>new<\/span> <\/span>Integer<\/span>(<\/span>5<\/span>),<\/span><\/span>\n    <\/span>new<\/span> <\/span>Times<\/span>(<\/span><\/span>\n      <\/span>new<\/span> <\/span>Integer<\/span>(<\/span>12<\/span>),<\/span><\/span>\n      <\/span>new<\/span> <\/span>Integer<\/span>(<\/span>4<\/span>)<\/span><\/span>\n      )<\/span><\/span>\n    )<\/span><\/span>\n  );<\/span><\/span>\n<\/span>\n  result = <\/span>expression<\/span>-><\/span>Evaluate<\/span>();<\/span><\/span>\n  cout << <\/span>"Result of "<\/span>;<\/span><\/span>\n  <\/span>expression<\/span>-><\/span>Walk<\/span>();<\/span><\/span>\n  cout << <\/span>" = "<\/span> << result << endl;<\/span><\/span>\n<\/span>\n  <\/span>delete<\/span> expression;<\/span> \/\/ Clean up expression AST<\/span><\/span>\n<\/span>\n  <\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span><\/code><\/pre><\/div>\n<\/div>\n\n\n\n
    \n
    \n
    Note:<\/strong><\/em> <\/strong><\/p>\n\n\n\n
    In all of the classes you write, be sure to implement any non-trivial member functions in a separate .cpp file<\/em>, not in the .h file.  <\/em> <\/p>\n\n\n\n
    In Part 1, this will be in file nodes.cpp<\/code><\/p>\n\n\n\n
    In Part 2, in file extnodes.cpp<\/code>. Any code depending on <iostream><\/code> should be placed in the .cpp file.<\/p>\n<\/blockquote>\n<\/div>\n<\/div>\n\n\n\n
    <\/span>Sequence of steps to perform:<\/em><\/span><\/h5>\n\n\n\n
      \n
    1. In nodes.h, write a class Integer<\/code><\/strong> which is publicly derived<\/em> from class Node<\/code><\/strong>.  The  class will have a data member which will contain the integer value for that instance of Integer<\/code><\/strong>. The class will also have a constructor which allows an integer value to be passed in as a parameter, and virtual functions Evaluate()<\/code><\/strong> and Walk()<\/code><\/strong>.  Instances of class Integer<\/code><\/strong> will be leaf nodes in the Abstract Syntax Tree.  Any non-inline member function implementations should go in file nodes.cpp<\/code>.<\/li>\n\n\n\n
    2. Now it’s time to look at interior (non-leaf) nodes: the operators. As mentioned before, these break down into two subclasses — unary<\/em> and binary <\/em>operators. However, all operators share some degree of commonality, so, first, create an abstract<\/em> class Operator<\/code><\/strong>, which is publicly derived<\/em> from Node<\/code><\/strong>, and which contains nothing but a single protected pure virtual member function<\/em>: 
      virtual const char *Name() const = 0;<\/strong>
      This will force every non-abstract class that derives from the Operator<\/strong> class to implement a virtual function with this signature. The Name() <\/code><\/strong>virtual member function is used to output the operator’s symbol (+<\/code><\/strong>, -<\/code><\/strong>, *<\/code><\/strong>, etc.). The Name()<\/code><\/strong>
      function will be called from the Walk()<\/code><\/strong> function (see later). (Note that you can add appropriate spacing around the operator name to obtain pleasing results when the expression is output.)<\/li>\n\n\n\n
    3. All unary operators share some common attributes. Naturally, every unary operator is an Operator<\/code><\/strong>. In particular, each unary operator needs only a single<\/em> pointer<\/em> to its operand (child) node. Create an abstract<\/em> class, UnaryOperator<\/code><\/strong>, derived from Operator<\/code><\/strong>. This class will serve as the base class for all unary operators<\/em>. It will contain data members and member functions common to all unary operators.
      The UnaryOperator<\/code><\/strong> class should have a single data member to point to its operand. What type should this data member be? (Hint: read the above paragraph carefully.) <\/em>Make this data member private<\/code>! Provide a protected
      member function (with an appropriate name) to allow derived classes to access<\/em>, but not modify<\/em> it. Make the constructor and destructor for UnaryOperator<\/code><\/strong> be protected<\/code>. 
      Note:<\/strong><\/em> <\/strong>The test program assumes that the tree may be cleaned up by performing a delete. The easiest way to accomplish this is to assume that every Node<\/code><\/strong> will be allocated (new<\/code>) from the heap, and so can be validly deleted. Do the appropriate delete(s) in the UnaryOperator<\/code><\/strong> destructor.<\/em>
      Implement the Walk()<\/code><\/strong> virtual member function in the UnaryOperator<\/code><\/strong> class. [Why there?]<\/em>  Make it protected. 
      Hint: <\/strong>This Walk()<\/code><\/strong> function will make recursive calls to itself and other virtual Walk()<\/code><\/strong> member functions.<\/em><\/li>\n\n\n\n
    4. Create the concrete (non-abstract) class UnaryMinus<\/code><\/strong>, derived from UnaryOperator<\/code><\/strong>. It should have a very simple public<\/code> constructor (with what for arguments?<\/em><\/strong>). Implement the Evaluate()<\/code><\/strong> and Name()<\/code><\/strong> virtual functions for this class.<\/li>\n\n\n\n
    5. All binary operators share some common attributes. Naturally, every binary operator is an Operator<\/code><\/strong>. In addition, each binary operator needs two pointers<\/em> — one to its left operand (child) node, and one to its right operand (child) node. Create an abstract<\/em> class, BinaryOperator<\/code><\/strong>, publicly derived from Operator<\/code><\/strong>. This class will serve as the base class for all binary operators. It will contain data members and member functions common to all binary operators.
      The BinaryOperator<\/strong> class should have a two data members. What type should each one be?<\/em><\/strong> 
      Hint: <\/em><\/strong>read the above paragraph carefully. <\/em>
      Make these data members private<\/code>. Provide protected<\/code> access member functions (with appropriate names) to allow derived classes to access, but not modify, them. Make the constructor and destructor for BinaryOperator<\/code><\/strong> be protected.
      Note:<\/strong><\/em> <\/strong>The test program assumes that the tree may be cleaned up by performing a delete. The easiest way to accomplish this is to assume that every Node will be allocated (new<\/code>) from the heap, and so can be validly deleted. Do the appropriate delete(s) in the UnaryOperator<\/code><\/strong> destructor.<\/em>
      Implement the Walk()<\/code><\/strong> virtual member function in the BinaryOperator<\/code><\/strong> class. Make it protected<\/code>. 
      Hint: <\/strong>This Walk() function will make recursive calls to itself and other virtual Walk() member functions.<\/em><\/li>\n\n\n\n
    6. Create the classes Plus<\/code><\/strong> and Times<\/code><\/strong>, each publicly derived from BinaryOperator<\/code><\/strong>. They should have a very simple public constructor (with what for arguments?<\/em><\/strong>)  Implement the Evaluate()<\/code><\/strong> and Name()<\/code><\/strong> virtual functions for these classes.<\/li>\n<\/ol>\n\n\n\n
      By now, you should be able to compile and link the entire syntax program, and run it. (Note that you will have to compile and link together two .cpp files)<\/p>\n\n\n\n
      Does it work?<\/em><\/strong> If so, do you understand how?<\/strong><\/em><\/p>\n\n\n\n
      My version produced the following output for the first expression:<\/p>\n\n\n\n
      Result of -5 + 12 * 4 = 43.0<\/strong><\/code><\/pre>\n\n\n\n
      <\/span>Part B<\/em>: Adding More Node Types<\/em><\/span><\/h4>\n\n\n\n
      \n
      Requirement:<\/strong> <\/p>\n\n\n\n
      From now on, consider all the .h<\/strong> and .cpp<\/strong> files you developed in Part A locked<\/em>. This means that you cannot add or change anything in those files<\/em>.<\/p>\n<\/blockquote>\n\n\n\n
      Create new files extnodes.h<\/code> and extnodes.cpp<\/code>, and add the additional node classes to them (not<\/em> to nodes.h<\/code> or nodes.cpp<\/code>)<\/p>\n\n\n\n
        \n
      1. A Real<\/code> <\/strong>class that will hold floating point (double) values.<\/li>\n\n\n\n
      2. A UnaryPlus<\/code> <\/strong>class.<\/li>\n\n\n\n
      3. A Minus<\/code> <\/strong>class.<\/li>\n\n\n\n
      4. A DividedBy<\/code> <\/strong>class<\/li>\n<\/ol>\n\n\n\n
        Here’s an extended test program to test your work:<\/p>\n\n\n\n
        \n
        \n
        <\/path><\/path><\/svg><\/span>
        \/\/<\/span><\/span>\n\/\/  Syntax2.cpp<\/span><\/span>\n\/\/  Abstract Syntax Trees<\/span><\/span>\n\/\/<\/span><\/span>\n\/\/  Created by Bryan Higgs on 11\/5\/24.<\/span><\/span>\n\/\/<\/span><\/span>\n<\/span>\n\/\/ Test evaluation of an abstract syntax tree.<\/span><\/span>\n<\/span>\n#include<\/span> <\/span><iostream><\/span><\/span>\nusing<\/span> <\/span>namespace<\/span> <\/span>std<\/span>;<\/span><\/span>\n<\/span>\n#include<\/span> <\/span>"Nodes.h"<\/span><\/span>\n#include<\/span> <\/span>"extnodes.h"<\/span>   <\/span>\/\/ For Real, UnaryPlus, Minus and DividedBy<\/span><\/span>\n<\/span>\nint<\/span> <\/span>main<\/span>(<\/span>int<\/span> <\/span>argc<\/span>, <\/span>const<\/span> <\/span>char<\/span> <\/span>*<\/span> <\/span>argv<\/span>[])<\/span><\/span>\n{<\/span><\/span>\n  Node *expression =<\/span> \/\/ AST represents: -5 + 12 * 4<\/span><\/span>\n           <\/span>new<\/span> <\/span>Plus<\/span>(<\/span>                    \/\/ +<\/span><\/span>\n                 <\/span>new<\/span> <\/span>UnaryMinus<\/span>(<\/span>        \/\/   -<\/span><\/span>\n                       <\/span>new<\/span> <\/span>Integer<\/span>(<\/span>5<\/span>)<\/span>   \/\/    5<\/span><\/span>\n                       ),<\/span><\/span>\n                 <\/span>new<\/span> <\/span>Times<\/span>(<\/span>             \/\/   *<\/span><\/span>\n                       <\/span>new<\/span> <\/span>Integer<\/span>(<\/span>12<\/span>),<\/span> \/\/    12<\/span><\/span>\n                       <\/span>new<\/span> <\/span>Integer<\/span>(<\/span>4<\/span>)<\/span>   \/\/    4<\/span><\/span>\n                       )<\/span><\/span>\n                 );<\/span><\/span>\n<\/span>\n  <\/span>double<\/span> result = <\/span>expression<\/span>-><\/span>Evaluate<\/span>();<\/span><\/span>\n<\/span>\n  cout << <\/span>"Result of "<\/span>;<\/span><\/span>\n  <\/span>expression<\/span>-><\/span>Walk<\/span>();<\/span><\/span>\n  cout << <\/span>" = "<\/span> << result << endl;<\/span><\/span>\n<\/span>\n  <\/span>delete<\/span> expression;<\/span> \/\/ Clean up expression AST<\/span><\/span>\n<\/span>\n   \/\/ Test additional expression functionality<\/span><\/span>\n<\/span>\n  expression =<\/span> \/\/ AST represents: 53.5 \/ 45 - 73.54 * (+3 + 8)<\/span><\/span>\n           <\/span>new<\/span> <\/span>Minus<\/span>(<\/span><\/span>\n                 <\/span>new<\/span> <\/span>DividedBy<\/span>(<\/span><\/span>\n                       <\/span>new<\/span> <\/span>Real<\/span>(<\/span>53.5<\/span>),<\/span><\/span>\n                       <\/span>new<\/span> <\/span>Integer<\/span>(<\/span>45<\/span>)<\/span><\/span>\n                       ),<\/span><\/span>\n                 <\/span>new<\/span> <\/span>Times<\/span>(<\/span><\/span>\n                       <\/span>new<\/span> <\/span>Real<\/span>(<\/span>73.54<\/span>),<\/span><\/span>\n                       <\/span>new<\/span> <\/span>Plus<\/span>(<\/span><\/span>\n                             <\/span>new<\/span> <\/span>UnaryPlus<\/span>(<\/span><\/span>\n                                   <\/span>new<\/span> <\/span>Integer<\/span>(<\/span>3<\/span>)<\/span><\/span>\n                                   ),<\/span><\/span>\n                             <\/span>new<\/span> <\/span>Integer<\/span>(<\/span>8<\/span>)<\/span><\/span>\n                             )<\/span><\/span>\n                       )<\/span><\/span>\n                 );<\/span><\/span>\n<\/span>\n  result = <\/span>expression<\/span>-><\/span>Evaluate<\/span>();<\/span><\/span>\n  cout << <\/span>"Result of "<\/span>;<\/span><\/span>\n  <\/span>expression<\/span>-><\/span>Walk<\/span>();<\/span><\/span>\n  cout << <\/span>" = "<\/span> << result << endl;<\/span><\/span>\n<\/span>\n  <\/span>delete<\/span> expression;<\/span> \/\/ Clean up expression AST<\/span><\/span>\n<\/span>\n   \/\/ Another expression<\/span><\/span>\n<\/span>\n  expression =<\/span> \/\/ AST represents: (53.5 - 45) * (73.54 + -3 + 8)<\/span><\/span>\n           <\/span>new<\/span> <\/span>Times<\/span>(<\/span><\/span>\n                 <\/span>new<\/span> <\/span>Minus<\/span>(<\/span><\/span>\n                       <\/span>new<\/span> <\/span>Real<\/span>(<\/span>53.5<\/span>),<\/span><\/span>\n                       <\/span>new<\/span> <\/span>Integer<\/span>(<\/span>45<\/span>)<\/span><\/span>\n                       ),<\/span><\/span>\n                 <\/span>new<\/span> <\/span>Plus<\/span>(<\/span><\/span>\n                       <\/span>new<\/span> <\/span>Real<\/span>(<\/span>73.54<\/span>),<\/span><\/span>\n                       <\/span>new<\/span> <\/span>Plus<\/span>(<\/span><\/span>\n                             <\/span>new<\/span> <\/span>UnaryMinus<\/span>(<\/span><\/span>\n                                   <\/span>new<\/span> <\/span>Integer<\/span>(<\/span>3<\/span>)<\/span><\/span>\n                                   ),<\/span><\/span>\n                             <\/span>new<\/span> <\/span>Integer<\/span>(<\/span>8<\/span>)<\/span><\/span>\n                             )<\/span><\/span>\n                       )<\/span><\/span>\n                 );<\/span><\/span>\n<\/span>\n  result = <\/span>expression<\/span>-><\/span>Evaluate<\/span>();<\/span><\/span>\n  cout << <\/span>"Result of "<\/span>;<\/span><\/span>\n  <\/span>expression<\/span>-><\/span>Walk<\/span>();<\/span><\/span>\n  cout << <\/span>" = "<\/span> << result << endl;<\/span><\/span>\n<\/span>\n  <\/span>delete<\/span> expression;<\/span> \/\/ Clean up expression AST<\/span><\/span>\n<\/span>\n  <\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span><\/code><\/pre><\/div>\n<\/div>\n\n\n\n
        \n
        When you have completed the additional classes, compile this new syntax.cpp<\/strong> file and run it to get the results of the three expressions. (Cut the above code from this webpage and paste it into your editor.)<\/p>\n\n\n\n
        \n
        Note: <\/strong>You may notice that the second and third expressions in the above class are not correctly parenthesized when printed. Don’t worry about that for now; we’ll fix that later, in Part C.<\/p>\n<\/blockquote>\n\n\n\n
        Note that, now, you’ll have three .cpp<\/strong> files to compile and link together.<\/p>\n\n\n\n
        What did you learn from this exercise?<\/em><\/strong><\/p>\n\n\n\n
        How hard was it to add these?<\/em><\/strong><\/p>\n<\/div>\n<\/div>\n\n\n\n
        <\/span>Part C: Teaching Walk() to Correctly Parenthesize<\/em><\/span><\/h4>\n\n\n\n
        You probably noticed in Part B that there are certain expressions (such as the second and third expressions in our enhanced main program) where the output isn’t quite right — it needs extra parentheses to represent the correct operator precedence.<\/p>\n\n\n\n
        Let’s fix this. Here are the steps we’ll follow:<\/p>\n\n\n\n
          \n
        • Modify the Operator<\/code><\/strong> class as follows:\n
            \n
          • Add a set of public const static<\/code> <\/strong>data members (why static<\/code><\/strong> and why const<\/code><\/strong>?) of type int<\/code><\/strong>, to indicate various operator precedence levels: PREC_HIGHEST<\/code>, PREC_HIGHER<\/code>, PREC_MEDIUM<\/code>, PREC_LOWER<\/code>, PREC_LOWEST<\/code>
            <\/strong>Note that the actual values of these data members don’t matter, except that the values should represent the relative precedence values appropriately. I suggest that PREC_LOWEST<\/code><\/strong> be 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>\n\n\n\n
          • Add a public<\/code> <\/strong>pure virtual member function Precedence()<\/code><\/strong> 
            virtual int Precedence() const = 0;<\/strong>
            to force every class that is derived from the Operator<\/code><\/strong> class to implement this member function.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
          • Once you’ve implemented all these Precedence()<\/strong> member functions, the entire project should build again. However, we haven’t actually used the member functions anywhere yet, so the behavior of our classes will still be as it was before.So, let’s finish the job:\n
              \n
            • In each of the Walk()<\/code><\/strong> member functions, you’ll have to do the following:<\/li>\n\n\n\n
            • For each operand, find out whether the operand is an Operator<\/code><\/strong>. How?
              Hint: <\/strong>Take a look at the dynamic_cast operator.<\/em><\/li>\n\n\n\n
            • If it is an Operator<\/code><\/strong>, compare its precedence level with the precedence level of the current operator.<\/li>\n\n\n\n
            • If the precedence level of the operand operator is lower than that of the current operator, insert parentheses around the Walk()<\/code><\/strong> call for that operand.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n
              That should do it! Rebuild, and try it. Test, test, test!<\/p>\n\n\n\n
              In my implementation, the second and third expressions printed out as:<\/p>\n\n\n\n
              Result of 53.5 \/ 45 - 73.54 * (+3 + 8) = -807.751\nResult of (53.5 - 45) * (73.54 + -3 + 8) = 667.59<\/strong><\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
              Abstract Syntax Trees Description Various programs (such as compilers and calculators), use a data structure called an Abstract Syntax Tree (AST) to represent syntax that has been recognized by the program. NOTE: An Abstract Syntax Tree is not the same as a Binary Search Tree.  In a Binary Search Tree, both interior and leaf nodes can contain data, and […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":29,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-37","page","type-page","status-publish","hentry"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/bhiggs.x10hosting.com\/PracticalCPlusPlusProgramming\/index.php\/wp-json\/wp\/v2\/pages\/37","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/bhiggs.x10hosting.com\/PracticalCPlusPlusProgramming\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/bhiggs.x10hosting.com\/PracticalCPlusPlusProgramming\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/bhiggs.x10hosting.com\/PracticalCPlusPlusProgramming\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/bhiggs.x10hosting.com\/PracticalCPlusPlusProgramming\/index.php\/wp-json\/wp\/v2\/comments?post=37"}],"version-history":[{"count":7,"href":"https:\/\/bhiggs.x10hosting.com\/PracticalCPlusPlusProgramming\/index.php\/wp-json\/wp\/v2\/pages\/37\/revisions"}],"predecessor-version":[{"id":1706,"href":"https:\/\/bhiggs.x10hosting.com\/PracticalCPlusPlusProgramming\/index.php\/wp-json\/wp\/v2\/pages\/37\/revisions\/1706"}],"up":[{"embeddable":true,"href":"https:\/\/bhiggs.x10hosting.com\/PracticalCPlusPlusProgramming\/index.php\/wp-json\/wp\/v2\/pages\/29"}],"wp:attachment":[{"href":"https:\/\/bhiggs.x10hosting.com\/PracticalCPlusPlusProgramming\/index.php\/wp-json\/wp\/v2\/media?parent=37"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}