-- 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 in-order traversal or vertical output using level-traversal.
or you print to a char 2d-array 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.experts-exchange.com/questions/25014702/Help-on-Algorith-for-parsing-an-in-put-string-in-a-binary-tree.html