Thread: Is this allowed?

Can I have a class, an abstract class moreover, that has two subclasses as objects?

I think that this one may need recursion as well as Nodes.

I almost wish I could have Node itself keep track of right and left subtrees.

 
public abstract class Node <T>
{
 
protected Node<T> left, right, parent;
protected T data;
protected ArrayList<T> childrenHolder;
 
public Node(T data, Node<T> parent, Node<T> left, Node<T> right)
{
data = this.data;
left = this.left;
right = this.right;
parent = this.parent;
childrenHolder = new ArrayList<T>();
}
 
public T getData()
{
return data;
}
 
public Node<T> getParent()
{
return parent;
}
 
public Node<T> getLeft()
{
return left;
}
 
public Node<T> getRight()
{
return right;
}
 
public abstract double evaluate();
 
public boolean isLeaf()
{
if (this.left == null && this.right == null)
return true;
else return false;
 
}
 
public int getImmediateChildren(Node<T> aNode)
{
 
if (aNode.isLeaf())
return 0;
 
else if (((aNode.left == null && aNode.right != null) || (aNode.left != null && aNode.right == null)))
return 1;
 
else
return 2;
 
 
}
 
public void setParent(Node<T> aParent)
{
this.parent = aParent;
}
 
public void setLeft(Node<T> newLeft)
{
this.left = newLeft;
}
 
public void setRight(Node<T> newRight)
{
this.right = newRight;
}
public boolean isRoot()
{
if (this.parent == null)
return true;
else
return false;
}
 
public T getRoot(Node<T> aNode)
{
 
while (aNode.isRoot() == false)
{
aNode = aNode.getParent();
}
 
return (aNode.getData());
 
}
 
 
}

 
public abstract class Node <T>
{
 
protected Node<T> left, right, parent;
protected T data;
protected ArrayList<T> childrenHolder;
 
public Node(T data, Node<T> parent, Node<T> left, Node<T> right)
{
data = this.data;
left = this.left;
right = this.right;
parent = this.parent;
childrenHolder = new ArrayList<T>();
}
 
public T getData()
{
return data;
}
 
 
public Node<T> getParent()
{
return parent;
}
 
public Node<T> getLeft()
{
return left;
}
 
public Node<T> getRight()
{
return right;
}
 
public abstract float evaluate();
 
public boolean isLeaf()
{
if (this.left == null && this.right == null)
return true;
else return false;
 
}
 
public int getImmediateChildren(Node<T> aNode)
{
 
if (aNode.isLeaf())
return 0;
 
else if (((aNode.left == null && aNode.right != null) || (aNode.left != null && aNode.right == null)))
return 1;
 
else
return 2;
 
 
}
 
public void setParent(Node<T> aParent)
{
this.parent = aParent;
}
 
public void setLeft(Node<T> newLeft)
{
this.left = newLeft;
}
 
public void setRight(Node<T> newRight)
{
this.right = newRight;
}
public boolean isRoot()
{
if (this.parent == null)
return true;
else
return false;
}
 
public T getRoot(Node<T> aNode)
{
 
while (aNode.isRoot() == false)
{
aNode = aNode.getParent();
}
 
return (aNode.getData());
 
}
 
 
}

 
public class OperandNode<Float> extends Node
{
private Float data;
 
 
public OperandNode(Float data
{
data = this.data;
 
 
 
}
 
 
public Float getData()
{
return this.data;
}
 
public float evaluate()
{
 
return this.getData();
 
}
 
 
 
}

 
public class OpearatorNode<Character> extends Node
{
 
private Character data;
private Node<T> left, right;
 
public OpeatorNode(Character data, Node<T> left, Node<T> right)
{
data = this.data;
left = this.left;
right = this.right;
}
 
}

Ok, the nodes on its left and/or right could either be leaf Nodes (OperandNode) or non-leaf nodes themselves(OperatorNode).

However, Node has a data type of T, but OperatorNode has a data type of Character. This will doubtless cause an error. How do I overcome this?

I see a class for a binary tree, but no way to evaluate its subtrees. Even if there are, I cannot understand how to do it.

should I create the expression tree class first before:

1. Create a class Node to represent the nodes of the expression tree. It should contain an abstract method called “evaluate” that evaluates the expression rooted at this node.
2. Create two sub-classes OperatorNode and OperandNode, the former for the non-leaf nodes and the latter to represent leaves. Non-leaf nodes contain a single character storing the operator and two references, left and right. Leaf nodes contain a single floating-point number. The evaluate method of leaf nodes simply returns this value, while that of the non-leaf nodes evaluates its two sub-trees and combines their result using its operator.
3. Create a class that represents an expression tree. This tree keeps track of the root of the expression tree. This class should have the following methods:
a. void buildTree(String expr): This method takes as a parameter an expression, and creates an expression tree.
b. double evaluate(): This method returns the value of the expression tree. (Hint: Think about how evaluation and post-fix notation are related).
c. String toString(): This method prints the expression using parentheses correctly. For example, the four trees above should print “(a+b)”, “((a*b)+c)”, “(a*(b+c))” and “((a+b)-c)” respectively.

It seems to say to first, but how can I?

I don't know how to let it know which operator there is:

Well I think I do:

if (this.getData() == '+')

{

float sum = this.left + this.right;

// but what if either the left or the right is null?

}

else if (this.getData() == '-')

{

float result = this.(left or right) - this.(right or left);
// how would it know which one to subtract from which and what would I do if it's null?
}


else if (this.getData() == '*')
{
float result = this.left * this.right;

// again, what if null?

}

else if (this.getData() == '/')
{

float result = this.(left or right) / this.(right or left);

// what if null and how will it know which one goes where

}

else if (this.getData() == '( ' )
{
evaluate it in parenthis
}

else if (this.getData() == ' ) ')
{

end paraenthesis

}

Also, the order of precedence is

( )

*
/
%
+
-

 
public abstract class Node 
{
 
protected Node  left, right, parent;
protected Object data;
protected ArrayList<Object> childrenHolder;
 
public Node(Object data, Node  parent, Node  left, Node  right)
{
data = this.data;
left = this.left;
right = this.right;
parent = this.parent;
childrenHolder = new ArrayList<Object>();
}
 
public Object getData()
{
return data;
}
 
 
public Node  getParent()
{
return parent;
}
 
public Node getLeft()
{
return left;
}
 
public Node  getRight()
{
return right;
}
 
public abstract float evaluate();
 
public boolean isLeaf()
{
if (this.left == null && this.right == null)
return true;
else return false;
 
}
 
public int getImmediateChildren(Node aNode)
{
 
if (aNode.isLeaf())
return 0;
 
else if (((aNode.left == null && aNode.right != null) || (aNode.left != null && aNode.right == null)))
return 1;
 
else
return 2;
 
 
}
 
public void setParent(Node aParent)
{
this.parent = aParent;
}
 
public void setLeft(Node newLeft)
{
this.left = newLeft;
}
 
public void setRight(Node  newRight)
{
this.right = newRight;
}
public boolean isRoot()
{
if (this.parent == null)
return true;
else
return false;
}
 
public Object getRoot(Node  aNode)
{
 
while (aNode.isRoot() == false)
{
aNode = aNode.getParent();
}
 
return (aNode.getData());
 
}
 
 
}

 
public class OperandNode<Float> extends Node
{
private Float data;
 
 
public OperandNode(Float data)
{
data = this.data;
 
 
 
}
 
 
public Float getData()
{
return this.data;
}
 
public float evaluate()
{
 
return this.getData();
 
}
 
 
 
}

 
public class OpearatorNode<Character> extends Node
{
 
private Character data;
private Node  left, right;
 
public OpeatorNode(Character data, Node  left, Node right)
{
data = this.data;
left = this.left;
right = this.right;
}
 
public OperatorNode getRight();
{
return this.right;
}
 
public OperatorNode getLeft()
{
return this.left;
}
 
 
}

 
public class Expression_Tree 
{
private Node root;
private MyStack<Node> stackOne;
private MyStack<OperatorNode> stackTwo;
private StringBuffer buffer;
public Expression_Tree(Node root)
{
root = this.root;
stackOne = new MyStack<Node>();
stackTwo = new MyStack<OperatorNode>();
}
 
public Node getRoot()
{
return this.root;
}
 
 
 
public void buildTree(String expression)
{
buffer = new StringBuffer(expression);
 
}
 
}

import java.util.*;
import java.io.*;
 
public class MyStack <T>
{ // beginning of class
 
private DoublyLinkedList<T> dLL;
 
public MyStack()
{ // beginning of constructor
dLL = new DoublyLinkedList<T>();
} // end of constructor
 
public void pop
{ // beginning of method
dLL.remove(0);
 
} // end of method
 
public void push(T data)
{ // beginning of method
 
dLL.addFirst(data);
} // end of method
 
public void setEmpty()
{
dLL.removeAll();
 
}
 
 
public T top()
{ // beginning of method
return dLL.get(0);
} // end of method
 
public int Size()
{ // beginning of method
return dLL.Size();
} // end of method
 
} // end of class

import javax.swing.Icon;
import javax.swing.ImageIcon;
import javax.swing.JOptionPane;
import java.util.*;
import java.io.*;
//Paul Adcock
// Assignment 4
// Lasted Worked On: 10/12/2010
 
// this class is the Doubly Linked list class.  It has a Node that holds a reference to some date of type T and has a reference
// to the next Node and to the previous Node.  
 
 
public class DoublyLinkedList<T>
{
    private class Node<T>
    {
        private T data;
        private Node<T> next;
               private Node<T> previous;
 
