Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Page 1 of 2 12 LastLast
Results 1 to 25 of 29

Thread: Is this allowed?

  1. #1
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default 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());
     
    }
     
     
    }
    Attached Files Attached Files
    Last edited by javapenguin; November 7th, 2010 at 01:23 PM.


  2. #2
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,262
    Thanks
    176
    Thanked 820 Times in 763 Posts
    Blog Entries
    5

    Default Re: Is this allowed?

    Quote Originally Posted by javapenguin View Post
    Can I have a class, an abstract class moreover, that has two subclasses as objects?
    Why not? Did you try it? Did it work? Not sure why you want Node to be abstract...the only abstract function (evaluate) seems like a behavior that might make more sense being placed in another location as it seems quite dependent upon a single implementation

  3. The Following User Says Thank You to copeg For This Useful Post:

    javapenguin (November 7th, 2010)

  4. #3
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Is this allowed?

    I'm wondering if, based on the pdf assignment, I am doing this Node class right. I have a feeling I'm doing too much.

  5. #4
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Is this allowed?

     
    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?
    Last edited by javapenguin; November 7th, 2010 at 04:11 PM.

  6. #5
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Is this allowed?

    Ok, based on the pdf, am I doing this right?

    I have no idea what to do with tokens? Never handled them before.

  7. #6
    Member DavidFongs's Avatar
    Join Date
    Oct 2010
    Location
    Minneapolis, MN
    Posts
    107
    Thanks
    1
    Thanked 45 Times in 41 Posts

    Default Re: Is this allowed?

    Can you explain why you are using generics?

    It seems like you should have an abstract superclass Node, that has an abstract method, evaluate. Then you should have an OperatorNode that extends Node, that has a class member of type char, and two class members of type Node. Finally you should have an OperandNode class that extends Node, and has a class member of type float. Each subclass will obviously need to provide an implementation of evaluate

    You don't need the generic <T> in your code at all, if I am reading the pdf correctly..... and your superclass, Node, doesn't need a data member

  8. The Following User Says Thank You to DavidFongs For This Useful Post:

    javapenguin (November 8th, 2010)

  9. #7
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Question Re: Is this allowed?

    Quote Originally Posted by DavidFongs View Post
    Can you explain why you are using generics?

    It seems like you should have an abstract superclass Node, that has an abstract method, evaluate. Then you should have an OperatorNode that extends Node, that has a class member of type char, and two class members of type Node. Finally you should have an OperandNode class that extends Node, and has a class member of type float. Each subclass will obviously need to provide an implementation of evaluate

    You don't need the generic <T> in your code at all, if I am reading the pdf correctly..... and your superclass, Node, doesn't need a data member
    Ok, if I don't need the generic, why not?

    It's subclasses hold one particular type of data, but as that type is different, I cannot have a get Data method in my Node class. Are you suggesting I get rid of most of those methods?

  10. #8
    Member DavidFongs's Avatar
    Join Date
    Oct 2010
    Location
    Minneapolis, MN
    Posts
    107
    Thanks
    1
    Thanked 45 Times in 41 Posts

    Default Re: Is this allowed?

    I think its obvious why not. The subclasses take care of holding the data. The abstract super class doesn't hold the data. The type of data is dependent on the subclass. Each subclass has access to its "data" when it needs it (in the subclasses implementation of the evaluate() method).

    Based on your assignment, why do you need a get data method as part of the Node class? The rest of the methods can stay, you just need to remove the generic <T> part of them.

  11. The Following User Says Thank You to DavidFongs For This Useful Post:

    javapenguin (November 8th, 2010)

  12. #9
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Is this allowed?

    Ok, so what about my getData() method? Make it abstract too?

    It is currently returning a variable of type T.

  13. #10
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Is this allowed?

    On getData() could I make it abstract and change the return type to Object?

  14. #11
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Is this allowed?

     
    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;
    }
     
    }

  15. #12
    Member DavidFongs's Avatar
    Join Date
    Oct 2010
    Location
    Minneapolis, MN
    Posts
    107
    Thanks
    1
    Thanked 45 Times in 41 Posts

    Default Re: Is this allowed?

    You don't need a getData method in the Node class. Looking at the assignment, I don't see why it is necessary.

  16. The Following User Says Thank You to DavidFongs For This Useful Post:

    javapenguin (November 8th, 2010)

  17. #13
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Question Re: Is this allowed?

    So how do I keep track of the data at that Node?


  18. #14
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Is this allowed?

    Well, how do I do the evaulate method for OperatorNode? I don't know how to figure out the values in each subtree. It seems to involve recursion, but I can't figure it out at the moment.

  19. #15
    Member DavidFongs's Avatar
    Join Date
    Oct 2010
    Location
    Minneapolis, MN
    Posts
    107
    Thanks
    1
    Thanked 45 Times in 41 Posts

    Default Re: Is this allowed?

    The non leaf nodes evaluate will use recursion.

    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.
    It is very similar to a binary tree traversal, you can look up the recursive algorithm to do this.

  20. The Following User Says Thank You to DavidFongs For This Useful Post:

    javapenguin (November 9th, 2010)

  21. #16
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Is this allowed?

    Quote Originally Posted by DavidFongs View Post
    The non leaf nodes evaluate will use recursion.



    It is very similar to a binary tree traversal, you can look up the recursive algorithm to do this.
    This tree is a binary tree. That might be why.



    A non-leaf Node could have two non-leaf nodes, which then each have two non-leaf nodes, which then each have two non-leaf nodes and which each could then have two leaf nodes.

    I cannot think of any way to get it to get all of them.

  22. #17
    Member DavidFongs's Avatar
    Join Date
    Oct 2010
    Location
    Minneapolis, MN
    Posts
    107
    Thanks
    1
    Thanked 45 Times in 41 Posts

    Default Re: Is this allowed?

    Did you look up binary tree traversal on google? There are recursive, and non recursive, algorithms with pseudo code

  23. The Following User Says Thank You to DavidFongs For This Useful Post:

    javapenguin (November 9th, 2010)

  24. #18
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Is this allowed?

    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

    ( )

    *
    /
    %
    +
    -

    Last edited by javapenguin; November 9th, 2010 at 01:02 PM.

  25. #19
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Is this allowed?

    Anybody home?

  26. #20
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Is this allowed?

    Hey, is it legal to have switch structures within switch structures

    c =this.getData();
    switch(c)
    {

    case( ' ( ' )

    bla bla bla;

    wait, do I even want a switch structure? I'm thinking maybe not after all.

  27. #21
    Member DavidFongs's Avatar
    Join Date
    Oct 2010
    Location
    Minneapolis, MN
    Posts
    107
    Thanks
    1
    Thanked 45 Times in 41 Posts

    Default Re: Is this allowed?

    Are you ignoring the advice I'm giving you? Implement the evaluate method for each subclass. One of the evaluate methods simply returns its float value (the leaf). If its not a leaf, you recursively call evaluate again.

    Tree traversal: Tree traversal - Wikipedia, the free encyclopedia

    Look at the pseudo code, work from there.

  28. The Following User Says Thank You to DavidFongs For This Useful Post:

    javapenguin (November 9th, 2010)

  29. #22
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Is this allowed?

    I have this, but I don't know how to make the OperatorNode class evaluate the expressions.

    public class BST<T extends Comparable<T>> 
    {
    	private class Node<T>
    	{
    		private T data;
    		private Node<T> left,right;
     
    		public Node(T data,Node<T> left,Node<T> right)
    		{
    			this.data = data;
    			this.left = left;
    			this.right = right;
    		}
     
    		public void setLeft(Node<T> left)
    		{
    			this.left = left;
    		}
     
    		public void setRight(Node<T> right)
    		{
    			this.right = right;
    		}
     
    		public void setData(T data)
    		{
    			this.data = data;
    		}
     
    		public Node<T> getLeft()
    		{
    			return left;
    		}
     
    		public Node<T> getRight()
    		{
    			return right;
    		}
     
    		public T getData()
    		{
    			return data;
    		}
     
    		public void preOrder()
    		{
    			System.out.println(data);
    			if (left!=null)
    				left.preOrder();
    			if (right!=null)
    				right.preOrder();
    		}
     
    		public void inOrder()
    		{
    			if (left!=null)
    				left.inOrder();
    			System.out.println(data);			
    			if (right!=null)
    				right.inOrder();
    		}
     
    		public void postOrder()
    		{
     
    			if (left!=null)
    				left.postOrder();
    			if (right!=null)
    				right.postOrder();
    			System.out.println(data);
    		}
    	}
     
    	private Node<T> root;
     
    	public BST()
    	{
    		root = null;
    	}
     
    	public boolean search(T data)
    	{
    		Node<T> curr;
     
    		curr = root;
     
    		while ((curr!=null) && (data.compareTo(curr.getData())!=0))
    		{
    			if (data.compareTo(curr.getData())<0) //if data<curr.data
    			{
    				curr = curr.getLeft();
    			}
    			else
    			{
    				curr = curr.getRight();
    			}
    		}
    		if (curr!=null)
    			return true;
     
    		return false;		
    	}
     
    	public void add(T data)
    	{
    		Node<T> curr,prev;
     
    		if (search(data))
    			return;
     
    		Node<T> newnode = new Node<T>(data,null,null); //create new node
     
    		curr = root;
    		prev = null;
     
    		while (curr!=null)
    		{
    			prev = curr;
    			if (data.compareTo(curr.getData())<0) //if data<curr.data
    			{
    				curr = curr.getLeft();
    			}
    			else
    			{
    				curr = curr.getRight();
    			}
    		}
     
    		//the special case, root is null
    		if (root==null)
    		{
    			root = newnode;
    		}
    		else if (data.compareTo(prev.getData())<0)  //if data<curr.data
    		{
    			prev.setLeft(newnode);
    		}
    		else
    		{
    			prev.setRight(newnode);
    		}
    	}
     
    	public void printPreOrder()
    	{
    		if (root!=null)
    			root.preOrder();
    	}
     
    	public void printInOrder()
    	{
    		if (root!=null)
    			root.inOrder();
    	}
     
    	public void printPostOrder()
    	{
    		if (root!=null)
    			root.postOrder();
    	}
     
     
     
    }

  30. #23
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Is this allowed?

     
    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.
    Last edited by javapenguin; November 11th, 2010 at 06:11 PM.

  31. #24
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Is this allowed?


  32. #25
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Is this allowed?

    Ok, I'm thinking that perhaps for a + b * c

    I do something like this:

    OperandStack.push('+');
    OperandStack.push('*');

    OperatorStack.push(a);
    OperatorStack.push(b);
    OperatorStack.push(c);

    Pop b and c and * so that I get b * c.

    Then push result onto OperandStack.

    Then pop a and the result and pop + and add a to the result of b*c so that

    a new result is a + b*c.

    Push this result onto OperandStack and done.

    But I'm still a bit confused as to how to get it to do this.

    How will it know from reading it which ones to pop and push at the right times?

Page 1 of 2 12 LastLast