Binary Expression Tree

[Duki]

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;
 }

[Narue]

>For example, 2^3^4 should be evaluated as 2^(3^4).
>So I should get 2^81, instead of the usual 2^12.
Erm, it looks to me like the input is supposed to be prefix rather than infix. If you're getting 2^12 for your result, then I suspect you aren't entering the correct expression. You can test it for yourself:

^ ^ 2 3 4 = 2^12
^ 2 ^ 3 4 = 2^81

[Duki]

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 ^?

[Narue]

>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?

[Duki]

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 even that 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.

[Narue]

>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^81

What 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.

[nucleon]

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?

[Duki]

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, ^.^;

[Narue]

>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

[Duki]

Ah, nice. I'll give that a try. Thanks!