I copied the algorithm to do it with a stack from here: How to put postfix expressions in a binary tree?
The issue is that I end up with a node, but I need a binary tree.
String currentPartOfEquation;
Stack<Node<String>> inputProcessor = new Stack(postFixExpression.size()); //create a stack of the size of how many parts there are to the expression. technically, a length of a string.
Iterator<String> lookThroughInput = postFixExpression.iterator();
//iterate through the input!
BinaryTree<String> output = new BinaryTree<String>();
while(lookThroughInput.hasNext()) //Is there something left?
{
currentPartOfEquation = lookThroughInput.next(); //we read next input! We read one symbol of a postfix expression.
if(currentPartOfEquation.equals("*") ||
currentPartOfEquation.equals("/") || currentPartOfEquation.equals("-")
|| currentPartOfEquation.equals("+")) //Do we have a math operator as the symbol read in the expression?
{
//the first extracted off stack will end up being a right child for the current operator....
//we're popping based on an algorithm
//of making leaf nodes for #s following with
//giving 'em families with the operator input found here as a parent.
Node<String> right = inputProcessor.pop();
//operator's children!!!!
Node<String> left = inputProcessor.pop();
// operator node with its family relations. no parent yet, so null for that field
// we are creating a tree every time using the class definition.
Node<String> parent = createNode(currentPartOfEquation, temp, left, right);
temp = parent;
//for a parental connection for each next op to each previous op.
// push this family node into our stack using the class definition.
inputProcessor.push(parent);
}
else //we see a number in our input!!!
{
//no parents or children, just the NUMBER stored in a node!!!!!!! it's our LEAF NODE!!!!
Node<String> leaf = createNode(currentPartOfEquation, null, null, null);
// push this leaf node holding a # into our stack!!!!!
inputProcessor.push(leaf);
}
}
return inputProcessor.top();
// at the end there should be be one element in the stack holding the entire family in correct order!!!!! this tree should be created by the very end.
Some info about exactly how the Binary Tree works in relation to Nodes:
Node implements position and that's how they are connected. node is an inner class with parent, left, right (all nodes), and element (an object) as instance variables.
a constructor in the Node class assigns element, parent, left, right. the Binary Tree contains an instance variable Node called root which is the top element of the tree - the root - and createNode is it's function too.
createNode does return new node and assigns element, parent, left, right corresponding exactly to the constructor of Node.
by means of the Binary Tree's methods (which both returns Positions and takes Positions from the parameter, but work with nodes), the Binary Tree connects nodes (methods like add right, add left, etc.)
the validate method in the Binary Tree which gets used a lot takes a Position and returns it as a Node.
