The goal of this homework is to practice the builder pattern and visitor pattern
ID: 3735342 • Letter: T
Question
The goal of this homework is to practice the builder pattern and visitor pattern. In
the lecture, you are given an example of parsing a string of a binary expression using
the builder patter. In that example, all nodes are of the same class Node, which has
two pointers, m_leftChild and m_rightChild. This causes memory waste because all
terminal nodes also have these two data members although they have no children.
Also, it does not have a visitor that can calculate the value of the binary expression.
In this project, you need to design and implement classes to implement the following
functionalities:
1. Using the builder pattern, given a binary expression as a string, your program can
construct a binary expression tree using two types of nodes: terminal nodes, which
have no children data members, and nonterminal nodes, which have children data
members. You can refer to the example code in the lecture and Homework 12.
2. You need to develop a visitor that can calculate the value of a binary expression
tree. You may need to use a stack. You may need a function such as istringstream()
to convert a string to a value.
3. You need to develop classes so that the following main() function will produce the
following output. Note that both the terminal node class and the nonterminal class
need to have print operations so that they can be used to print out the binary
expression tree.
int main(int argc, char** argv) {
ExpBuilder builder;
ExpParser parser;
parser.setBuilder(&builder);
string input="(((30+500)*70)-(60/50))";
parser.parse(input);
Node* root = builder.getExpression();
cout<<input<<endl;
root->print();
StackBasedCalVisitor sbsv;
root->Accept(&sbsv);
cout<<endl<<"StackBasedSumVisitor Result: "<<sbsv.getResult()<<endl;
return 0;
}
Output:
(((30+500)*70)-(60/50))
(((30+500)*70)-(60/50))
StackBasedSumVisitor Result: 37098.8
Explanation / Answer
Hi the question was too much clear . Hence i created a common code where you can evaluate the binary expression along with handling all the other scenarios
Note: Please look for the comments in the code to understand the code
// C++ program to evaluate an expression tree
#include <bits/stdc++.h>
using namespace std;
// Class to represent the nodes of syntax tree
class node
{
public:
string info;
node *left = NULL, *right = NULL;
node(string x)
{
info = x;
}
};
// Utility function to return the integer value
// of a given string
int toInt(string s)
{
int num = 0;
for (int i=0; i<s.length(); i++)
num = num*10 + (int(s[i])-48);
return num;
}
// This function receives a node of the syntax tree
// and recursively evaluates it
int eval(node* root)
{
// empty tree
if (!root)
return 0;
// leaf node i.e, an integer
if (!root->left && !root->right)
return toInt(root->info);
// Evaluate left subtree
int l_val = eval(root->left);
// Evaluate right subtree
int r_val = eval(root->right);
// Check which operator to apply
if (root->info=="+")
return l_val+r_val;
if (root->info=="-")
return l_val-r_val;
if (root->info=="*")
return l_val*r_val;
return l_val/r_val;
}
//driver function to check the above program
int main()
{
// create a syntax tree
node *root = new node("+");
root->left = new node("*");
root->left->left = new node("5");
root->left->right = new node("4");
root->right = new node("-");
root->right->left = new node("100");
root->right->right = new node("20");
cout << eval(root) << endl;
delete(root);
root = new node("+");
root->left = new node("*");
root->left->left = new node("5");
root->left->right = new node("4");
root->right = new node("-");
root->right->left = new node("100");
root->right->right = new node("/");
root->right->right->left = new node("20");
root->right->right->right = new node("2");
cout << eval(root);
return 0;
}
// C++ program to evaluate an expression tree
#include <bits/stdc++.h>
using namespace std;
// Class to represent the nodes of syntax tree
class node
{
public:
string info;
node *left = NULL, *right = NULL;
node(string x)
{
info = x;
}
};
// Utility function to return the integer value
// of a given string
int toInt(string s)
{
int num = 0;
for (int i=0; i<s.length(); i++)
num = num*10 + (int(s[i])-48);
return num;
}
// This function receives a node of the syntax tree
// and recursively evaluates it
int eval(node* root)
{
// empty tree
if (!root)
return 0;
// leaf node i.e, an integer
if (!root->left && !root->right)
return toInt(root->info);
// Evaluate left subtree
int l_val = eval(root->left);
// Evaluate right subtree
int r_val = eval(root->right);
// Check which operator to apply
if (root->info=="+")
return l_val+r_val;
if (root->info=="-")
return l_val-r_val;
if (root->info=="*")
return l_val*r_val;
return l_val/r_val;
}
//driver function to check the above program
int main()
{
// create a syntax tree
node *root = new node("+");
root->left = new node("*");
root->left->left = new node("5");
root->left->right = new node("4");
root->right = new node("-");
root->right->left = new node("100");
root->right->right = new node("20");
cout << eval(root) << endl;
delete(root);
root = new node("+");
root->left = new node("*");
root->left->left = new node("5");
root->left->right = new node("4");
root->right = new node("-");
root->right->left = new node("100");
root->right->right = new node("/");
root->right->right->left = new node("20");
root->right->right->right = new node("2");
cout << eval(root);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.