        public Node(T data,Node<T> next, Node<T> previous)
        {
            this.data = data;
            this.next = next;
                       this.previous=previous;
        }
 
        public T getData()
        {
            return data;
        }
 
        public Node<T> getNext()
        {
            return next;
        }
 
public Node<T> getPrevious()
{
return previous;
}
 
        public void setNext(Node<T> next)
        {
            this.next = next;
        }      
 
public void setPrevious(Node<T> previous)
{
this.previous = previous;
}
    }
 
    private Node<T> head;//head of the linked list
       private Node<T> tail; // tail of linked list
    private int size;
   private ImageIcon icon;
   private Icon icon2;
    public DoublyLinkedList()
    {
        head = null;
                tail = null;
        size = 0;
        icon = new ImageIcon("doh3.jpg");
    }
 
 
 
    // returns a String of all the items in the linked list.  
    public String toString()
    {
        String str = "[";
 
        Node<T> curr;
 
        for (curr=head;curr!=null;curr = curr.getNext())
        {
            str = str + curr.getData();
            if (curr.getNext()!=null)
                str = str + " ";
        }
        str = str + "]";
        return str;
 
 
    }
 
public void removeRange(int from, int to)
{
if (from < 0 || from > = Size() || to < 0 || to >=Size())
{
return;
}
 
for (int i = from; i <=to; i++)
{
remove(i);
}
}
 
