# Thread: Preorder Binary Expression Tree Help

1. Member 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;

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; 05-11-2011 at 10:03 PM.  Reply With Quote

2. Member 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.  Reply With Quote

3. Member 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.  Reply With Quote

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.  Reply With Quote

binary, expression, preorder, tree 