Results 1 to 4 of 4
  1. #1
    gixxer05 is offline Member
    Join Date
    May 2011
    Posts
    8
    Rep Power
    0

    Default Preorder Binary Expression Tree Help

    Good afternoon,

    I'm a Java newbie who is having a tough really time (approximately 1 week before giving in and asking for help) figuring out how to fill my binary expression tree with operators and operands. I need to recursively add thier values together with polynomials. I'm ok with creating the polynomials, but how can I build the tree and then add the value to the polynomials? I guess the toughest part for me so far is building the tree and determing how to call it from main so that it I can add the values to my polynomial, in the main...my code follows. Can someone please, please help or give me a clue as to what I'm missing? Thanks.
    Java Code:
    class Tree 
    {
    
    // Instance variables
       private Node root;
       private char[] treeString;
       private int stringIndex;
    
    // Constructor that builds a tree from a prefix string
       public Tree(String tree) throws SyntaxException
       {
          treeString = tree.toCharArray();
          stringIndex = 0;
          
          try
          {
             // Initiate building the tree from all elements in the 
             // character array treeString referenced in the makeNode function
             root = makeNode();
    
             // Throw an SyntaxException if there are extra nodes
             // determined if all the elements in the char array does
             // not match the length of the tree...which should be equal
             // since the treeString char[] contains all nodes that are build
             // at once
             if (stringIndex != tree.length())
    
                throw new SyntaxException("Extra Nodes");
          }
          catch (ArrayIndexOutOfBoundsException exception)
          {
             throw new SyntaxException("Missing Nodes");
          }
       }
    
    // Returns the root of the tree
       public Node getRoot()
       {
          return root;
       }
       
    // Creates either an interior or exterior node
       public Node makeNode() throws SyntaxException
       {
          Node node = null, left ,right;
    
          // The character represents an interior node. 
          // (Operators = +, -, *, /)
          // If the character is not a digit, it must be a operator
          if (!Character.isDigit(treeString[stringIndex]))
          {
             
             // Recursive call to return the node to the left and right
             left = makeNode();
             right = makeNode();
             
             // Create a new node containing the new operator
             node = new Interior( treeString[stringIndex], left, right);
             
             // Step to the next char value in the treeString char Array
             stringIndex++;
             
          }
          
          // The character represents an exterior node. 
          // (Operands = integers 1, 2, 10, etc.)
          else 
          {
        	  
        	 // Pass the operand (number value) to the Exterior node constructor
        	 node = new Exterior(treeString[stringIndex]); 
        	   
        	 // Step to the next char value in the treeString char Array
             stringIndex++;
          }
    
          return node;   
       }
       
           // Print all the items in the tree to which root points.
           // The item in the root is printed first, followed by the
           // items in the left subtree and then the items in the
           // right subtree.  
       public void preorderPrint() 
       {
    	   
    	   // Get the root node of the tree
    	   Interior root = (Interior) getRoot();
    	   
    	// If the root node's value is not empty
        if (  root != null ) 
        {  
        	
           // root.evaluate() returns the double value of the current node	
           System.out.print( root.evaluate() + " " );
           
           // Print items in left subtree.
           preorderPrint( root.left );  
           
           // Print items in right subtree.
           preorderPrint( root.right );  
        }
        // (Otherwise, there's nothing to print.)
     } 
    }
    
    
    // Class that represents a node that holds an operator.
    class Interior extends Node
    {
    
       // Instance variables
       private Node left, right;
       
       // The operator.
       char op;        
    
       // Constructor
       public Interior(char op, Node left, Node right)
       {
    	  this.op = op;
          this.left = left;
          this.right = right;
       }
    
    
       double evaluate() 
       {
    
         double leftVal = left.evaluate();
         double rightVal = right.evaluate();
         
        // To get the value, compute the value of the left and
        // right operands, and combine them with the operator.  
         switch ( op ) 
         {
         
             case '+':  return leftVal + rightVal;
             case '-':  return leftVal - rightVal;
             case '*':  return leftVal * rightVal;
             case '/':  return leftVal / rightVal;
             
             // Bad operator.
             default:   return Double.NaN;  
          }
     }
    }
    
    
    //Represents a node that holds a number.
    class Exterior extends Node
    {
    	
         // The number in the node.
    	 double number;  
    	
      Exterior( double val ) 
      {
    	  
         // Constructor.  Create a node to hold the number value.
         number = val;
      }
    
      double evaluate() 
      {
    	  
         // The value is just the number that the node holds.
         return number;
      }
    }
    
    
    //In my main, I'm trying to get the tree to print it's values and get the simplified
     expression by calling the methods like so:
    		
                              Tree t = new Tree(prefixexpression);
    		
    		// Print the tree values to the console
    		t.preorderPrint();
    		
    		// Get the simplified prefix expression
    		double val;
    		Node n = null;
    		val = n.evaluate();
    Last edited by gixxer05; 05-11-2011 at 11:03 PM.

  2. #2
    gixxer05 is offline Member
    Join Date
    May 2011
    Posts
    8
    Rep Power
    0

    Default

    I need to do the following:
    1. create a binary expression tree from command line input witch can be like the following: 1 3 * / 3 + 7,
    2. all operators should be interior nodes and numbers exterior nodes
    3. perform the mathmatical operations in preorder form
    4. output the simplified value to: public static void main(final String[] args) throws IOException, SyntaxException {}

    Specifically, I'm having trouble devising how to access the left and right root values. The root.left and root.right references are not working in the preorderPrint() function. How do I reference the two pointers, when they are in the Interior class, which extends the Node class? Is this even an appropriate way to access the nodes? Is my implementation correct? Thanks for your help.

  3. #3
    gixxer05 is offline Member
    Join Date
    May 2011
    Posts
    8
    Rep Power
    0

    Default Please help

    My project specification may give some clarification of what I'm attempting to acheive with my code:

    A prefix expression consists of operators and operands. The operators can be any of the following +, - * or /. The operands can be either an unsigned (i.e. positive) constant or a call to a polynomial function. The user should be prompted first for the prefix expression.

    The input might look as follows: + * 2.5 + P 7.4 6.3 8
    The infix equivalent for the above user input is: ((2.5 * (P(7.4) + 6.3)) + 8)

    After the prefix expression is input, one polynomial should be input that corresponds to the polynomial P in the expression. The format should be the same as Project 1. For example, 5 3 4 1 8 0 represents the polynomial 5x3 + 4x + 8.

    After the expression and polynomial have been input, the expression should be evaluated and its value should be displayed.

    Example 1
    Please input prefix expression: + * 2.5 + P 7.4 6.3 8
    Please input the polynomial: 5 2 2 0
    The value of the expression is: 713.25

    So I'm attempting read in the characters and build the binary tree.
    Then I'm attempting to recursively print the binary tree values (both operators/Interior class nodes and operands/Exterior class nodes), for example:

    Get the input from the user, from the commandline: + * 2 3 5 P

    +
    . .
    . .
    * P
    . . .
    . . .
    2 3 5

    Do a inorder traversal of the tree to produce a infix expression and
    print it from preorderPrint: 2 * 3 + 5 P

    Note: only operators can be parents, meaning they can have branches, or leafs, created by the Interior method because they are interior nodes. The operands, or numbers, will be on a branch and will not be a parent so they are exterior nodes created in the Exterior class.

    I made the suggested name changes to variables in my cade. Thanks for the tips. I hope I'm being helpful.

  4. #4
    Norm's Avatar
    Norm is online now Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,611
    Rep Power
    25

    Default

    If you understand the logic of what your program is to do (at this point I don't), then perhaps you need to use some debugging techniques to see if your program is doing what you want it to do.
    If you don't have an interactive debugger, then you can use print statements to show how the variable values change and how the program logic flows. Add LOTS of print statements to show variable names and their values as the program executes.

Similar Threads

  1. binary tree
    By ryamz in forum New To Java
    Replies: 2
    Last Post: 08-12-2010, 03:45 AM
  2. Replies: 0
    Last Post: 04-04-2010, 08:40 AM
  3. Help creating expression tree
    By nellaf in forum New To Java
    Replies: 8
    Last Post: 12-04-2009, 05:17 AM
  4. Binary Tree
    By MuslimCoder in forum New To Java
    Replies: 8
    Last Post: 11-19-2009, 06:57 PM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •