Thread: Having trouble understanding what teacher said for build Tree.

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 int search(T data)
{
for (int x =0; x < Size(); x++)
{
if (get(x).equals(data))
return x;
 
}
return -1;
}
 
public DoublyLinkedList<T> getCopy()
{
DoublyLinkedList<T> copy = new DoublyLinkedList<T>();
 
for(int x =0; x < this.Size(); x++)
{
copy.add(x, this.get(x));
}
copy.head = this.head;
copy.tail = this.tail;
 
return copy;
 
 
}
 
public T[] toArray()
{
T[] array = new T[Size()];
 
for (int x =0; x < Size(); x++)
{
array[x] = get(x);
}
 
return array;
}
}

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
 
public boolean empty()
{
if (dLL.Size() ==0)
return true;
else return false;
}
 
public DoublyLinkedList<T> getDoublyLinkedList()
{
return dLL;
}
 
 
 
 
} // end of class

package ProjectOfDoom;
 
import java.util.ArrayList;
// can you use polymorphism on an interface?  
 
public interface Node
{
 
 
 
 
public  double evaluate();
 
 
 
 
}

package ProjectOfDoom;
 
public class OperandNode extends Node
{
private double data;
 
 
public OperandNode(double data)
{
data = this.data;
 
 
 
}
 
 
public double getData()
{
return this.data;
}
 
public double evaluate()
{
 
return  this.getData();
 
}
 
 
 
}

package ProjectOfDoom;
 
public class OperatorNode extends Node
{
 
private char data;
private Node  left, right;
 
public OperatorNode(char data, Node  left, Node right)
{
data = this.data;
left = this.left;
right = this.right;
}
 
public Node getRight()
{
return this.right;
}
 
public Node getLeft()
{
return this.left;
}
 
public char getData()
{
    return this.data;
}
 
public double evaluate()
{
 
 
if (this.getData() == '+')
 
return (getLeft().evaluate() +  getRight().evaluate());
 
else if (this.getData() == '-')
 
return(getLeft().evaluate()  - getRight().evaluate());
 
else if(this.getData() == '*')
return (getLeft().evaluate() * getRight().evaluate());
 
else if(this.getData() == '/')
return (getLeft().evaluate() / getRight().evaluate());
 
else if (this.getData() == '%')
return(getLeft().evaluate() % getRight().evaluate());
 
 
 
 
}
}

public class Tokenizer {
    public static String getNextToken(StringBuffer expr) //get the next token in string expr starting at index start
    {
        int i = 0;
        boolean found;
        String token="";
 
        char c = expr.charAt(i);
        if ((c=='+') || (c=='-') || (c=='*') || (c=='/') || (c=='%') || (c=='(') || (c==')'))
        {
            token = ""+c;
            expr = expr.delete(0,1);
            return token;
        }
 
        found = false;
 
        while ((i<expr.length()) && (!found))
        {
            c = expr.charAt(i);
            if ((c=='+') || (c=='-') || (c=='*') || (c=='/') || (c=='%') || (c=='(') || (c==')'))
            {
                found = true;
                token = expr.substring(0,i);
                expr = expr.delete(0,i);
            }
            else
                i++;
 
        }
        if (!found)
        {
            token = expr.substring(0,i);
            expr = expr.delete(0,i);  
        }
        return token;
    }
}

