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.

View Poll Results: How long does it take for you to get a response?

Voters
3. You may not vote on this poll
  • A day or two.

    2 66.67%
  • About 4 days to a week.

    1 33.33%
  • 2-3 weeks

    0 0%
  • A Month or longer

    0 0%
Results 1 to 20 of 20

Thread: Evaluating Expressions

  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

    Unhappy Evaluating Expressions

    copeg has insisted that I shouldn't keep flipping from topic to topic, so I'm going to make many posts in the hope that people will be able to respond faster, as he suggested they might.


  2. #2
    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: Evaluating Expressions

     
    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 double 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 double data;
     
     
    public OperandNode(double data)
    {
    data = this.data;
     
     
     
    }
     
     
    public doublet getData()
    {
    return this.data;
    }
     
    public double 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 Node getRight();
    {
    return this.right;
    }
     
    public Node getLeft()
    {
    return this.left;
    }
     
    public double evaluate()
    {
     
    if (getLeft() instanceof OperandNode && getRight() instanceof OperandNode)
    { // beginning of if
    if (this.getData() == '+')
     
    return (getLeft().getData() + getRight().getData());
     
    else if (this.getData() == '-')
     
    return(getLeft().getData()  - getRight().getData());
     
    else if(this.getData() == '*')
    return (getLeft().getData() * getRight().getData());
     
    else if(this.getData() == '/')
    return (getLeft().getData() / getRight().getData());
     
    else if (this.getData() == '%')
    return(getLeft().getData() % getRight().getData());
     
     
    } // end of if
     
    else if (this.getRight() instanceof OperatorNode && this.getLeft() instanceof OperandNode)
    {
     
    }
     
    else if (this.getRight() instanceof OperandNode && this.getLeft() instanceof OperatorNode)
    {
     
    }
     
    else
    {
     
    }
    }
    }

     
    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);
     
    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 (getNextToken(buffer) instanceof float)
    {
    OperandNode temp = new OperandNode((float) token);
    stackOne.push(temp);
    }
     
    else if (getNextToken(buffer) instanceof Character)
    {
    OperatorNode temp2 = new OperatorNode((char) token);
    if (stackTwo.empty())
    {
    stackTwo.push(temp2);
    }
     
    else
    {
     
    }
    }
     
    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.
    */
     
     
     
    }
     
    }

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


    Have new method to help:

    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 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(root);
     
     
    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.
    */
     
    }
    }

     
    public class InvalidExpressionException extends Exception
    {
     
    // how do you write an exception class again
    // it had something that returned an error message and called super, but what was it?
     
    }
    Last edited by javapenguin; November 13th, 2010 at 08:23 PM.

  3. #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: Evaluating Expressions

    Should I be calling str or getNextToken() as the parameters? I'm thinking getNextToken(), but I don't think I'm doing something right.

    Quote Originally Posted by javapenguin
    Please answer so I don't have to post to myself.

  4. #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: Evaluating Expressions

    left Operator

    right Operand

    a*b+c

    so

    Node root;
    root = '+';
    root.left = '*';
    root.right = c;
    root.left.left = a;
    root.left.right = b;

    read in a. (left)
    perhaps add it to operand stack
    read in '*'(a root) and perhaps add it to operator stack

    read in b; (right) and perhaps add it to operand stack

    push '+';

    push c

    pop a and b and *

    evaluate a*b

    put result of a*b on left
    pop this result and c and '+'

    evaluate (result+c);

    push result;

    done;





    left Operand
    right Operator

    a + b*c

    so

    root = '+';
    root.left = a;
    root.right = '*';
    root.right.left = b;
    root.right.right = c;


    Note, there needs to be something that checks for precedence

    (((a+b) - (c*d))/ ((e%f) * (g+i)))

    should go from left to right and evaluate

    (a+b)

    then evaluate c*d

    then subtract (c*d) from (a+b)

    then it should get that result

    then it should find (e%f) and then (g+i)

    and then multiply (e%f) and (g+i)

    it should have the result of the first divided by result of the second
    and then return the final result

    also

    a * (b+c)

    should evaluate

    (b+c)

    then multiply that times a

  5. #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: Evaluating Expressions

    Treating ‘(‘ in the order of precedence is confusing some of you. Here is another explanation that should make it easier. If you encounter ‘(‘, blindly push it to the operator stack. If the current top of the operator stack is ‘(‘ then the newest operator (the token) always has highest precedence (which means if the top of the stack is ‘(‘, push the new operator onto the stack).

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

    Angry Why isn't the compiler happy?

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

    package ProjectOfDoom;
     
    import java.util.ArrayList;
     
    public abstract class Node
    {
     
    protected ArrayList<Object> childrenHolder;
     
     
     
    public Node()
    {
     
    }
     
     
    public abstract 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());
     
     
     
     
    }
    }

    In class OperatorNode it has this problem:
     

    The method getData() is undefined for the type Node.
    The method getData() is undefined for the type Node.
    The method getData() is undefined for the type Node.
    The method getData() is undefined for the type Node.
    The method getData() is undefined for the type Node.
    The method getData() is undefined for the type Node.
    The method getData() is undefined for the type Node.
    The method getData() is undefined for the type Node.
    The method getData() is undefined for the type Node.
    The method getData() is undefined for the type Node.


    Last edited by javapenguin; November 15th, 2010 at 01:09 PM. Reason: Fixed something

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

    Unhappy Re: Evaluating Expressions

    I now see that it's because I have to have getLeft() and getRight() return a Node since it could be either OperatorNode or OperandNode.

    So Node needs a getData() method.

    But if I parameterize it, then it'll be confused when I extend it.

    Nothing seems to work!

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

    Red face Re: Evaluating Expressions

    I'm so very sorry I lost my temper like that. That was really immature of me.

    I was feeling impatient due to an impending deadline and felt like every other post but mine was being answered. I've tried answering other posts, even though doing so sometimes puts me behind on my own projects, in order to speed up the response time for my own posts. However, it appeared that all my posts were being ignored, in spite of my efforts.


  9. #9
    Super Moderator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,225
    Thanks
    176
    Thanked 817 Times in 760 Posts
    Blog Entries
    5

    Default Re: Evaluating Expressions

    I'll be completely honest - after all of the above I still don't know what your question is (you keep asking why your posts aren't answered, but its hard to answer if we don't know the question, especially if one must invest quite a bit of time going through lines and lines of code and posts to find one). Once again I will point you in the direction of this reference: How to Ask Questions, especially be precise

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

    javapenguin (November 14th, 2010)

  11. #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: Evaluating Expressions

    Above, my OperatorNode could either have an OperatorNode or an OperandNode on its left and right. As I can't predict which one will be there, I have to make left and right be just Node. However, when I try my evaulate method in OperatorNode, the compiler is unhappy because Node doesn't have a getData() method, and I can't give it one unless it returns Object, which creates cast errors if I do that. I just don't know how to handle that. Let's start with that problem.

  12. #11
    Super Moderator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,225
    Thanks
    176
    Thanked 817 Times in 760 Posts
    Blog Entries
    5

    Default Re: Evaluating Expressions

    Quote Originally Posted by javapenguin View Post
    Above, my OperatorNode could either have an OperatorNode or an OperandNode on its left and right. As I can't predict which one will be there, I have to make left and right be just Node. However, when I try my evaulate method in OperatorNode, the compiler is unhappy because Node doesn't have a getData() method, and I can't give it one unless it returns Object, which creates cast errors if I do that. I just don't know how to handle that. Let's start with that problem.
    Now the problem has more of a definition. I don't have the time to go through all that code, but can't you check for the type, then cast it
    if ( node instanceof OperatoreNode ){
        OperatorNode on = (OperatorNode)node;
        ///do what is necessary
    }else if ( node instanceof OperandNode ){
        OperandNode on = (OperandNode)node;
      ///do what is necessary
    }

  13. The Following 2 Users Say Thank You to copeg For This Useful Post:

    javapenguin (November 15th, 2010), JavaPF (November 15th, 2010)

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

    Default Re: Evaluating Expressions

    This is frustrating. I posted a bunch of help in the other thread and you just completely ignored it.

    You don't need a get data method in Node. And the 3 node classes don't need to use generics.

    You don't need a get data method in any of the classes.

    You need to define evaluate for both subclasses of node.

    Then when you don't know whether left/right is an operand/operator node, it doesn't matter because polymorphism will take care of it, when you call evaluate.

    If you are going to ignore helpful (and correct) advice, remind me to ignore your threads in the future

    Good luck.

  15. The Following 2 Users Say Thank You to DavidFongs For This Useful Post:

    javapenguin (November 15th, 2010), JavaPF (November 15th, 2010)

  16. #13
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Evaluating Expressions

    I'm guessing your trying to create an abstract syntax tree. The best method for abstracting your problem is to create an interface call Expression.

    Expressions can be evaluated into some given result, and will always return some data (even if it's null). If you want, you can put generics onto the Expression, or fix it's return type (the generics option is rather time consuming and difficult).

    Then create your Operator nodes as being different from your data nodes. Both nodes should implement the Expression interface (i.e. operators and data can be evaluated). When evaluating data nodes, you only have to returned the data contained inside of them. When evaluating operator nodes, you need to evaluate all the parameter expressions, then perform some operation on these results.

    Here's a short example of what I mean:

    // only supports returning a double for the purposes of this example
    public interface Expression
    {
        public double evaluate();
    }

    /**
     * An add operation. Adds two numbers together.
     */
    public class AddOperation implements Expression // You can provide an abstract base Operation class if you would like, that's actually a better solution
    {
        public Expression Operand1, Operand2;
     
        ... // other code such as an AddOperation constructor
     
        public Double evaluate()
        {
            return Operand1.evaluate() + Operand2.evaluate();
        }
    }

  17. The Following 2 Users Say Thank You to helloworld922 For This Useful Post:

    javapenguin (November 15th, 2010), JavaPF (November 15th, 2010)

  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: Evaluating Expressions

    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<OperatorNode> stackTwo;
    private StringBuffer buffer;
    private String expression2;
    private StringBuffer buffer2;
    public Expression_Tree()
    {
    stackOne = new MyStack<Node>();
    stackTwo = new MyStack<OperatorNode>();
    }
     
    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);
     
    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 (getNextToken(buffer) instanceof double)
    {
    OperandNode temp = new OperandNode((double) token);
    stackOne.push(temp);
    }
     
    else if (getNextToken(buffer) instanceof char)
    {
    OperatorNode temp2 = new OperatorNode((char) token);
    if (stackTwo.empty())
    {
    stackTwo.push(temp2);
    }
     
    else
    {
     
    if (precedence((char) token, stackTwo.top()) ==1)
    {
    stackTwo.push((char) token);
     
    }
     
    else
    {
    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)))
    */
     
     
    }
     
    String bigBeefyString = str6 + ")";
     
    return bigBeefyString;
    }
    }
    Last edited by javapenguin; November 16th, 2010 at 01:49 PM. Reason: Hellllllllllllllllllllppppppppppppppppppppp!!!!!

  19. #15
    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: Evaluating Expressions

    I'm having a hard time understanding what he's asking in the build tree method.

  20. #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: Evaluating Expressions

    So, how do I do this?

    The buildTree().

    I know I'm not doing something right with the token thing.

    I cannot figure out what he wants to do with steps I and 3.

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

    Default Re: Evaluating Expressions

    Reading the pdf (from the other thread, you might want to repost it here for others), I'm not sure how to explain it any more than your professor already did. There are step by step instructions. What exactly do you not understand about it?

    As far as the tokens part, he explains that also. Try running the example expression through your code, and make sure you are getting the exact sequence of tokens that are listed in the pdf.

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

    javapenguin (November 16th, 2010)

  23. #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: Evaluating Expressions

    1.) I don't think my token or buffer size is getting smaller.

    2.) I don't know what he wants with the steps I and 3 on build tree. So I don't know where to put the while loops in there.

  24. #19
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Evaluating Expressions

    Likely what he means by building a tree is to create the abstract syntax tree.

    There are several ways to do this, but I think the easiest method is to convert your input into RPN (reverse polish notation). Then, when you're building the tree, just pop tokens off the stack and build the tree as appropriate.

    For example:

    take the following RPN stack:

    + 1 - 1 2

    Define an expression as either a number, or a binary operator and 2 operands.

    Then, to parse the above stack:

    Read the first token. It's a + statement, build a binary operator expression. This can be done by recursively parsing using the same stack (the first time you're parsing for the left operand, the second time for the right operand). If it's a number, simply return an expression containing that number.

  25. The Following User Says Thank You to helloworld922 For This Useful Post:

    javapenguin (November 16th, 2010)

  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: Evaluating Expressions

    Actually, what I'm doing is right, but how to I get rid of the following errors:

     

    Exception in thread "main" java.lang.Error: Unresolved compilation problems:
    Incompatible conditional operand types String and Double
    Cannot cast from StringBuffer to double
    Incompatible conditional operand types String and Character
    Cannot cast from StringBuffer to char
    Cannot cast from StringBuffer to char
    Cannot cast from StringBuffer to char
    Cannot cast from StringBuffer to char
    Cannot cast from StringBuffer to char

    at projectOfDoom.Expression_Tree.buildTree(Expression _Tree.java:72)
    at projectOfDoom.Test_Expression.main(Test_Expression .java:24)



Similar Threads

  1. VM re-evaluating a string
    By Johannes in forum Java Theory & Questions
    Replies: 6
    Last Post: September 20th, 2010, 04:44 PM
  2. regular expressions
    By brad35309 in forum What's Wrong With My Code?
    Replies: 2
    Last Post: April 5th, 2010, 08:30 PM
  3. why is this statement evaluating false??
    By humdinger in forum Object Oriented Programming
    Replies: 2
    Last Post: November 3rd, 2009, 03:28 PM
  4. Evaluating to negative zero
    By helloworld922 in forum Java Theory & Questions
    Replies: 6
    Last Post: June 25th, 2009, 02:34 PM
  5. Text Processing with Regular Expressions explained in Java
    By JavaPF in forum Java Programming Tutorials
    Replies: 1
    Last Post: August 6th, 2008, 02:03 AM

Tags for this Thread