QUOTE(pbl @ 24 Jun, 2008 - 09:03 PM)
Don't want to be rude but this topic has been covered/explained in many topics in this forum
Did you searched it for "tree" ? You'll have plenty of examples
I found plenty of examples of BSTs, AVLs, etc but no expression trees. Regardless, I think I have a solution:
Operator NodeCODE
public abstract class OperatorNode implements Expression {
protected Expression left;
protected Expression right;
// the "protected" keyword means only this class and
// its subclasses can access these variables
String operatorString;
private static int size = 0;
Expression getLeft() { return left; }
Expression getRight() { return right; }
public OperatorNode(Expression l, Expression r, String s) {
left = l;
right = r;
operatorString = s;
size++;
}
/**
* Returns the total number of OperatorNodes created
* since the program began.
* You will need to add an instance variable and modify the
* OperatorNode constructor to get this to work.
*/
public static int getNumCreated() {
return size;
}
/**
* @ returns the height of the tree where this operator node is the root
*/
public int height() {
if (left == null && right == null) { // Node is a leaf node
return 0;
}
else { // Find the max height in either the left or right subtree
int max = left.height();
if (max < right.height()) {
max = right.height();
}
return max + 1;
}
}
/**
* implemented by other classes
*/
public abstract float compute();
/**
* Returns a fully parenthesized inorder String representation of
* this expression.
* Example: ((1+2)*(3-(4/5)))
* Example: 142
*/
public String toString() {
String S = new String();
if (left != null && right != null) {
S += "(" + left.toString() + " ";
S += operatorString + " ";
S += right.toString() + ")";
return S;
}
else {
String error = new String();
error = "There is no operation to print";
return error;
}
}
/**
* Creates a new OperatorNode of the same type as this one.
* We don't know the exact type of this OperatorNode yet,
* so this method is marked abstract.
* Subclasses of OperatorNode will have methods to create copies
* of themselves.
* @param left The left child of the newly created instance
* @param right The right child of the newly created instance
*/
public abstract OperatorNode createNew(Expression left, Expression right);
/**
* Commutes this expression over the operator.
* Expect an expression (a op b) , and produce (b op a) .
* If the operator does not commute, results of calculating the
* resulting expression may not be equivalent to those of the
* initial expression.
*
* Do not modify any nodes; instead, create a new one to return.
*/
public Expression commute() {
OperatorNode replacement = this.createNew(right, left);
return replacement;
}
/**
* As commute(), but modify the node rather than creating a new one.
*/
public Expression commuteMutating() {
Expression ptr = right;
right = left;
left = ptr;
return this;
}
}
AddNodeCODE
public class AddNode extends OperatorNode {
/**
* Constructs a new expression that will add the two parameters
* @param l The left child of this expression
* @param r The right child of this expression
*/
public AddNode(Expression l, Expression r) {
super(l, r, "+");
}
/**
* Computes the value of this AddNode
*
* @see Expression#compute()
*/
public float compute() {
float l = left.compute();
float r = right.compute();
return l + r;
}
/**
* Creates a new AddNode with the specified children
*
* @param l The left child of the returned expression
* @param r The right child of the returned expression
*/
public OperatorNode createNew(Expression l, Expression r) {
return new AddNode(l, r);
}
}
MultNodeCODE
public class MultNode extends OperatorNode {
public MultNode(Expression l, Expression r) {
super(l, r, "*");
}
/**
* @see OperatorNode#createNew(Expression, Expression)
*/
public OperatorNode createNew(Expression left, Expression right) {
return new MultNode(left, right);
}
/**
* @see Expression#compute()
*/
public float compute() {
float l = left.compute();
float r = right.compute();
return l*r;
}
}
SubNodeCODE
public class SubNode extends OperatorNode {
public SubNode(Expression l, Expression r) {
super(l, r, "-");
}
public OperatorNode createNew(Expression left, Expression right) {
return new SubNode(left, right);
}
public float compute() {
float l = left.compute();
float r = right.compute();
return l-r;
}
}
DivNodeCODE
public class DivNode extends OperatorNode {
public DivNode(Expression l, Expression r) {
super(l, r, "/");
}
/**
* @see OperatorNode#createNew(Expression, Expression)
*/
public OperatorNode createNew(Expression left, Expression right) {
return new DivNode(left, right);
}
/**
* @see Expression#compute()
*/
public float compute() {
float l = left.compute();
float r = right.compute();
return l/r;
}
}
Turned out to be a bit easier than I realized...however even after writing a Driver method (with a main) eclipse is acting funny and was not letting me run it yesterday. It passed my test program in terminal, but does anyone know why Eclipse was not working with this
Driver? It magically worked this morning with no changes...:
CODE
/**
* @ driver program for hw5
*
*/
public class Driver {
public static void main(String[] args)
{
/* TODO Fill in your own test code here */
// None of this will be graded, but your tests may help you
// improve the parts of your code that are graded.
// Don't rely on our test code to make sure your code is perfect!
// We may run more extensive tests after everything is turned in.
// Here are a few tests to get you started:
Expression a1 = new FloatNode(3);
Expression a2 = new FloatNode(1);
Expression a3 = new FloatNode(4);
Expression a4 = new FloatNode(1);
Expression a5 = new FloatNode(5);
Expression a6 = new FloatNode(9);
System.out.println("Space usage: "+OperatorNode.getNumCreated()+" nodes created (should be 0)");
// Here is an example.
//Expression example = new AddNode(new AddNode(new AddNode(a1,a2), new AddNode(a3,a4)),
// new AddNode(a5,a6));
Expression example = new MultNode(new AddNode(new SubNode(a1,a2),
new DivNode(a3,a4)),new AddNode(a5,a6));
System.out.println("Here's a tree to get you started:");
System.out.println("Your soln:\""+example+"\"");
System.out.println("Expected: \"(((3.0-1.0)+(4.0/1.0))*(5.0+9.0))\"");
System.out.println("The tree evaluates to:");
System.out.println("Your soln:"+example.compute());
System.out.println("Expected: 84.0");
System.out.println("The tree has height:");
System.out.println("Your soln:"+example.height());
System.out.println("Expected: "+3);
System.out.println("Space usage: "+OperatorNode.getNumCreated()+" nodes created (should be 5)");
// TODO: add your own tests!
//Expression example = new MultNode(new AddNode(a5,a6), new AddNode(a3,a4));
}
}
I was getting a classDefnotFound: Driver error. Additionally, Eclipse has stopped checking for errors in my code and always compiles; what is going on?
This post has been edited by strakerc: 25 Jun, 2008 - 03:33 AM
| 