    // adds the data as the first element.  If the list size is 0, makes first element tail.  If head is not null, it puts the old
    // tail as the second element and the new element as the new head.  
    public void addFirst(T data)
{  
    /*  Since this is the first Object,  previous should be null
     */
    Node<T> newNode = new Node<T>(data,head,null);
    //We know that if head is null, the list is empty
    if (head==null)
        {
        //If the list is empty,  tail will be newNode
        tail = newNode;
    }
 
    if(head!=null)
        head.setPrevious(newNode);
 
    //We want to set head to be newNode
// if the list was empty before, both head and tail will be set to newNode;
    head = newNode;
    //Increment Size
    size++;
}
 
    public void removeFirst()
    {
           if (size == 0)
{
               JOptionPane pane = new JOptionPane();
               pane.setIcon(icon);
pane.showMessageDialog(null, "Cannot remove from an empty list!", "Invalid removal", JOptionPane.ERROR_MESSAGE);
pane.setMessageType(JOptionPane.ERROR_MESSAGE);
 
return;
}
        Node<T> current = head; // creates a Node called current and sets it to head.
 
        head = head.getNext(); //move head to the next element
 
        current.setNext(null);
size--;
    }
 
    public void addLast(T data)
    {
        //If there are no elements, use the addFirst method
        if (tail == null)
        {
            addFirst(data);
            return;
        }
        /* Create the new Node from the data. Set next to null
         * because this will be the last element and will not
         * have a next. Set previous to tail because tail has
         * not been changed yet and is currently referencing
         * that element that will be directly before this element
         */
        Node<T> newNode = new Node(data,null,tail);
        /* Since the tail variable still references the element
         * directly before the new element, we can set that node's
         * next to our new element.
         */
        tail.setNext(newNode);
        //Set tail to our new Node
        tail = newNode;
        //Increment size
        size++;
    }
 
    public int Size()
    {
        return(size);
    }
 
    public void add(int index,T data)
    {
        int i;
       if (index == 0)
       {
           addFirst(data);
           return;
 
       }
        if (index>size)
        {
            JOptionPane.showMessageDialog(null, "Cannot add out of bounds!", "Invalid command", JOptionPane.ERROR_MESSAGE);
            return;
        }
 
 
        if (index < 0)
        {
            JOptionPane.showMessageDialog(null, "Cannot add out of bounds!", "Invalid command", JOptionPane.ERROR_MESSAGE);
            return;
        }
 
        if (head==null)
        {
            addFirst(data);
            return;
        }
 
        if (index == size)
        {
            addLast(data);
            return;
        }
 
        //step 1
        Node<T> current;
 
        current = head;
 
        for (i=0;i<index-1;i++)
        {
            current = current.getNext();
        }
 
        //current now refers to object immediately before new node
 
        //step 2
        Node<T> newnode = new Node<T>(data,current.getNext(), current.getPrevious());
 
        //step 3
 
        current.setNext(newnode);
 
 
        size++;
    }  
 
