Hey guys. I have a C++ lab that I cannot solve. Please help me! It will be in my
ID: 3841465 • Letter: H
Question
Hey guys. I have a C++ lab that I cannot solve. Please help me! It will be in my final grade.
Tree Parser
Here are the links to some sources of this lab:
Use the code at http://www.csit.parkland.edu/~kurban/permanent/cpp-examples/treeLab/
You will need a binary tree (either my code or from the web): http://www.csit.parkland.edu/~kurban/csc125/binarySearchTree/
You can run it at http://www.csit.parkland.edu/~kurban/permanent/cpp-examples/treeLab/tree.html
Links on the tree traversals:
http://algoviz.org/OpenDSA/Books/OpenDSA/html/BinaryTreeTraversal.html# (You don't need to sign in)
http://www.geeksforgeeks.org/618/
https://en.wikibooks.org/wiki/A-level_Computing/AQA/Paper_1/Fundamentals_of_algorithms/Tree_traversal
Here are the lab handouts:
Here is all the information I have. If there is any place not clear, please let me know and indicate the place. Thanks!
Tree Parser Lab 10Explanation / Answer
main.cpp
/* to use this,
- write a form that calls this program with 'action=' in the <form> tag
- call getPostData()
- use getField(string) to access form information
*/
#include <iostream>
#include <string>
#include <cstdlib>
#include "htmlform.h"
//#include "binarysearchtree.h"
using namespace std;
struct Node
{
pair<int, string> data;
Node* right;
Node* left;
private:
};
class BinarySearchTree
{
public:
BinarySearchTree()
{
m_Root = NULL;
}
~BinarySearchTree(){erase();}
BinarySearchTree(const BinarySearchTree& other);
void print();
void inorder();
void preorder();
void postorder();
bool empty()
{
return m_Root == NULL;
}
void insert(pair<int, string> data);
void erase(){eraseHelper(m_Root); m_Root = NULL;}
protected:
private:
void insertHelper(Node* &n, pair<int, string> data);
void printHelper(Node* n);
void preorderHelper1(Node* n);
void preorderHelper2(Node* n);
void inorderHelper1(Node* n);
void inorderHelper2(Node* n);
void postorderHelper1(Node* n);
void postorderHelper2(Node* n);
Node* copyHelper(Node* oldNode);
void eraseHelper(Node* n);
Node* m_Root;
};
void printProgram(string program); /// print the program in HTML
void parseProgram(string program, BinarySearchTree& btree);
void parse(string line, BinarySearchTree& btree);
using namespace std;
int main()
{
/// complete the http header
cout << "Content-type: text/html ";
/// build a form object
HTMLform steps;
steps.getPostData();
/// Show the debugging
cout << "Binary Search Tree Parser Lab startup" << endl;
steps.debug();
/// the entire programs
string program = steps.getField("program");
//string program = "INSERT 25, BRYNA INSERT 15, BRYNA INSERT 50, BRYNA INSERT 10, BRYNA INSERT 22, BRYNA INSERT 35, BRYNA INSERT 70, BRYNA POSTORDER INORDER PREORDER ";
printProgram(program);
BinarySearchTree btree;
parseProgram(program,btree);
return 0;
}
void printProgram(string program)
{
/// a single line
string line;
/// for counting the lines
int count = 0;
/// where the newline is (for peeling off a line)
int pos;
while ( string::npos != (pos = program.find(" ") ) )
{
line = program.substr(0, pos); /// before the newline
program = program.substr(pos+1); /// after the newline
/// there might newline characters at the end of line
if (line[pos] < '0') line.erase(pos-1);
/// here's where you need to process 'line'
/// this routine just prints it.
//cout << ++count << ": [" << line << "] len=" << line.size()<< "<br />" << endl;
}
}
void parseProgram(string program, BinarySearchTree& btree)
{
string line;
int count = 0;
int pos;
while ( string::npos != (pos = program.find(" ") ) )
{
line = program.substr(0, pos);
program = program.substr(pos+1);
if (line[pos] < '0')
line.erase(pos-1);
parse(line,btree);
cout << ++count << ": [" << line << "] len=" << line.size()<< "<br />" << endl;
}
}
void parse(string line, BinarySearchTree& btree)
{
if (line.substr(0,6) == "INSERT")
{
int commaPos = line.find(",");
string value, str;
value = line.substr(7,commaPos);
str = line.substr(commaPos+2);
// convert string to integer;
int key = atoi(value.c_str());
btree.insert(make_pair(key,str));
}
else if (line == "POSTORDER")
{
if (btree.empty())
{
cerr << "Empty tree." << endl;
}
btree.postorder();
}
else if (line == "PREORDER")
{
if (btree.empty())
{
cerr << "Empty tree." << endl;
}
btree.preorder();
}
else if (line == "INORDER")
{
if (btree.empty())
{
cerr << "Empty tree." << endl;
}
btree.inorder();
}
else if (line == "PRINT")
{
btree.print();
}
else
{
cerr << "Error: invalid command " << line << endl;
exit(1);
}
return;
}
void BinarySearchTree::print()
{
if (empty())
{
std::cout << "Empty Tree" << std::endl;
}
else
{
printHelper(m_Root);
}
}
void BinarySearchTree::printHelper(Node* n)
{
if (n == NULL) return;
/// in order traversal of the tree
printHelper(n->left);
std::cout << n->data.first << ", " << n->data.second << endl;
printHelper(n->right);
}
void BinarySearchTree::insert(pair<int, string> data)
{
insertHelper(m_Root, data);
}
void BinarySearchTree::insertHelper(Node* &n, pair<int, string> data)
{
// insert 'data' into a tree pointed to by 'n'
// if n is null, it goes here
if (n == NULL)
{
n = new Node;
n->data.first = data.first;
n->data.second = data.second;
n->left = NULL;
n->right = NULL;
return;
}
// n is not null, so we can check left & right
if (data.first < n->data.first)
{
insertHelper(n->left,data);
}
else if ((data.first == n->data.first) && data.second < n->data.second)
{
insertHelper(n->left,data);
}
else
{
insertHelper(n->right,data);
}
}
void BinarySearchTree::inorder()
{
if (empty())
{
std::cout << "Empty Tree" << std::endl;
}
else
{
inorderHelper1(m_Root);
cout << "<br>"<<endl;
inorderHelper2(m_Root);
}
}
void BinarySearchTree::inorderHelper1(Node* n)
{
if (n == NULL) return;
/// in order traversal of the tree
inorderHelper1(n->left);
std::cout << n->data.first << " " ;
inorderHelper1(n->right);
}
void BinarySearchTree::inorderHelper2(Node* n)
{
if (n == NULL) return;
/// in order traversal of the tree
inorderHelper2(n->left);
std::cout << n->data.second << " ";
inorderHelper2(n->right);
}
void BinarySearchTree::preorder()
{
if (empty())
{
std::cout << "Empty Tree" << std::endl;
}
else
{
preorderHelper1(m_Root);
cout << "<br>" << endl;
preorderHelper2(m_Root);
}
}
void BinarySearchTree::preorderHelper1(Node* n)
{
if (n == NULL) return;
/// pre order traversal of the tree
std::cout << n->data.first << " " ;
preorderHelper1(n->left);
preorderHelper1(n->right);
}
void BinarySearchTree::preorderHelper2(Node* n)
{
if (n == NULL) return;
/// pre order traversal of the tree
std::cout << n->data.second << " " ;
preorderHelper2(n->left);
preorderHelper2(n->right);
}
void BinarySearchTree::postorder()
{
if (empty())
{
std::cout << "Empty Tree" << std::endl;
}
else
{
postorderHelper1(m_Root);
cout << "<br>" << endl;
postorderHelper2(m_Root);
}
}
void BinarySearchTree::postorderHelper1(Node* n)
{
if (n == NULL) return;
/// post order traversal of the tree
postorderHelper1(n->left);
postorderHelper1(n->right);
std::cout << n->data.first << " ";
}
void BinarySearchTree::postorderHelper2(Node* n)
{
if (n == NULL) return;
/// post order traversal of the tree
postorderHelper2(n->left);
postorderHelper2(n->right);
std::cout << n->data.second <<" ";
}
BinarySearchTree::BinarySearchTree(const BinarySearchTree& other)
{
m_Root = copyHelper(other.m_Root);
}
Node* BinarySearchTree::copyHelper(Node* oldNode)
{
if (oldNode == NULL) return NULL;
/// otherwise build a new node
Node* newNode = new Node();
newNode->data.first = oldNode->data.first;
newNode->data.second = oldNode->data.second;
newNode->left = copyHelper(oldNode->left);
newNode->right = copyHelper(oldNode->right);
return newNode;
}
void BinarySearchTree::eraseHelper(Node* n)
{
if (!n) return;
eraseHelper(n->left);
eraseHelper(n->right);
delete n;
return;
}
htmlform.cpp
#include <iostream>
#include "htmlform.h"
using namespace std;
const char DEC2HEX[16 + 1] = "0123456789ABCDEF";
const char HEX2DEC[256] =
{
/* 0 1 2 3 4 5 6 7 8 9 A B C D E F */
/* 0 */ -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1,
/* 1 */ -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1,
/* 2 */ -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1,
/* 3 */ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,-1,-1, -1,-1,-1,-1,
/* 4 */ -1,10,11,12, 13,14,15,-1, -1,-1,-1,-1, -1,-1,-1,-1,
/* 5 */ -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1,
/* 6 */ -1,10,11,12, 13,14,15,-1, -1,-1,-1,-1, -1,-1,-1,-1,
/* 7 */ -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1,
/* 8 */ -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1,
/* 9 */ -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1,
/* A */ -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1,
/* B */ -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1,
/* C */ -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1,
/* D */ -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1,
/* E */ -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1,
/* F */ -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1
};
void HTMLform::debug()
{
cout << "<hr />";
cout << "Version 1 from 9/23/15" << endl;
cout << "we read in [" << m_PostData << "]";
cout << "<br />Table:<br />";
cout << "<table border='1'>";
for (int i=0;i<m_Pairs.size();i++)
{
cout << "<tr>";
cout << "<td>[";
cout << m_Pairs[i].getName();
cout << "]</td>";
cout << "<td>[";
cout << m_Pairs[i].getValue();
cout << "]</td>";
cout << "</tr>";
}
cout << "</table>";
cout << "<hr />";
}
void HTMLform::getPostData()
{
getline(cin, m_PostData);
/// store those lines in m_Pairs
/* format:
name1=value1&name2=value2&name3=value3...
*/
string postData = m_PostData;
string firstPair;
int pos;
while (postData.length() > 1)
{
//cout << "Debug: postData [" << postData << "]<br />";
pos = postData.find("&");
if (pos != string::npos)
{
firstPair = postData.substr(0, pos);
postData.erase(0, pos+1);
processPair(firstPair);
}
else
{
processPair(postData);
postData.clear();
}
}
}
void HTMLform::processPair(string nvpair)
{
//cout << "Debug: nvpair [" << nvpair << "]<br />";
NameValuePair temp;
string first;
string second;
int pos = nvpair.find("=");
first = nvpair.substr(0,pos);
second = nvpair.substr(pos+1); /// until the end
/// before url decode !!!
//cout << "Debug: first [" << first << "]<br />";
//cout << "Debug: second [" << second << "]<br />";
first = urlDecode(first);
second = urlDecode(second);
/// after url decode !!!
//cout << "Debug: decoded first [" << first << "]<br />";
//cout << "Debug: decoded second [" << second << "]<br />";
temp.setName(first);
temp.setValue(second);
m_Pairs.push_back(temp);
//cout << "Debug: pairs stored = [" << m_Pairs.size() << "]<br />";
}
string HTMLform::urlDecode(string &sSrc)
{
/// turn plus signs into spaces first
int pos;
while ( (pos = sSrc.find("+")) != string::npos)
{
sSrc[pos]=' ';
}
const unsigned char * pSrc = (const unsigned char *)sSrc.c_str();
const int SRC_LEN = sSrc.length();
const unsigned char * const SRC_END = pSrc + SRC_LEN;
// last decodable '%'
const unsigned char * const SRC_LAST_DEC = SRC_END - 2;
char * const pStart = new char[SRC_LEN];
char * pEnd = pStart;
while (pSrc < SRC_LAST_DEC)
{
// cout << "DECODE: " << *pSrc << "<br />";
if (*pSrc == '%')
{
char dec1, dec2;
if (-1 != (dec1 = HEX2DEC[*(pSrc + 1)])
&& -1 != (dec2 = HEX2DEC[*(pSrc + 2)]))
{
*pEnd++ = (dec1 << 4) + dec2;
pSrc += 3;
continue;
}
}
*pEnd++ = *pSrc++;
}
// the last 2- chars
while (pSrc < SRC_END)
*pEnd++ = *pSrc++;
std::string sResult(pStart, pEnd);
delete [] pStart;
//cout << "DECODE DONE: " << sResult << "<br />";
return sResult;
}
string HTMLform::getField(string field)
{
string retValue;
for (int i=0;i<m_Pairs.size();i++)
{
if (m_Pairs[i].getName() == field) retValue= m_Pairs[i].getValue();
}
return retValue;
}
htmlform.h
#include <string>
#include <vector>
#include "namevaluepair.h"
using namespace std;
class HTMLform
{
public:
void debug();
void getPostData();
string getField(string);
private:
void processPair(string);
string urlDecode(string&);
string m_PostData;
vector<NameValuePair> m_Pairs;
};
namevaluepair.h
#include <string>
using namespace std;
class NameValuePair
{
public:
// setter & getters
string getName() {return m_Name;}
string getValue() {return m_Value;}
void setName(string data) {m_Name=data;}
void setValue(string data) {m_Value=data;}
private:
string m_Name;
string m_Value;
};
tree.html
<html>
<head>
</head>
<body>
<table>
<tr>
<td>
<form method="POST" action="runme.cgi">
Enter your program below (up/down scrolling is permitted, avoid left/right scrolling) <br/ >
<textarea name="program" rows="20" cols="40" wrap="soft">
</textarea> <br/ >
<input type="submit"> <br/ >
</form>
</td>
<td>
<table>
<tr>
<th>Valid Commands:</th><th> What it does: </th>
</tr>
<tr>
<td>INSERT <i>value, string</i></td><td>Adds <i>string</i> to the tree at the places determined by <i>value</i>. Nothing needs to be displayed. The <i>value</i> is an integer after the space after INSERT and the <i>string</i> is after ther comma until the end of the line.</td>
</tr>
<tr>
<td>PREORDER</td><td>displays the contents of entire tree across the screen as a table with two rows using a <i>preorder traversal</i>. The first row contains the value and the second row contains the strings. (You'll likely need separate routines to print each row) </td>
</tr>
<tr>
<td>INORDER</td><td>displays the contents of entire tree across the screen as a table with two rows using an <i>inorder traversal</i>. The first row contains the value and the second row contains the strings. (You'll likely need separate routines to print each row) </td>
</tr>
<tr>
<tr>
<td>POSTORDER</td><td>displays the contents of entire tree across the screen as a table with two rows using an <i>postorder traversal</i>. The first row contains the value and the second row contains the strings. (You'll likely need separate routines to print each row) </td>
</tr>
<tr><td colspan="2">Any other commands will display that an invalid command was entered, the command will be displayed and exit the program.
</td></tr>
<tr>
<td>PRINT</td><td><b>EXTRA CREDIT, OPTIONAL</b> displays the contents of entire tree so it look like the tree really looks. You can limit yourself to 10 levels. You might consider using the HTMLTable class you wrote earlier in the semester. Arrows aren't necessary, but are extra nice. Sideways is ok too. </td>
</tr>
</table>
</td></tr>
</body>
</html>