 5

*

  3
 
 +

 1
template<class object>
void BinaryNode<object>::print_tree(BinaryNode<object> *tree, int size)
{
size *= 2;
int left_size = size  2;
int right_size = size + 2;
if(tree == NULL)
return;
cout<<setfill(' ')<<setw(size);
cout<<*tree>data<<endl;
if(tree>left!= NULL)
{
cout<<setfill(' ')<<setw(size);
cout<<"/"<<endl;
cout<<setfill(' ')<<setw(left_size);
print_tree(tree>left, left_size);
}
else if(tree>right != NULL)
{
cout<<setfill(' ')<<setw(size);
cout<<"'\'"<<endl;
cout<<setfill(' ')<<setw(right_size);
print_tree(tree>right, right_size);
}
}
either need horizontial output using inorder traversal or vertical output using leveltraversal.
or you print to a char 2darray in memory where you can move up in rows when necessary.
#ifndef BINARYNODE_H
#define BINARYNODE_H
#include<iomanip>
#include<iostream>
#include<queue>
#include<string>
template<class object>
class BinaryNode
{
public:
BinaryNode(object&);
BinaryNode(BinaryNode<object> * , int );
void breadth_first_search(BinaryNode<object> *);
void spacing(char, int);
int level;
object *data;
BinaryNode<object> *left;
BinaryNode<object> *right;
};
template<class object>
BinaryNode<object>::BinaryNode(object& node)
{
data = &node;
left = NULL;
right = NULL;
}
template<class object>
BinaryNode<object>::BinaryNode(BinaryNode<object> *node, int size)
{
breadth_first_search(node);
}
template<class object>
void BinaryNode<object>::breadth_first_search(BinaryNode<object> *node)
{
int level_count=0;
node>level=level_count;
queue<BinaryNode*> queue_node;
queue_node.push(node);
spacing('\t', node>level);
cout<<*node>data;
while(!queue_node.empty())
{
node = queue_node.front();
if(node>left != NULL)
{ int left_level_count =node>level;
node>left>level = ++left_level_count;
queue_node.push(node>left);
spacing('\t',node>left>level);
cout<<*node>left>data;
}
if(node>right != NULL)
{
int right_level_count = node>level;
node>right>level = ++right_level_count;
queue_node.push(node>right);
spacing('\t',node>right>level);
cout<<*node>right>data;
}
//cout<<*node>data<<endl;
queue_node.pop();
}
}
template<class object>
void BinaryNode<object>::spacing(char space, int data)
{
for(int i = 0; i<data; i++)
cout<<space;
}
#endif
#ifndef STACKLI_H_
#define STACKLI_H_
#include <stdlib.h>
#include<exception>
using namespace std;
#include"BinaryNode.h"
//#include "Except.h"
// Stack class  linked list implementation.
//
// CONSTRUCTION: with no parameters.
//
// ******************PUBLIC OPERATIONS*********************
// void push( x ) > Insert x
// void pop( ) > Remove most recently inserted item
// Object top( ) > Return most recently inserted item
// Object topAndPop( ) > Return and remove most recently inserted item
// bool isEmpty( ) > Return true if empty; else false
// void makeEmpty( ) > Remove all items
// ******************ERRORS********************************
// UnderflowException thrown as needed.
template <class Object>
class Stack
{
public:
Stack( );
Stack( const Stack & );
~Stack( );
bool isEmpty( ) const;
const Object & top( ) const;
void makeEmpty( );
void pop( );
void push( const Object & );
Object topAndPop( );
const Stack & operator=( const Stack & );
private:
struct ListNode
{
Object element;
ListNode *next;
ListNode( const Object & theElement, ListNode * n = NULL )
: element( theElement ), next( n ) { }
};
ListNode *topOfStack;
};
//#include "StackLi.cpp"
// Construct the stack.
template <class Object>
Stack<Object>::Stack( )
{
topOfStack = NULL;
}
// Copy constructor.
template <class Object>
Stack<Object>::Stack( const Stack<Object> & rhs )
{
topOfStack = NULL;
*this = rhs;
}
template<>
Stack<BinaryNode<char>*>::Stack()
{
topOfStack = NULL;
}
// Destructor.
template <class Object>
Stack<Object>::~Stack( )
{
makeEmpty( );
}
// Test if the stack is logically empty.
// Return true if empty, false, otherwise.
template <class Object>
bool Stack<Object>::isEmpty( ) const
{
return topOfStack == NULL;
}
// Make the stack logically empty.
template <class Object>
void Stack<Object>::makeEmpty( )
{
while( !isEmpty( ) )
pop( );
}
// Return the most recently inserted item in the stack.
// or throw an UnderflowException if empty.
template <class Object>
const Object & Stack<Object>::top( ) const
{
//if( isEmpty( ) )
//throw UnderflowException( );
return topOfStack>element;
}
// Remove the most recently inserted item from the stack.
// Throw Underflow if the stack is empty.
template <class Object>
void Stack<Object>::pop( )
{
// if( isEmpty( ) )
// throw UnderflowException( );
ListNode *oldTop = topOfStack;
topOfStack = topOfStack>next;
delete oldTop;
}
// Return and remove the most recently inserted item
// from the stack.
template <class Object>
Object Stack<Object>::topAndPop( )
{
Object topItem = top( );
pop( );
return topItem;
}
// Insert x into the stack.
template <class Object>
void Stack<Object>::push( const Object & x )
{
topOfStack = new ListNode( x, topOfStack );
}
// Deep copy.
template <class Object>
const Stack<Object> & Stack<Object>::operator=( const Stack<Object> & rhs )
{
if( this != &rhs )
{
makeEmpty( );
if( rhs.isEmpty( ) )
return *this;
ListNode *rptr = rhs.topOfStack;
ListNode *ptr = new ListNode( rptr>element );
topOfStack = ptr;
for( rptr = rptr>next; rptr != NULL; rptr = rptr>next )
ptr = ptr>next = new ListNode( rptr>element );
}
return *this;
}
#endif
#include<iostream>
#include<string>
#include<cstring>
#include<sstream>
#include<iterator>
#include<vector>
#include<algorithm>
using namespace std;
#include"StackLi.h"
#include"BinaryNode.h"
bool lower_procedence(char *tokenPtr, char top_of_stack)
{
// Checks if operaotr just read in is of higher or equal presedence
// than the operator next on the stack
bool flag = true;
if ((*tokenPtr == '+') && (top_of_stack == '+'))
{
flag = true;
}
else if ((*tokenPtr == '') && (top_of_stack == ''))
{
flag = true;
}
else if ((*tokenPtr == '') && (top_of_stack == '+') )
{
flag = true;
}
else if ((*tokenPtr == '+') && (top_of_stack == ''))
{
flag = false;
}
else if(((*tokenPtr == '+')  (*tokenPtr == '')) && ((top_of_stack == '*')  (top_of_stack == '/')))
{
flag= true;
}
else if ((*tokenPtr == '*') && (top_of_stack == '/'))
{
flag = false;
}
else if ((*tokenPtr == '*') && (top_of_stack == '*'))
{
flag = true;
}
else if ((*tokenPtr == '/') && (top_of_stack == '/'))
{
flag = true;
}
else if ((*tokenPtr == '/') && (top_of_stack == '*'))
{
flag = true;
}
else if(((*tokenPtr == '*')  (*tokenPtr == '/')) && ((top_of_stack == '+')  (top_of_stack == '')))
{
flag= false;
}
else if((*tokenPtr == ')')&& (top_of_stack != '(') )
{
flag= false;
}
else if ((*tokenPtr == ')') && ( top_of_stack == '('))
{
flag = true;
}
else if(top_of_stack == '(')
flag = false;
else
flag = true;
return flag;
}
int main()
{
Stack<char> * operator_Stack = new Stack<char>;
Stack<BinaryNode<char>*> * ptrStack = new Stack<BinaryNode<char>*>;
char equation[50];
char* tokenPtr;
//vector<char> postfix_Equations(1, 0);
vector<char> postfix_Equations;
cout<<"Please Enter In A Equation"<<endl;
cin.getline(equation, sizeof(equation), '\n');//To catch all of the char p
tokenPtr = strtok(equation," ");
while(tokenPtr != NULL)
{
if( *tokenPtr == '+'  *tokenPtr==''  *tokenPtr == '/'  *tokenPtr == '*'  *tokenPtr == '^')
{
while(!operator_Stack>isEmpty())
{
if(lower_procedence(tokenPtr, operator_Stack>top()))
{
postfix_Equations.push_back(operator_Stack>topAndPop());
}
else
{
operator_Stack>push(*tokenPtr);
break;
}
}
if(operator_Stack>isEmpty())
operator_Stack>push(*tokenPtr);
}
else if (*tokenPtr == '(')
operator_Stack>push(*tokenPtr);
else if(*tokenPtr == ')')
{
while((operator_Stack>top() != '(')&& (!operator_Stack>isEmpty()))
postfix_Equations.push_back(operator_Stack>topAndPop());
if( operator_Stack>top() == '('  operator_Stack>top() == ')' )
{
operator_Stack>pop();
}
}
else if(isalpha(*tokenPtr)  isalnum(*tokenPtr))
postfix_Equations.push_back(*tokenPtr);
tokenPtr = strtok(NULL, " ");
}
if(!operator_Stack>isEmpty())
{
while(!operator_Stack>isEmpty())
postfix_Equations.push_back(operator_Stack>topAndPop());
}
cout<<"\nPostfix Equation\n"<<endl;
for(int i =0; i!= postfix_Equations.size(); i++)
cout<<postfix_Equations[i];
cout<<"\n"<<endl;
//End of POSTFIX
for(int i = 0; i < postfix_Equations.size(); i++)
{
if(postfix_Equations[i] == '('  postfix_Equations[i] == ')'  postfix_Equations[i] == '+'  postfix_Equations[i]==''  postfix_Equations[i] == '/'  postfix_Equations[i] == '*'  postfix_Equations[i] == '^')
{
if(ptrStack>isEmpty())
{
BinaryNode<char> *newNode = new BinaryNode<char>(postfix_Equations[i]);
ptrStack>push(newNode);
}
else
{
BinaryNode<char> *newNode = new BinaryNode<char>(postfix_Equations[i]);
newNode>right = ptrStack>topAndPop();
if(!ptrStack>isEmpty())
{
newNode>left = ptrStack>topAndPop();
}
ptrStack>push(newNode);
}
}
else if(postfix_Equations[i] == '~'  postfix_Equations[i] == '!'  postfix_Equations[i] == '&')
{
BinaryNode<char> *newNode = new BinaryNode<char>(postfix_Equations[i]);
newNode>right = ptrStack>topAndPop();
ptrStack>push(newNode);
}
else
{
BinaryNode<char> *newNode = new BinaryNode<char>(postfix_Equations[i]);
ptrStack>push(newNode);
}
tokenPtr = strtok(NULL, " ");
}
BinaryNode<char> *finalNode = new BinaryNode<char>(ptrStack>topAndPop(), postfix_Equations.size());
system("PAUSE");
return 0;
}
xyz uvw
abc def ghi jkl
https://www.expertsexchange.com/questions/25014702/HelponAlgorithforparsinganinputstringinabinarytree.html