Narue
Bad Cop
Administrator
15,460 posts since Sep 2004
Reputation Points: 6,464
Solved Threads: 1,401
Have something to say? Contribute New Article Reply to this Article
Binary Expression Tree
Hey everyone,
I'm trying to make it so that my ^ operator is right justified within this binary expression tree.
For example, 2^3^4 should be evaluated as 2^(3^4). So I should get 2^81, instead of the usual 2^12.
Here is the code I have so far. Everything works, except the ^ is still left associative. I know this is a hard one, so if you don't have time to help me out it's no problem.
Thanks!
// btreeEx.h
// queue.h
// linked list implementation of Queue ADT
#include <cstddef> // for NULL
#include <new> // for bad_alloc exception
#include <iostream>
using namespace std;
template <class T>
struct Node; // forward reference, Node defined below
template<class T>
class Queue
{
private:
Node<T> * front; // pointer to front of Queue
Node<T> * rear; // pointer to rear of Queue
int length; // logical length of Queue
public:
Queue(); // default c-tor
~Queue(); // d-tor
void makeMT(); // make Queue logically empty
// Post: front and rear have been reset to the empty state
bool isMT() const; // test for Queue being empty
// returns true if the queue is empty; false otherwise
bool isFull() const; // test for Queue being full
// Returns true if the queue is full; false otherwise
void enqueue(T item); // enqueue an item
// Post: parameter item is at the rear of the queue
void dequeue(T & item); // dequeue an item
// Post: front of queue has been removed and a copy returned in item
int getLength() const; // returns length queue
// Post: Queue is unchanged
void replaceItem(T old, T nu); // replaces all occurrences of old with nu
// Pre: queue has been initialized
// Post: each occurrence of old in queue has been changed to nu
void prntQueue() const; // displays contents of queue
// Pre: queue has been initialized
// Post: contents of queue have been printed
}; // end Queue
// implementations
/*template <class T>
struct Node
{
T info;
Node<T> * next;
}; */
template<class T> // default class c-tor
Queue<T>::Queue() : front(NULL), rear(NULL), length(0)
{ }
template<class T> // d-tor
Queue<T>::~Queue()
{
makeMT();
}
template<class T>
void Queue<T>::makeMT()
{
Node <T> * temp;
while ( front != NULL ) {
temp = front;
front = front->next;
delete temp;
} // endwhile
rear = NULL;
length = 0;
return;
} // end makeMT()
template<class T>
bool Queue<T>::isMT() const
{
return ( length == 0 ); // alternative is to return ( front == NULL );
} // end isMT()
template<class T>
bool Queue<T>::isFull() const
{
Node<T> * location;
try {
location = new Node<T>;
delete location;
return false;
} // endtry
catch(bad_alloc exception)
{
return true;
} // endcatch
} // end isFull()
template<class T>
void Queue<T>::enqueue(T item)
{
Node<T> * newNode;
newNode = new Node<T>;
newNode->info = item;
newNode->next = NULL;
if ( rear == NULL )
front = newNode;
else
rear->next = newNode;
rear = newNode;
length++;
} // end enqueue()
template<class T>
void Queue<T>::dequeue(T & item)
{
Node<T> * temp;
temp = front;
item = front->info;
front = front->next;
if ( front == NULL )
rear = NULL;
delete temp;
length--;
return;
} // end dequeue()
template<class T>
int Queue<T>::getLength() const
{
return length;
} // end getLength()
template<class T>
void Queue<T>::replaceItem(T old, T nu)
{
Node<T> * location = front;
while ( location != NULL ) {
if ( location->info == old )
location->info = nu;
location = location->next;
} // endwhile
} // end replaceItem()
template<class T>
void Queue<T>::prntQueue() const
{
Node<T> * location = front;
cout << "\n Printing contents of queue:\n";
while ( location != NULL ) {
cout << "\t" << location->info;
location = location->next;
} // endwhile
cout << endl;
return;
} // end prntQueue()
// end Queue implementations
// stkxcptn.h - header file for PopOnMTStack and PushOnFullStack exception class
//#include <iostream>
//using namespace std;
class PopOnMTStack
{
private :
string msg;
public :
PopOnMTStack() // default c-tor
{
msg = string("\n Stack underflow - operation aborted");
}
const string message() const
{
return msg;
}
}; // end PopOnMTStack
class PushOnFullStack
{
private :
string msg;
public :
PushOnFullStack() // default c-tor
{
msg = string("\n Stack overflow - operation aborted");
}
const string message() const
{
return msg;
}
}; // end PopOnMTStack
// stack.h
// header file for Stack ADT using a templated linked list
//#pragma once
//#include "stkxcptn.h"
template <class T>
struct Node; // forward reference - struct Node is defined below
template<class T>
class Stack
{
private:
Node<T> * top;
public:
Stack();
~Stack();
void makeMT();
// Function: sets stack to an empty state
// Post: Stack is empty
bool isFull() const;
// Function: determines whether the stack is full
// Pre: Stack has been initialized
// Post: Function value = false (assuming new succeeds)
bool isMT() const;
// Function: determines whether the stack is empty
// Pre: Stack has been initialized
// Post: Function value = (stack is empty)
void push(T item);
// Function: adds item to the top of the stack
// Pre: Stack has been initialized
// Post: If (stack is full), PushOnFullStack exception is thrown;
// otherwise, item is at the top of the stack
void pop(T & item);
// Function: removes top item from the stack and returns it in item
// Pre: Stack has been initialized
// Post: If (stack is MT), PopOnMTStack exception is thrown;
// otherwise, top element has been removed from stack
void prntStack() const;
// Function: displays contents of the stack
// Pre: Stack has been initialized
// Post: Stack is walked and members printed
}; // end Stack
// Stack ADT - implementation using a templated linked list
//#include <cstddef>
//#include <new>
template <class T>
struct Node
{
T info; // Node data of type T
Node * next; // link to next Node
Node<T>() : info(0), next(NULL) // default c-tor for Node
{ }
Node<T>( const T & e, Node * nx = NULL ) // parameterized c-tor for Node
: info(e), next(nx)
{ }
}; // end Node
template<class T>
Stack<T>::Stack() : top(NULL)
{ }
template <class T>
Stack<T>::~Stack()
{
Node<T> * temp;
while ( top != NULL ) {
temp = top;
top = top->next;
delete temp;
} // endwhile
} // end ~Stack()
template<class T>
void Stack<T>::pop(T & item)
{
if ( isMT() )
throw PopOnMTStack();
else {
Node<T> * temp;
temp = top;
item = top->info;
top = top->next;
delete temp;
} // endif
} // end pop()
template<class T>
bool Stack<T>::isFull() const
{
Node<T> * location;
try {
location = new Node<T>;
delete location;
return false;
} // endtry
catch(bad_alloc exception)
{
return true;
} // endcatch
} // end isFull()
template <class T>
void Stack<T>::push(T item)
{
if ( isFull() )
throw PushOnFullStack();
else {
Node<T> * ptr;
ptr = new Node<T>(item);
ptr->next = top;
top = ptr;
} // endif
} // end push()
template <class T>
void Stack<T>::makeMT()
{
Node<T> * temp;
while ( top != NULL ) {
temp = top;
top = top->next;
delete temp;
} // endwhile
} // end makeMT()
template <class T>
bool Stack<T>::isMT() const
{
return ( top == NULL );
} // end isMT()
template <class T>
void Stack<T>::prntStack() const
{
Node<T> * ptr = top;
cout << "\n Walking the stack: "
while ( ptr != NULL ) {
cout << "\t" << ptr->info;
ptr = ptr->next;
} // endwhile
return;
} // end prntStack()
// file tree.h contains the definition of class Tree
// class is templated
#include <fstream>
#include <cmath> // for pow()
#include <string> // Assign #19
const char LAST_SYMBOL = '=';
enum OpType { OPERATOR, OPERAND };
struct InfoNode
{
OpType whichType; // type field
union // anonymous union
{
char operation;
double operand; // Assign #19 - change type from int to double
};
};
typedef InfoNode T;
template <class T>
struct TreeNode;
// Assumption: T is a type for which the operators "<"
// and "==" are defined - either an appropriate built-in type or
// a class that overloads these operators
enum OrderType { PRE_ORDER, IN_ORDER, POST_ORDER };
template <class T>
class Tree
{
private:
TreeNode<T> * root;
// The following queues are used for traversals
Queue<T> preQue;
Queue<T> inQue;
Queue<T> postQue;
public:
Tree(); // constructor
~Tree(); // destructor
Tree(const Tree<T> & oTree);
// copy constructor
void operator=(const Tree<T> & oTree);
// Overloads the assignment operator
void makeMT();
// Function: Initializes tree to the empty state
// Post: Tree is empty
bool isMT() const;
// Function: Determines whether the tree is empty
// Post: Function value = (tree is empty)
bool isFull() const;
// Function: Determines whether the tree is full
// Post: Function value = (tree is full)
int numberOfNodes() const;
// Function: Determines the number of elements in the tree
// Post: Function value = number of elements in the tree
void retrieveItem(T & item, bool & found);
// Function: Retrieves item whose key matches item's key (if present)
// Pre: Key of item has been initialized
// Post: If there is an item someItem whose key matches item's
// key, then found is true and item is a copy of someItem;
// otherwise found is false and item is unchanged
// The tree is unchanged
void insertItem(T item);
// Function: Adds item to the tree
// Pre: Tree is not full; item is not in the tree
// Post: item is in the tree
// Binary search property is maintained
void removeItem(T item);
// Function: Deletes the item whose key matches item's key
// Pre: Key of item has been initialized
// One and only one item in the tree has a key matching
// item's key
// Post: No element in tree has key matching item's key
void resetTree(OrderType order);
// Function: Initializes current position for an iteration
// through the tree in order specified
// Post: Current position is prior to root of the tree
void getNextItem (T & item, OrderType order, bool & fini);
// Function: Gets the next element in the tree in the order specified
// in order
// Pre: Current position is defined
// Item at current position is not last in the tree
// Post: Current position is one position beyond current position at
// entry to getNextItem()
// fini = (current position is last in tree)
// item is a copy of element at current position
void printTree(std::ofstream & outFile) const;
// Function: Prints the values in the tree in ascending key
// order on outFile
// Pre: outFile has been opened for writing
// Post: Values in the three have been printed in ascending key order
// outFile is still open
template <class T>
friend void buildExprTree(Tree<T> & expr);
template <class T>
friend double eval(Tree<T> & expr);
}; // end Tree
//#include "Tree.cpp"
// Implementation file for Binary Search Tree;
// recursive insertion and deletion functions
template <class T>
struct TreeNode
{
T info;
TreeNode * left;
TreeNode * right;
TreeNode() // default c-tor for TreeNode
{ }
};
template <class T>
int countNodes(Tree<T> * tree)
{ // Post: returns the number of nodes in the tree
if (tree == NULL)
return 0;
else
return countNodes(tree->left) + countNodes(tree->right) + 1;
}
template <class T>
int Tree<T>::numberOfNodes() const
{ // calls recursive function CountNodes to count nodes in the tree
return countNodes(root);
}
// Recursively searches tree for item
// Post: If there is an element someItem whose key matches item's, found
// is true and item is set to a copy of someItem; otherwise found
// is false and item is unchanged
template <class T>
void retrieve(TreeNode<T> * tree, T & item, bool & found)
{
if (tree == NULL)
found = false; // item is not found
else if ( item < tree->info ) // Search left subtree
retrieve(tree->left, item, found); // Search right subtree
else if ( item > tree->info )
retrieve(tree->right, item, found);
else {
item = tree->info; // item is found
found = true;
} // endif
}
template <class T>
void Tree<T>::retrieveItem(T& item, bool& found)
{ // calls recursive function Retrieve to search the tree for item
retrieve(root, item, found);
}
template <class T>
void insert(TreeNode<T> * & tree, T item) // inserts item into tree
{ // Post: item is in tree; search property is maintained
if ( tree == NULL ) { // insertion place found
tree = new TreeNode<T>;
tree->right = NULL;
tree->left = NULL;
tree->info = item;
}
else if ( item < tree->info )
insert(tree->left, item); // insert in left subtree
else
insert(tree->right, item); // nsert in right subtree
}
template <class T>
void Tree<T>::insertItem(T item)
{ // calls recursive function Insert to insert item into tree
insert(root, item);
}
template <class T>
// Deletes the node pointed to by tree
// Post: User's data in the node pointed to by tree is no longer in the tree.
// If tree is a leaf node or has only non-NULL child pointer the node
// pointed to by tree is deleted; otherwise, the user's data is replaced
// by its logical predecessor and the predecessor's node is deleted
void removeNode(TreeNode<T> * & tree)
{
T data;
TreeNode<T>* tempPtr;
tempPtr = tree;
if ( tree->left == NULL ) {
tree = tree->right;
delete tempPtr;
}
else if ( tree->right == NULL ) {
tree = tree->left;
delete tempPtr;
}
else {
getPredecessor(tree->left, data);
tree->info = data;
remove(tree->left, data); // Delete predecessor node
}
}
template <class T>
void remove(TreeNode<T>*& tree, T item)
{ // deletes item from tree - Post: item is not in tree
if (item < tree->info )
remove(tree->left, item); // Look in left subtree
else if ( item > tree->info )
remove(tree->right, item); // Look in right subtree
else
removeNode(tree); // Node found; call removeNode
}
template <class T>
void Tree<T>::removeItem(T item)
{ // calls recursive function remove() to delete item from tree
remove(root, item);
}
template<class T>
void getPredecessor(TreeNode<T> * tree, T & data)
{ // sets data to the info member of the right-most node in tree
while ( tree->right != NULL )
tree = tree->right;
data = tree->info;
}
template <class T>
void Tree<T>::printTree(std::ofstream & outFile) const
{ // calls recursive function print() to print items in the tree
print(root, outFile);
}
template<class T>
void print(TreeNode<T> * tree, std::ofstream & outFile)
{ // prints info member of items in tree in sorted order on outFile
if ( tree != NULL ) {
print(tree->left, outFile); // Print left subtree
outFile << tree->info;
print(tree->right, outFile); // Print right subtree
} // endif
}
template <class T>
Tree<T>::Tree()
{
root = NULL;
}
template<class T>
void destroy(TreeNode<T> * & tree)
{ // Post: tree is empty; nodes have been deallocated
if ( tree != NULL ) {
destroy(tree->left);
destroy(tree->right);
delete tree;
} // endif
}
template <class T>
Tree<T>::~Tree()
{ // calls recursive function destroy() to destroy the tree
destroy(root);
}
template <class T>
void copyTree(TreeNode<T> * & copy, TreeNode<T> * origTree )
{ // Post: copy is root of a tree that is a dup of tree pointed to by origTree
if ( origTree == NULL )
copy = NULL;
else {
copy = new TreeNode<T>;
copy->info = origTree->info;
copyTree(copy->left, origTree->left);
copyTree(copy->right, origTree->right);
} // endif
}
template <class T>
Tree<T>::Tree(const Tree<T> & origTree)
{ // calls recursive function copyTree() to copy origTree into root
copyTree(root, origTree.root);
}
template <class T>
void Tree<T>::operator=(const Tree<T> & origTree)
{ // calls recursive function CopyTree to copy origTree into root
if ( &origTree == this )
return; // Ignore assigning self to self
destroy(root); // Deallocate existing tree nodes
copyTree(root, origTree.root);
}
// function prototypes for auxiliary functions
template <class T>
void buildExprTree(Tree<T> & expr); // builds preorder binary expression tree
template <class T>
void preorder(TreeNode<T> *, Queue<T> &); // enqueues tree items in preorder
template <class T>
void inorder(TreeNode<T> *, Queue<T> &); // enqueues tree items in inorder
template <class T>
void postorder(TreeNode<T> *, Queue<T> &); // enqueues tree items in postorder
template <class T>
void Tree<T>::resetTree(OrderType order)
{ // calls function to create a queue of the tree elements in specified order
switch ( order ) {
case PRE_ORDER : preorder(root, preQue);
break;
case IN_ORDER : inorder(root, inQue);
break;
case POST_ORDER: postorder(root, postQue);
break;
} // endswitch
}
template <class T>
void preorder(TreeNode<T> * tree, Queue<T> & preQue)
{ // Post: preQue contains the tree items in preorder
if ( tree != NULL ) {
preQue.enqueue(tree->info);
preorder(tree->left, preQue);
preorder(tree->right, preQue);
} // endif
}
template <class T>
void inorder(TreeNode<T>* tree, Queue<T>& inQue)
{ // Post: inQue contains the tree items in inorder
if ( tree != NULL ) {
inorder(tree->left, inQue);
inQue.enqueue(tree->info);
inorder(tree->right, inQue);
} // endif
}
template <class T>
void postorder(TreeNode<T> * tree, Queue<T> & postQue)
{ // Post: postQue contains the tree items in postorder
if ( tree != NULL ) {
postorder(tree->left, postQue);
postorder(tree->right, postQue);
postQue.enqueue(tree->info);
} // endif
}
// Returns the next item in the desired order
// Post: For the desired order, item is the next item in the queue
// If item is the last one in the queue, fini is true; otherwise
// fini is false
template <class T>
void Tree<T>::getNextItem(T & item, OrderType order, bool & fini)
{
fini = false;
switch ( order ) {
case PRE_ORDER : preQue.dequeue(item);
if ( preQue.isMT() )
fini = true;
break;
case IN_ORDER : inQue.dequeue(item);
if ( inQue.isMT() )
fini = true;
break;
case POST_ORDER: postQue.dequeue(item);
if ( postQue.isMT() )
fini = true;
break;
} // endswitch
}
void parseStr(string s, char & sym, double & d); // Assign #19 - prototype
template <class T>
void buildExprTree(Tree<T> & expr)
{
buildTree(expr.root);
}
// buildTree.cpp
// buildTree() builds a binary expression tree
// Note: operands are NOT restricted to single digits
void buildTree(TreeNode<T> * & tree)
{
string inStr; // Assign #19
double opnd; // Assign #19
enum MoveType { RIGHT, LEFT };
MoveType nextMove = LEFT;
TreeNode<T> * nptr = new TreeNode<T>;
TreeNode<T> * last;
char symbol;
Stack <TreeNode<T> *> stack;
cin >> symbol;
cout << " operator: " << symbol << endl; // first symbol is operator
nptr->info.whichType = OPERATOR;
nptr->info.operation = symbol;
tree = nptr;
// instead of
// cin >> symbol; // this version uses single-digit operands – we have
cin >> inStr; // Assign #19 - uses type double operands
parseStr(inStr, symbol, opnd); // Assign #19
while ( symbol != LAST_SYMBOL ) {
last = nptr;
nptr = new TreeNode<T>;
if ( ispunct(symbol) ) {
cout << " operator: " << symbol << endl;
nptr->info.whichType = OPERATOR;
nptr->info.operation = symbol;
}
else {
//cout << " operand: " << symbol << endl;
cout << " operand: " << opnd << endl; // Assign #19
nptr->info.whichType = OPERAND;
//nptr->info.operand = int(symbol - '0');
nptr->info.operand = opnd; // Assign #19
nptr->right = NULL;
nptr->left = NULL;
} // endif
switch ( nextMove ) {
case LEFT : last->left = nptr;
stack.push(last);
break;
case RIGHT : stack.pop(last);
last->right = nptr;
break;
} // endswitch
if ( nptr->info.whichType == OPERATOR )
nextMove = LEFT;
else
nextMove = RIGHT;
// instead of cin >> symbol;
cin >> inStr; // Assign #19 - uses type double operands
parseStr(inStr, symbol, opnd); // Assign #19
} // endwhile
return;
} // end buildTree()
void parseStr(string s, char & sym, double & d) // Assign #19
{
const char * p = s.c_str(); // convert to C-style string
if ( p[0] == '+' || p[0] == '^' || p[0] == '/' || p[0] == '*' ||
p[0] == '-' || p[0] == LAST_SYMBOL ) { // symbol is an operator
sym = p[0];
d = 0.0;
} // endif-thenpart
else { // input is type double operand
d = atof(p); // convert input to type double operand
sym = '1'; // can make symbol any non-operator
} // endif-elsepart
} // end parseStr()
template <class T> //int eval(Tree<T> & expr)
double eval(Tree<T> & expr) // Assign #19
{
return eval(expr.root);
}
// Pre: ptr is a pointer to a binary expression tree
// Post: Function value = the value of the expression
// represented by the binary tree pointed to by ptr
//int eval(TreeNode<T> * ptr)
double eval(TreeNode<T> * ptr) // Assign #19
{ // function to evaluate a binary expression tree
switch ( ptr->info.whichType ) {
case OPERAND : return ptr->info.operand;
case OPERATOR :
switch ( ptr->info.operation ) {
case '+' : return ( eval(ptr->left) + eval(ptr->right) );
case '-' : return ( eval(ptr->left) - eval(ptr->right) );
case '*' : return ( eval(ptr->left) * eval(ptr->right) );
case '/' : return ( eval(ptr->left) / eval(ptr->right) );
case '^' : return ( pow(eval(ptr->left), eval(ptr->right)) );
} // endswitch
} // endswitch
return 0.0;
} // end eval()
//tstexpr.cpp
/* ------------------------------------------------------------------------------
* program to test binary tree expression evaluation
* CS 320 - Data Structures
*/
#include "btreeEx.h"
void main()
{
Tree<T> e;
cout << "\n Use a Binary Tree for Preorder Expression Evaluation\n";
cout << "\n Enter expression terminated by an equal sign, e.g.: - * 6.2 3.1 5.8 =\n";
buildExprTree(e);
cout << "\n The value of the expression is " << eval(e);
cout << "\n -- Done --\n";
return;
}You're right about the input. However, the input has to stay as ^ ^ 2 3 4. I need a special case maybe, to take care of the double ^?
>However, the input has to stay as ^ ^ 2 3 4.
That's stupid. You want to input a a prefix expression but evaluate it differently from the prefix notation rules. Would you be kind enough to explain why you need to do this?
Narue
Bad Cop
Administrator
15,460 posts since Sep 2004
Reputation Points: 6,464
Solved Threads: 1,401
That's stupid. You want to input a a prefix expression but evaluate it differently from the prefix notation rules. Would you be kind enough to explain why you need to do this?
hahah, no kidding.
This is, I guess, considered to be a programming challenge from my professor. The only thing I could think of would be to add a exception-handling block for when two ^ are found... but I have no clue if eventhat will work.
Honestly, I don't think anyone in the class has this figured out. I might turn in my assignment without this part included, hoping he'll mark it off. Quite silly, I agree.
>Honestly, I don't think anyone in the class has this figured out
I'm not surprised. Assuming you've given me the same requirements your teacher gave you, there's really no way you can solve the problem adequately. Since he changed the rules, you need to know the new rules before you can follow them.
You currently have one case:
^ ^ 2 3 4 = 2^81What about the case you've replaced?
^ 2 ^ 3 4 = ?What about the infinite recursion you should be able to handle correctly? What are the rules for three operators? Four? Fifty? What if they're not all adjacent? You lack sufficient information.
Narue
Bad Cop
Administrator
15,460 posts since Sep 2004
Reputation Points: 6,464
Solved Threads: 1,401
The whole point of prefix notation is to represent the formula in such a way as to eliminate the complications of precedence and association. To reinstate these complications is sidiotic.
I feel the most likely case here is that you are misunderstanding the assignment. It makes perfect sense to process exponentiation as right-associative; but it does not make sense to reinterpret prefix notation. So perhaps the input is supposed to be infix notation?
I know the problem sounds a little (understatement maybe) odd.
I understand what you're saying nucleon, and that would seem a lot more logical. However, I'm sure I haven't misunderstood the project. :)
>Narue
This is probably going to make you flip out. But in the case of input such as: 2 ^ 3 ^ 4, the left associativity should be used. In any case with subsequent ^, right associativity should be used (e.g., ^ ^ 2 3 4).
heheh, ^.^;
>But in the case of input such as: 2 ^ 3 ^ 4, the left associativity should be used
>used. In any case with subsequent ^, right associativity should be (e.g., ^ ^ 2 3 4).
Then I'd guess your teacher wants you to use prefix evaluation for the former and postfix evaluation for the latter. When you see adjacent operators, move them behind the correct number of operands:
* = Operand or operator not applicable
* ^ ^ 2 3 4 *
Find adjacent operators:
* ^ ^ 2 3 4 *
Count the operands that apply:
* ^ ^ 2 3 4 *
Move the operators to postfix position:
* 2 3 4 ^ ^ *
Evaluate:
Push 2
Push 3
Push 4
Found ^: Pop 4, 3, Evaluate
Push 81
Found ^, Pop 81, 2, Evaluate
Push 2^81 Narue
Bad Cop
Administrator
15,460 posts since Sep 2004
Reputation Points: 6,464
Solved Threads: 1,401
This article has been dead for over three months
You
© 2012 DaniWeb® LLC