public class Expression_Tree
{
private Node root;
private MyStack<Node> stackOne;
private MyStack<Character> stackTwo;
private StringBuffer buffer;
private String expression2;
private StringBuffer buffer2;
public Expression_Tree()
{
stackOne = new MyStack<Node>();
stackTwo = new MyStack<Character>();
}
 
public Node getRoot()
{
return root;
}
 
public void setRoot(Node root2)
{
root = root2;
}
 
 
public String getExpression()
{
return expression2;
}
 
public void setExpression(String expression3)
{
expression2 = expression3;
}
 
public void setBuffer(String expression3)
{
buffer2 = new StringBuffer(expression3);
}
 
public StringBuffer getBuffer()
{
return buffer2;
}
public void buildTree(String expression)
{
 
setExpression(expression);
 
buffer = new StringBuffer(expression);
StringBuffer token= buffer;
 
String str = getNextToken(buffer);
 
 
// initialize both stacks to be empty
// perhaps I should call my setEmpty() method
 
// how will it know if token is operator or operand?
 
if (!stackOne.empty())
stackOne.setEmpty();
 
if (!stackTwo.empty())
stackTwo.setEmpty();
 
while (buffer.length !=0)
{
 
if (Tokenizer.getNextToken(buffer) instanceof Double)
{
OperandNode temp = new OperandNode((double) token);
stackOne.push(temp);
}
 
else if (Tokenizer.getNextToken(buffer) instanceof Character)
{
Character c = new Character((char) token);
if (stackTwo.empty())
{
stackTwo.push(temp2);
}
 
else
{
 
if ((char) token.equals(')'))
{
while (stackTwo.top() != '(')
{
OperatorNode n = stackTwo.top();
stackTwo.pop();
char c = n.getData();
Node n1 = stackOne.top();
stackOne.pop();
Node n2 = stackOne.top();
stackOne.pop();
OperatorNode on = new OperatorNode(c, n1, n2);
 
}
 
}
if (precedence((char) token, stackTwo.top()) ==1)
{
stackTwo.push((char) token);
 
}
 
else
{
while (!stackTwo.empty())
{
 
OperatorNode n = stackTwo.top();
stackTwo.pop();
char c = n.getData();
Node n1 = stackOne.top();
stackOne.pop();
Node n2 = stackOne.top();
stackOne.pop();
OperatorNode on = new OperatorNode(c, n1, n2);
}
 
stackTwo.push((char) token);
 
 setRoot( stackOne.top());
stackOne.pop();
 
 
}
 
 
}
}
 
else
System.out.println("Something isn't right.");
}
/*
The algorithm to build an expression tree given an expression uses two stacks, one that holds Node objects, and another that holds operators. The algorithm is as follows:
1. Initialize both stacks to be empty.
2. For every “token” from the expression (see below):
a. If token is operand, create OperandNode with it and push into operand stack.
b. If token is operator:
i. If operator stack is empty, push token to operator stack.
ii. If operator stack is not empty:
I. If token is ‘)’ do steps III(a-c) below until ‘(‘ is popped from operator stack.
II. If precedence of token is greater than top of operator stack, push token to operator stack.
III. If precedence of token is lesser than or equal to top of operator stack:
a. Pop one operator from operator stack.
b. Pop two Node objects from operand stack.
c. Create new Operator node, put popped operator in it and put the popped Node objects as its children.
d. Push token to operator stack.
3. If the operator stack is not empty, repeat steps III(a-c) below until the operator stack is empty. If the expression is valid, there will be exactly one node in the operand stack. Pop it, and this is the root of the expression tree.
You can either use your own Stack class from the previous assignment or use Java’s Stack class.
Obtaining tokens from a string:
Since the input expression does not have any spaces your program must break it into a sequence of operators and operands. These are referred to as “tokens”. For example the expression “(1.2+3.25)*2” is broken into the following tokens: “(“, “1.2”, “+”, “3.25”, “)”, “*”, “2”.
Please start the buildTree method by converting the expression from a String object to a StringBuffer object. This class works the same way as String, except it allows you to change a string. Use the provided method to get the next token sub-string. This method returns the next token and also removes it from the StringBuffer object passed as its parameter. If the resulting StringBuffer object has zero length, it means the expression is over.
*/
 
 
 
}
 
public double evaluate()
{
return getRoot().evaluate();
}
 
public String toString()
{
String str5 = getExpression();
StringBuffer buffer4 = newStringBuffer(str5);
 
 
 
String str6 = "(" + str5;
 
String aToken = getNextToken(buffer4);
 
 
 
while(buffer4.length !=0)
{
 
/*
if the expression is a, where a is just a double, I'm supposed to return at the end (a)
if the expression is a+b, where a and b, and from now on, all letters are doubles,
I'm supposed to determine that + is the root and that a and b are the left and right sides and get (a+b) returned at the end.
If I have the expression a+b*c
I'm supposed to determine that + is the root once more
and that * is the root of the right side and so get (a+(b*c))
If I have the expression a+b*c/d
I am supposed to get (a+(b*(c/d))) as final answer
*/
 
 
}
 
String bigBeefyString = str6 + ")";
 
return bigBeefyString;
}
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;
}
 
}
 
}

public class Test_Expression
{
 
static Scanner console = new Scanner(System.in);
 
public static void main(String[] args)
{
 
// I'd like to have a Node that keeps track of the root, but I can't instantiate a Node as it's abstract and has to be abstract.  
// Also, I think that I have too much in my Node class.  
 
Expression_Tree et = new Expression_Tree();
 
 
String expression = "";
System.out.println("Enter an expression.");
 
expression = console.nextLine();
 
et.buildTree(expression);
 
 
 
// System.out.println("(" + expression + ")");
 
System.out.println(et.toString());
 
System.out.println(et.evaluate());
 
 
 
/*
Main Method:
The main method of your program should ask the user for an expression from the keyboard. It should then print that expression with parentheses and also print the result of its evaluation.
*/
 
}
}

I don't know how to do the toString() or the build Tree. I've got an idea, but I can't understand the directions on buildTree for part I and part 3.

The toString() I'm not sure how to set up.



^