Results 1 to 4 of 4
 05112011, 10:01 PM #1Member
 Join Date
 May 2011
 Posts
 8
 Rep Power
 0
Preorder Binary Expression Tree Help
Good afternoon,
I'm a Java newbie who is having a tough really time (approximately 1 week before giving in and asking for help) figuring out how to fill my binary expression tree with operators and operands. I need to recursively add thier values together with polynomials. I'm ok with creating the polynomials, but how can I build the tree and then add the value to the polynomials? I guess the toughest part for me so far is building the tree and determing how to call it from main so that it I can add the values to my polynomial, in the main...my code follows. Can someone please, please help or give me a clue as to what I'm missing? Thanks.
Java Code:class Tree { // Instance variables private Node root; private char[] treeString; private int stringIndex; // Constructor that builds a tree from a prefix string public Tree(String tree) throws SyntaxException { treeString = tree.toCharArray(); stringIndex = 0; try { // Initiate building the tree from all elements in the // character array treeString referenced in the makeNode function root = makeNode(); // Throw an SyntaxException if there are extra nodes // determined if all the elements in the char array does // not match the length of the tree...which should be equal // since the treeString char[] contains all nodes that are build // at once if (stringIndex != tree.length()) throw new SyntaxException("Extra Nodes"); } catch (ArrayIndexOutOfBoundsException exception) { throw new SyntaxException("Missing Nodes"); } } // Returns the root of the tree public Node getRoot() { return root; } // Creates either an interior or exterior node public Node makeNode() throws SyntaxException { Node node = null, left ,right; // The character represents an interior node. // (Operators = +, , *, /) // If the character is not a digit, it must be a operator if (!Character.isDigit(treeString[stringIndex])) { // Recursive call to return the node to the left and right left = makeNode(); right = makeNode(); // Create a new node containing the new operator node = new Interior( treeString[stringIndex], left, right); // Step to the next char value in the treeString char Array stringIndex++; } // The character represents an exterior node. // (Operands = integers 1, 2, 10, etc.) else { // Pass the operand (number value) to the Exterior node constructor node = new Exterior(treeString[stringIndex]); // Step to the next char value in the treeString char Array stringIndex++; } return node; } // Print all the items in the tree to which root points. // The item in the root is printed first, followed by the // items in the left subtree and then the items in the // right subtree. public void preorderPrint() { // Get the root node of the tree Interior root = (Interior) getRoot(); // If the root node's value is not empty if ( root != null ) { // root.evaluate() returns the double value of the current node System.out.print( root.evaluate() + " " ); // Print items in left subtree. preorderPrint( root.left ); // Print items in right subtree. preorderPrint( root.right ); } // (Otherwise, there's nothing to print.) } } // Class that represents a node that holds an operator. class Interior extends Node { // Instance variables private Node left, right; // The operator. char op; // Constructor public Interior(char op, Node left, Node right) { this.op = op; this.left = left; this.right = right; } double evaluate() { double leftVal = left.evaluate(); double rightVal = right.evaluate(); // To get the value, compute the value of the left and // right operands, and combine them with the operator. switch ( op ) { case '+': return leftVal + rightVal; case '': return leftVal  rightVal; case '*': return leftVal * rightVal; case '/': return leftVal / rightVal; // Bad operator. default: return Double.NaN; } } } //Represents a node that holds a number. class Exterior extends Node { // The number in the node. double number; Exterior( double val ) { // Constructor. Create a node to hold the number value. number = val; } double evaluate() { // The value is just the number that the node holds. return number; } } //In my main, I'm trying to get the tree to print it's values and get the simplified expression by calling the methods like so: Tree t = new Tree(prefixexpression); // Print the tree values to the console t.preorderPrint(); // Get the simplified prefix expression double val; Node n = null; val = n.evaluate();
Last edited by gixxer05; 05112011 at 10:03 PM.
 05112011, 10:02 PM #2Member
 Join Date
 May 2011
 Posts
 8
 Rep Power
 0
I need to do the following:
1. create a binary expression tree from command line input witch can be like the following: 1 3 * / 3 + 7,
2. all operators should be interior nodes and numbers exterior nodes
3. perform the mathmatical operations in preorder form
4. output the simplified value to: public static void main(final String[] args) throws IOException, SyntaxException {}
Specifically, I'm having trouble devising how to access the left and right root values. The root.left and root.right references are not working in the preorderPrint() function. How do I reference the two pointers, when they are in the Interior class, which extends the Node class? Is this even an appropriate way to access the nodes? Is my implementation correct? Thanks for your help.
 05122011, 06:17 PM #3Member
 Join Date
 May 2011
 Posts
 8
 Rep Power
 0
Please help
My project specification may give some clarification of what I'm attempting to acheive with my code:
A prefix expression consists of operators and operands. The operators can be any of the following +,  * or /. The operands can be either an unsigned (i.e. positive) constant or a call to a polynomial function. The user should be prompted first for the prefix expression.
The input might look as follows: + * 2.5 + P 7.4 6.3 8
The infix equivalent for the above user input is: ((2.5 * (P(7.4) + 6.3)) + 8)
After the prefix expression is input, one polynomial should be input that corresponds to the polynomial P in the expression. The format should be the same as Project 1. For example, 5 3 4 1 8 0 represents the polynomial 5x3 + 4x + 8.
After the expression and polynomial have been input, the expression should be evaluated and its value should be displayed.
Example 1
Please input prefix expression: + * 2.5 + P 7.4 6.3 8
Please input the polynomial: 5 2 2 0
The value of the expression is: 713.25
So I'm attempting read in the characters and build the binary tree.
Then I'm attempting to recursively print the binary tree values (both operators/Interior class nodes and operands/Exterior class nodes), for example:
Get the input from the user, from the commandline: + * 2 3 5 P
+
. .
. .
* P
. . .
. . .
2 3 5
Do a inorder traversal of the tree to produce a infix expression and
print it from preorderPrint: 2 * 3 + 5 P
Note: only operators can be parents, meaning they can have branches, or leafs, created by the Interior method because they are interior nodes. The operands, or numbers, will be on a branch and will not be a parent so they are exterior nodes created in the Exterior class.
I made the suggested name changes to variables in my cade. Thanks for the tips. I hope I'm being helpful.
 05122011, 06:33 PM #4
If you understand the logic of what your program is to do (at this point I don't), then perhaps you need to use some debugging techniques to see if your program is doing what you want it to do.
If you don't have an interactive debugger, then you can use print statements to show how the variable values change and how the program logic flows. Add LOTS of print statements to show variable names and their values as the program executes.
Similar Threads

binary tree
By ryamz in forum New To JavaReplies: 2Last Post: 08122010, 02:45 AM 
Data Structures(Binary Search Tree to AVL Tree)ASAP pls
By jfAdik in forum Forum LobbyReplies: 0Last Post: 04042010, 07:40 AM 
Help creating expression tree
By nellaf in forum New To JavaReplies: 8Last Post: 12042009, 04:17 AM 
Binary Tree
By MuslimCoder in forum New To JavaReplies: 8Last Post: 11192009, 05:57 PM
Bookmarks