The goal of this lab is to reinforce binary tree concepts. Specifically, this lab is to do problem #1 on page 534 of the text(Data Structures and Other Objects Using C++ (4th Edition) ). A partial solution is located here. You need to complete this solution.

expression_tree.cpp

#include "expression_tree.h" #include #include #include

//Precondition: op is either "+" or "-" //Postcondition: expression tree with root containing op & left & right //as subtrees has been created expression_tree::expression_tree (const std::string& op, const expression_tree& left, const expression_tree& right) { assert ((op == "+") || (op == "*")); node = new binary_tree_node (op, left.node, right.node); }

//Postcondition: return whether all characters is s are digits bool all_digits (const string& s) { size_t i = 0; while (i < s.length() && isdigit (s[i])) i++; return i == s.length(); }

//Precondition: value represents an integer //Postcondition: expression tree with value in root and no children has //has been created expression_tree::expression_tree (const std::string& value) { node = new binary_tree_node(value); }

expression_tree::~expression_tree();

expression_tree::expression_tree (const expression_tree& other);

expression_tree::expression_tree& operator = (const expression_tree& other);

//Postcondition: returns value of arithmetic expression represented by expression tree int expression_tree::evaluate() const { // to be implemented }

expression._tree.h

#ifndef _EXPRESSION_TREE_H_ #define _EXPRESSION_TREE_H_

#include "bintree.h" #include #include

using namespace main_savitch_10;

class expression_tree { public: expression_tree (const std::string& op, const expression_tree& left, const expression_tree& right); // precondition: op is either "+" or "-" // postcondition: expression tree with root containing op & left & right // as subtrees has been created expression_tree (const std::string& value); // precondition: value represents an integer // postcondition: expression tree with value in root and no children has // has been create

~expression_tree();

expression_tree (const expression_tree& other);

expression_tree& operator = (const expression_tree& other); int evaluate() const; // return: value of arithmetic expression represented by expression tree

private: binary_tree_node* node; };

#endif

lab10.cpp

#include #include #include "expression_tree.h"

using namespace std;

expression_tree build_expression_tree(); // return: expression tree

int main () { expression_tree t = build_expression_tree(); int value = t.evaluate(); cout << "value: " << value << endl; return EXIT_SUCCESS; }

expression_tree build_expression_tree() { expression_tree t1 ("1"); expression_tree t2 ("2"); expression_tree t3 ("3"); expression_tree t4 ("4"); expression_tree t5 ("5"); expression_tree t6 ("*", t1, t2); expression_tree t7 ("+", t4, t5); expression_tree t8 ("*", t3, t7); expression_tree t9 ("+", t6, t8); return t9; } /* binary_tree_node* build_expression_tree() { binary_tree_node* t1 = new binary_tree_node("1"); binary_tree_node* t2 = new binary_tree_node("2"); binary_tree_node* t3 = new binary_tree_node("3"); binary_tree_node* t4 = new binary_tree_node("4"); binary_tree_node* t5 = new binary_tree_node("5"); binary_tree_node* t6 = new binary_tree_node("*", t1, t2); binary_tree_node* t7 = new binary_tree_node("+", t4, t5); binary_tree_node* t8 = new binary_tree_node("*", t3, t7); binary_tree_node* t9 = new binary_tree_node("+", t6, t8); return t9; }*/