Please give an example of this program running fully and if you want some money
ID: 3767535 • Letter: P
Question
Please give an example of this program running fully and if you want some money to make this program please leave a comment with your email and I'll email you. I'll pay through XOOM.
TITLE
IMPLEMENTING AND MANIPULATING EXPRESSION TREES
INTRODUCTION
A binary tree is a tree in which each node may have up to two children, and these children are distinguished as the left child and the right child. Binary trees may represent arithmetic expressions involving binary operators. Expressions represented in this way are easy to process recursively, and an expression tree can be scanned to produce preorder, inorder, and postorder versions of the expression it represents.
DESCRIPTION
Design, implement, test, and document a program that implements and exercises expression trees. Use a (non-template) class to provide an ExpressionTree type. The class will implement the tree type as a linked binary tree. Interior nodes will hold operators --- +, -, *, / --- and leaves will hold operands; that is, the values of single digits: 0, 1, 2, ... , 9. The main program will open a file, named by the user, that contains fully parenthesized infix expressions, one per line. These expressions must use single digits as numerical operands. The program will then call class member functions to print prefix, infix, and postfix versions of each expression and its integer value.
INPUT
The program will read the name of the input file from the terminal and infix expressions from the named file. White space in the input expressions should have no effect on the results.
OUTPUT
The program will prompt for the name of the data file and will print to the terminal prefix, infix, and postfix versions of the expressions read from the data file as well as their values.
ERRORS
The program can assume that the input is as described, in particular that data files contain correct fully-parenthesized infix expressions. The program should be able to handle white space in the input file. Otherwise, it need not detect any errors.
EXAMPLE
If the data file data.dat contains these lines:
then a run of the program might look like this:
OTHER REQUIREMENTS
The implementation of the ExpressionTree type must be encapsulated in a class. In addition to a default constructor, a destructor, and a function that re-initializes an existing tree to be empty, the class must include these functions:
build_tree(in_f) - Read a fully-parenthesized infix expression from the file in_f and build the corresponding expression tree. The invoking tree becomes the expression tree.
pre_order(out_f) - Print to the output stream out_f the prefix version of the expression that the invoking tree represents.
in_order(out_f) - Print to the output stream out_f the infix version of the expression that the invoking tree represents.
post_order(out_f) - Print to the output stream out_f the postfix version of the expression that the invoking tree represents.
value() - Return the integer value of the expression that the invoking tree represents.
Write recursive procedures to carry out the three printing operations, and note that the infix procedure must print left and right parentheses at the appropriate times. The evaluation and tree-building functions must also be recursive.
Do NOT use the examples above as test cases for your program. You must design your own tests.
HINTS
When recursive functions operate on pointer-based class objects, as here, there must be two functions: a public one and a recursive private one that the public one calls.
My Current Code (Has errors in the header file the lower functions are not in a class when they should be in a class and it doesn't end like a normal header file. Plus it doesn't read from the file so I don't know if the printing functions are working or not) :
////Header File Code////
#include <bits/stdc++.h>
using namespace std;
// An expression tree node
class ExpressionTree
{
public:
char value;
bool isLeaf;
ExpressionTree *left , *right;
};
int isOperator(char c);
int whichbrace(char c);
int isnumeral(char c);
int calculate(int a, int b, char c);
// Utility function to do inorder traversal
void inorder(ExpressionTree *t);
void postorder(ExpressionTree *t);
void preorder(ExpressionTree *t);
int findValue(ExpressionTree * t);
// A utility function to create a new node
ExpressionTree* createNode();
// Returns root of constructed tree for given
// postfix expression
ExpressionTree* constructTree(char *expression);
// Driver program to test above
// A utility function to check if 'c'
// is an operator
///////Expression Tree Class Implementation file////
#include <bits/stdc++.h>
#include "BinaryTree.h"
using namespace std;
int isOperator(char c)
{
if (c == '+' || c == '-' ||
c == '*' || c == '/' )
return 1;
return 0;
}
int whichbrace(char c)
{
if(c=='(')
{
return 0;
}
else if(c==')')
{
return 1;
}
else return 2;
}
int isnumeral(char c)
{
return isdigit(c);
}
int calculate(int a, int b, char c){
if(c=='+'){
return a+b;
}
if(c=='-'){
return a-b;
}
if(c=='*'){
return a*b;
}
if(c=='/'){
return a/b;
}
}
// Utility function to do inorder traversal
void inorder(ExpressionTree *t)
{
if(t==NULL){
return;
}
else
{
if(t->left!=NULL)
{
printf("( ");
inorder(t->left);
}
printf("%c ", t->value);
if(t->right!=NULL)
{
inorder(t->right);
printf(") ");
}
}
}
void postorder(ExpressionTree *t)
{
if(t==NULL){
return;
}
else if(t->isLeaf){
printf("%c ", t->value);
}
else
{
postorder(t->left);
postorder(t->right);
printf("%c ", t->value);
}
}
void preorder(ExpressionTree *t)
{
if(t==NULL){
return;
}
else if(t->isLeaf){
printf("%c ", t->value);
}
else
{
printf("%c ", t->value);
preorder(t->left);
preorder(t->right);
}
}
int findValue(ExpressionTree * t)
{
// printf (string(t->value));
// printf("sdaf");
if(t==NULL){
return 0;
}
else if(t->isLeaf==1){
return (t->value) -'0';
}
else
{
return calculate(findValue(t->left),findValue(t->right),t->value);
}
}
// A utility function to create a new node
ExpressionTree* createNode()
{
ExpressionTree *node = new ExpressionTree;
node->left = node->right = NULL;
return node;
};
// Returns root of constructed tree for given
// postfix expression
ExpressionTree* constructTree(char *expression)
{
stack<ExpressionTree *> stack0;
ExpressionTree *t, *t1, *t2, *t3;
//iterating on the input string
for (int i=0; i<strlen(expression); i++)
{
//push number
if(whichbrace(expression[i])==0)
{
//do nothing
}
else if(whichbrace(expression[i])==1)
{
t = createNode();
t->isLeaf =false;
// Pop 1)number , 2)operator and another 3)number
t1 = stack0.top();
stack0.pop();
t2 = stack0.top();
stack0.pop();
t3 = stack0.top();
stack0.pop();
t->left = t3;
t->right = t1;
t->value = t2->value;
stack0.push(t);
}
//number
else if (isnumeral(expression[i]))
{
t = createNode();
t->isLeaf =true;
t->value = expression[i];
stack0.push(t);
}
//operator
else if(isOperator(expression[i]))
{
t = createNode();
t->isLeaf =false;
t->value = expression[i];
stack0.push(t);
}
}
// pop the bult tree
t = stack0.top();
stack0.pop();
return t;
}
// Driver program to test above
/////////main File implementation Code/////
#include <bits/stdc++.h>
#include "BinaryTree.h"
using namespace std;
int main(int arg,char* args[1])
{
ifstream myReadFile(args[1]);
string line;
while(std::getline(myReadFile, line))
{
char* infix = strdup(line.c_str());
ExpressionTree* r = constructTree(infix);
printf("Preorder: ");
preorder(r);
printf(" ");
printf("Inorder: ");
inorder(r);
printf(" ");
printf("Postorder: ");
postorder(r);
printf(" ");
int val = findValue(r);
printf("Value: ");
printf("%d ",val );
printf(" ");
printf(" ");
}
return 0;
}
Explanation / Answer
// ExpressionTree.h
#include <iostream>
#include <cstdlib>
#include <string>
#include <fstream>
using namespace std;
// class TreeNode
class TreeNode
{
public:
char data;
TreeNode *left, *right;
// Constructor
TreeNode(char data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
// class StackNode
class StackNode
{
public:
TreeNode *treeNode;
StackNode *next;
// Constructor
StackNode(TreeNode *treeNode)
{
this->treeNode = treeNode;
next = NULL;
}
};
class ExpressionTree
{
private:
StackNode *top;
/** function to check if digit **/
bool isDigit(char ch)
{
return ch >= '0' && ch <= '9';
}
/** function to check if operator **/
bool isOperator(char ch)
{
return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}
/** function to convert character to digit **/
int toDigit(char ch)
{
return ch - '0';
}
// private recursive function to generate pre order expression
void pre_order(TreeNode *ptr, ofstream *out_f)
{
if (ptr != NULL)
{
*out_f<<ptr->data;
pre_order(ptr->left, out_f);
pre_order(ptr->right, out_f);
}
}
// private recursive function to generate in order expression
void in_order(TreeNode *ptr, ofstream *out_f)
{
if (ptr != NULL)
{
in_order(ptr->left, out_f);
*out_f<<ptr->data;
in_order(ptr->right, out_f);
}
}
// private recursive function to generate post order expression
void post_order(TreeNode *ptr, ofstream *out_f)
{
if (ptr != NULL)
{
post_order(ptr->left, out_f);
post_order(ptr->right, out_f);
*out_f << ptr->data;
}
}
/** function to push a node **/
void push(TreeNode *ptr)
{
if (top == NULL)
top = new StackNode(ptr);
else
{
StackNode *nptr = new StackNode(ptr);
nptr->next = top;
top = nptr;
}
}
/** function to pop a node **/
TreeNode *pop()
{
if (top == NULL)
{
cout<<"Underflow"<<endl;
}
else
{
TreeNode *ptr = top->treeNode;
top = top->next;
return ptr;
}
}
/** function to get top node **/
TreeNode *peek()
{
return top->treeNode;
}
/** function to insert character **/
void insert(char val)
{
if (isDigit(val))
{
TreeNode *nptr = new TreeNode(val);
push(nptr);
}
else if (isOperator(val))
{
TreeNode *nptr = new TreeNode(val);
nptr->left = pop();
nptr->right = pop();
push(nptr);
}
else
{
// neglect space and braces
}
}
// private recursive function to evaluate value of expression
double value(TreeNode *ptr)
{
if (ptr->left == NULL && ptr->right == NULL)
return toDigit(ptr->data);
else
{
double result = 0.0;
double left = value(ptr->left);
double right = value(ptr->right);
char op = ptr->data;
switch (op)
{
case '+':
result = left + right;
break;
case '-':
result = left - right;
break;
case '*':
result = left * right;
break;
case '/':
result = left / right;
break;
default:
result = left + right;
break;
}
return result;
}
}
public:
// constructor
ExpressionTree()
{
// initialize top of the stack to null
top = NULL;
}
/** function to re-initialize tree **/
void re_initialize()
{
top = NULL;
}
/** function to build tree from input file*/
void build_tree(string eqn)
{
for (int i = eqn.length() - 1; i >= 0; i--)
insert(eqn[i]);
}
// Public function to calculate value of expression
double value()
{
return value(peek());
}
// Public function to generate post order expression
void post_order(ofstream *out_f)
{
post_order(peek(), out_f);
}
// Public function to generate in order expression
void in_order(ofstream *out_f)
{
in_order(peek(), out_f);
}
// Public function to generate pre order expression
void pre_order(ofstream *out_f)
{
pre_order(peek(), out_f);
}
};
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
// ExpressionTree.cpp
#include <iostream>
#include <fstream>
#include <string>
#include "ExpressionTree.h"
using namespace std;
int main()
{
string input_filename, output_filename;
string eqn;
ExpressionTree *et = new ExpressionTree();
cout << "Enter the file name with equations : ";
cin >> input_filename;
cout << "Enter the output file name to print the rsults : ";
cin >> output_filename;
std::ifstream fin;
fin.open(input_filename.c_str());
std::ofstream fout;
fout.open(output_filename.c_str());
while(getline(fin, eqn))
{
et->build_tree(eqn);
et->pre_order(&fout);
et->in_order(&fout);
et->post_order(&fout);
fout << "Value = " << et->value() << endl;
}
fin.close();
fout.close();
return 0;
}