    public void remove(int index)
    {
        if ((index<0) || (index>=size))
{
JOptionPane.showMessageDialog(null, "You cannot remove an out-of-bounds value!", "Invalid removal", JOptionPane.ERROR_MESSAGE);
            return;
        }
 
 
 
Node <T> next2, previous3;
       Node<T> NodeToRemove = head; // sets Node to remove originally to head
 
 
for (int v = 0; v < index; v++)
{
NodeToRemove = NodeToRemove.getNext(); // traverse to Node we want to remove
}
 
previous3 = NodeToRemove.getPrevious(); // sets previous3 to value before Node to remove
next2 = NodeToRemove.getNext(); // sets next2 to value after Node to remove
 
if (previous3 == null)
{
if (next2 == null)
{
head = null;
tail = null;
}
 
else
{
head = next2;
}
}
 
else
{
previous3.setNext(next2);
}
 
if (next2 == null)
{
if (previous3 == null)
{
head = null;
tail = null;
}
 
else
{
tail = previous3;
}
}
else
{
next2.setPrevious(previous3);
}
 
 
        size--;
    }
 
    public T get(int i)
    {
        if (i < 0 || i >= size)
            return null;
 
        if (i ==0)
        {
                Node<T> thisNode = head;
                return(head.getData());
        }
 
        if (i == size - 1)
        {
            Node<T> thisNode = tail;
            return(tail.getData());
        }
        Node<T> specialNode = head;
        for (int x = 1; x < i + 1; x++)
        {
            specialNode = specialNode.getNext();
        }
        return(specialNode.getData());
 
        // How do I get it to return the data at i?
 
 
    }
 
    // calls get method of first index
    public T front()
    {
        if (head == null)
            return null;
 
        return(get(0));
    }
 
    // calls get Method of last index
    public T back()
    {
        if (tail == null)
            return null;
 
        return(get(size - 1));
    }
 
    public void removeLast()
    {
 
        if (head == null)
        {
            JOptionPane.showMessageDialog(null, "Cannot remove from an empty list!", "Invalid removal", JOptionPane.ERROR_MESSAGE);
            return;
        }
        remove(Size() -1 );
    }
 
    // gets a String for the first bracket.  Then stores each set of first and last, 2nd and 2nd to last, etc, in a String array;
    // it then sets the third string to the concatination of all of the Strings in the array.  It thens puts these together and adds
    // the last set of brackets and returns the final string.  
public String printAlternate()
{
/*
This method returns a string that has
the data in the following fashion (assume for this example that the list stores String objects)
If the list is currently [amit is now here], it will return a string �[amit here is now]�
If the list is currently [amit is now currently here], it will return a string �[amit here is currently now]�
*/
    String str = "[";
    String [] str2 = new String[size];
for (int v = 0; v < size; v++)
{
    str2[v] = this.get(v) + " " + this.get(size - (v+1) );
}
String str3 = "";
for (int x = 0; x < size - 2; x++)
{
    str3 = str2[x].concat(str2[x+1]);
}
String str4 = str + " " + str3 + " " + "]";
return(str4);
}
 
// removes all data 
public void removeAll()
{
int x = 0;
int y = this.Size() - 1;
 
removeRange(x,y); 
}
 
public DoublyLinkedList<T> getCopy()
{
DoublyLinkedList<T> dLL = new DoublyLinkedList<T>();
T[] array = new T[this.Size()];
 
for (int x =0; x < this.Size; x++)
{
array[x] = this.get(x);
dLL.add(array[x], x);
 
}
 
return dLL;
}
}

public int precedence(char op1, char op2)
{
if (op1 == '(' || op1 == ' ) ')
{
 
return 1;
}
 
else if (op1 == '*')
{
if (op2 == '(' || op2 == ')')
return -1;
else
return 1;
 
}
 
else if (op1 == '/')
{
if (op2 == '(' || op2 == ')')
return -1;
else if (op2 == '*')
return -1;
else
return 1;
}
 
else if (op1 == '%')
{
if (op2 == '(' || op2 == ')')
return -1;
else if (op2 == '*')
return -1;
else if (op2 == '/')
return -1;
else
return 1;
}
 
else if (op1 == '+')
{
if (op2 == '(' || op2 == ')')
return -1;
else if (op2 == '*')
return -1;
else if (op2 == '/')
return -1;
else if (op2 == '%')
return -1;
else 
return 1;
}
 
else
{
if (op2 == '-')
return 1;
else
return -1; 
}
 
}

I still don't understand how it would evaluate them.

How the OperatorNode class would handle that.