Please fix the following code! I need to implement the "int expression_tree:: evaluate() const" method in expression_tree.cpp but I'm having trouble. Basically the if the node is a leaf node, return the value. Otherwise, the node represents an operator, in which case, you perform the operation on the evaluated sub trees. If a division is being performed and the denominator is zero, a division_by_zero exception is thrown. (O(n)) The programs are below and all the commented stuff is unneeded and must not be used.

bintree.h

// FILE: bintree.h (part of the namespace main_savitch_10) // PROVIDES: A template class for a node in a binary tree and functions for // manipulating binary trees. The template parameter is the type of data in // each node. // // TYPEDEF for the binary_tree_node template class: // Each node of the tree contains a piece of data and pointers to its // children. The type of the data (binary_tree_node::value_type) is // the Item type from the template parameter. The type may be any of the C++ // built-in types (int, char, etc.), or a class with a default constructor, // and an assignment operator. // // CONSTRUCTOR for the binary_tree_node class: // binary_tree_node( // const item& init_data = Item( ), // binary_tree_node* init_left = NULL, // binary_tree_node* init_right = NULL // ) // Postcondition: The new node has its data equal to init_data, // and it's child pointers equal to init_left and init_right. // // MEMBER FUNCTIONS for the binary_tree_node class: // const item& data( ) const <----- const version // and // Item& data( ) <----- non-const version // Postcondition: The return value is a reference to the data from // this binary_tree_node. // // const binary_tree_node* left( ) const <----- const version // and // binary_tree_node* left( ) <----- non-const version // and // const binary_tree_node* right( ) const <----- const version // and // binary_tree_node* right( ) <----- non-const version // Postcondition: The return value is a pointer to the left or right child // (which will be NULL if there is no child). // // void set_data(const Item& new_data) // Postcondition: The binary_tree_node now contains the specified new data. // // void set_left(binary_tree_node* new_link) // and // void set_right(binary_tree_node* new_link) // Postcondition: The binary_tree_node now contains the specified new link // to a child. // // bool is_leaf( ) // Postcondition: The return value is true if the node is a leaf; // otherwise the return value is false. // // NON-MEMBER FUNCTIONS to maniplulate binary tree nodes: // tempate // void inorder(Process f, BTNode* node_ptr) // Precondition: node_ptr is a pointer to a node in a binary tree (or // node_ptr may be NULL to indicate the empty tree). // Postcondition: If node_ptr is non-NULL, then the function f has been // applied to the contents of *node_ptr and all of its descendants, using // an in-order traversal. // Note: BTNode may be a binary_tree_node or a const binary tree node. // Process is the type of a function f that may be called with a single // Item argument (using the Item type from the node). // // tempate // void postorder(Process f, BTNode* node_ptr) // Same as the in-order function, except with a post-order traversal. // // tempate // void preorder(Process f, BTNode* node_ptr) // Same as the in-order function, except with a pre-order traversal. // // template // void print(const binary_tree_node* node_ptr, SizeType depth) // Precondition: node_ptr is a pointer to a node in a binary tree (or // node_ptr may be NULL to indicate the empty tree). If the pointer is // not NULL, then depth is the depth of the node pointed to by node_ptr. // Postcondition: If node_ptr is non-NULL, then the contents of *node_ptr // and all its descendants have been written to cout with the << operator, // using a backward in-order traversal. Each node is indented four times // its depth. // // template // void tree_clear(binary_tree_node*& root_ptr) // Precondition: root_ptr is the root pointer of a binary tree (which may // be NULL for the empty tree). // Postcondition: All nodes at the root or below have been returned to the // heap, and root_ptr has been set to NULL. // // template // binary_tree_node* tree_copy(const binary_tree_node* root_ptr) // Precondition: root_ptr is the root pointer of a binary tree (which may // be NULL for the empty tree). // Postcondition: A copy of the binary tree has been made, and the return // value is a pointer to the root of this copy. // // template // size_t tree_size(const binary_tree_node* node_ptr) // Precondition: node_ptr is a pointer to a node in a binary tree (or // node_ptr may be NULL to indicate the empty tree). // Postcondition: The return value is the number of nodes in the tree.

#ifndef BINTREE_H #define BINTREE_H #include // Provides NULL and size_t

namespace main_savitch_10 {

template class binary_tree_node { public: // TYPEDEF // typedef Item value_type; // CONSTRUCTOR binary_tree_node( const Item& init_data = Item( ), binary_tree_node* init_left = NULL, binary_tree_node* init_right = NULL ) { data_field = init_data; left_field = init_left; right_field = init_right; } // MODIFICATION MEMBER FUNCTIONS Item& data( ) { return data_field; } binary_tree_node* left( ) { return left_field; } binary_tree_node* right( ) { return right_field; } void set_data(const Item& new_data) { data_field = new_data; } void set_left(binary_tree_node* new_left) { left_field = new_left; } void set_right(binary_tree_node* new_right) { right_field = new_right; } // CONST MEMBER FUNCTIONS const Item& data( ) const { return data_field; } const binary_tree_node* left( ) const { return left_field; } const binary_tree_node* right( ) const { return right_field; } bool is_leaf( ) const { return (left_field == NULL) && (right_field == NULL); } private: Item data_field; binary_tree_node *left_field; binary_tree_node *right_field; };

// NON-MEMBER FUNCTIONS for the binary_tree_node: template void inorder(Process f, BTNode* node_ptr);

template void preorder(Process f, BTNode* node_ptr);

template void postorder(Process f, BTNode* node_ptr);

template void print(binary_tree_node* node_ptr, SizeType depth);

template void tree_clear(binary_tree_node*& root_ptr);

template binary_tree_node* tree_copy(const binary_tree_node* root_ptr);

template std::size_t tree_size(const binary_tree_node* node_ptr); }

#include "bintree.template" #endif

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

expression_tree.cpp

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

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); }

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

expression_tree::expression_tree (const std::string& value) { node = new binary_tree_node(value); }

//PROBLEM FUNCTION int expression_tree::evaluate() const { int result; std:: string value; if(node -> is_leaf()) { value = node -> data(); std::stringstream numValue(value); int result = 0; numValue >> result; return result; } else { switch(op) { case '+': result = left -> evaluate() + right -> evaluate(); break; case '*': result = left -> evaluate() * right -> evaluate(); break; } return result; } }

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; }*/