Need help with Java - Overclock.net

welfinator · 03-25-07

ok so my teacher gave us this project to program and i am lost:

our job is to: Implement an expression evaluator that uses a parser to build an expression tree. Then use postorder traversal to evaluate the expression, using a stack for the intermediate results.

this is my binary tree class:

Quote:

/**
* Write a description of class BinaryTree here.
*
* @author (your name)
* @version (a version number or a date)
*/
public abstract class BinaryTree
{
TreeNode root;

public BinaryTree()
{
root = null;
}

public TreeNode getRoot()
{
return root;
}

public void setRoot(TreeNode newNode)
{
root = newNode;
}

public boolean isEmpty()
{
return root == null;
}

public abstract void insert(Comparable item);
public abstract TreeNode find(Comparable key);
}

i have no idea how to do this program any help will be appreciated

*dangerousHobo* · 03-25-07

Well since your class BinaryTree is abstract your going to want to make a class that extends BinaryTree.

Could you give some more information on the project, as I'm a bit confused myself.

decompiled · 03-25-07

Do you understand what post order traversal is?

To do a postorder traversal of a binary tree

1. Traverse the left subtree; and then
2. traverse the right subtree; and then
3. visit the root.

So... you want to write code that goes as far left down the tree as possible then when it can't go to the root node then go right and try to go as far left as possible.

A great example is:

Code:

You would evaluate this as ( 9 - 3 ) + ( 4 * 2 ) or 6 + 8 = 14

Starting left we get 9. Then we go up to root which is -. Then we traverse right. Because there is no left child to the node with 3 we evaluate the expression as 9 - 3. Then we move to Root which is + and descend down the right side of the tree to 4 and work our way back up. Hope this helps =).

welfinator · 03-26-07

thanks guys for the help, i think i got it now my teacher kinda hbelped me lol

C-bro · 03-26-07

Are you allowed to use the Stack class that's built into Java?

If not, I have my own that I had to program for a project. I can pass it on if you'd like. I did it with generics, so it should work fine for your application.

		Overclock.net - Overclocking.net > Software, Programming and Coding > Coding and Programming
Need help with Java

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)