binary tree implementation

You are to design and implement, in C++, a parser for postfix expressions. Your parser should accept a legal postfix expression and output the equivalent infix expression.
Your implementation must use a stack of general binary trees to perform the parsing and conversion of the input. Your parser should read an expression from the standard input file one character at a time. You may assume that the expression is a syntactically valid postfix expression comprised of single digit numbers, single letter variables, and the binary operators +, -, *, and /. The symbols in the postfix expression are processed from left to right as follows:

1. If the next symbol in the expression is an operand, a tree comprised of a
single node labeled with that operand is pushed onto the stack.

2. If the next symbol in the expression is an operator, then the top two
trees on the stack correspond to its operands. The two top trees are
popped from the stack and a new tree is created which has the operator
as its root and the two trees corresponding to its operands as its
subtrees. This new tree is then pushed on the stack.

After all symbols of the expression have been processed in this fashion, the stack will contain a single tree that is the desired expression tree. This tree can then be traversed and the nodes written to the standard output to yield the equivalent infix expression.

For instance, given the input ab/cd–e*+ your parser should output a/b+c-d*e.
Since you will only be parsing binary operators the expression tree in your implementation
should be an instantiation of a templated BinaryTree class. Likewise, your stack of trees should be an instantiation of a templated Stack class.

For this assignment you are to design and implement, in C++, a complete implementation of a generic, templated, Binary Tree class. Your implementation must include three constructor methods, a destructor method, and methods for isEmpty, Info, inOrder, preOrder, and postOrder. Your constructor methods will provide a means of creating an empty Binary Tree, a Binary Tree with only one node and two empty subtrees, and a Binary Tree with a root node and two non-empty subtrees. isEmpty should return true if there are no values stored in the binary tree, Info returns the value stored in the root of the tree, and the three traversals should simply visit each node in the tree in the order
indicated. The visit function for the traversals should simply output the value stored at the current node.

Your class must use the following structure definition for the binary tree data:
struct Tree_Node
Node_Type Node_Info;
BinaryTree<Node_Type> *left;
BinaryTree<Node_Type> *right;

Tree_Node *root;

where BinaryTree is the name of the class and Node_Type is the class template parameter.
Alright, I understand all the concepts up to this point, i just.... have no idea where to begin to implement it all as a whole..

i know that i should create a stack class but it almost makes no sense when i think about it. Should i still create a struct node{}; for the stack class as well as the binary class or should the struct in the directions be defined independently and its pointers used for both the stack and the binary tree? I just cant wrap my head around the project as a whole, if someone could explain the directions more simply to me or something? thanks
Topic archived. No new replies allowed.