Improve company productivity with a Business Account.Sign Up

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 522
  • Last Modified:

parsing an input express creating an expression tree with the tokens, then use a postorder tree transversal to extrace a postifx expression

Trying to do this program but after all my research on expression trees I am still drawing a blank.  Can anyone get me started in the right direction.  First of all I need a class to use for the tree.  
And then some hints if not outright direction on how to proceed.  I have code from other programs I have done to evaluate the infix expression for validity, but then I need to build the tree.  I understand the basic concept for building a tree (graphically in that I can trace the logic on paper), but not how to do it programatically(?).  I have search EE for this and there are 10 hits, but they did not help me.

Thanks in advance for your assistance.   I will be glad to break this into several questions for additional points if desired.
0
jjackson2004
Asked:
jjackson2004
  • 7
  • 4
4 Solutions
 
ValeriCommented:
I think it will help you:
http://www.javacoffeebreak.com/books/extracts/javanotesv3/c11/s4.html
Have a look at the end of the article - Expression trees.
0
 
imladrisCommented:
The basic building block of a tree is a class that contains a data element and pointers to sub nodes. Something like:

class TreeNode
{    String data;
      TreeNode left,right;

      TreeNode(String d)
      {    data=d;
            left=right=null;
            return;
      }
}

You could start with creating the rootnode referenced by variable root. Then add nodes to hold additional data, and set the left and right "pointers" to other TreeNodes lower down on the tree, etc.
0
 
jjackson2004Author Commented:
OK.  thanks for the first link.  It helped a lot.  I am following it's advice and going with the two node types, one for the operators and one for the operands.  They are listed below.  Next I need stacks for the nodes.  I modified stacks from a similar program I did and this is also listed below.  I am starting out slow on this one because I become so frustrated with the syntax picky type errors.  So I have put these in netbeans and no errors so far.  Would you please check over and make sure my logic is acceptable so far?

Also, is there a way to make an interface for the two stacks and then extend them.  If so, would you mind showing me the proper coding?  No. Skip that for now, I need to get this up and running to show very soon.

Thanks
Made a test program while I build the different parts.

****************************

public class test {

    public static void main(String[] args) {


        abstract class ExpNode {
              // Represents a node of any type in an expression tree.

           abstract int value();  // Return the value of this node.

       } // end class ExpNode


       class ConstNode extends ExpNode {
              // Represents a node that holds a number.

           int number;  // The number in the node.

           ConstNode( int val ) {
                 // Constructor.  Create a node to hold val.
              number = val;
           }

           int value() {
                 // The value is just the number that the node holds.
              return number;
           }

        } // end class ConstNode


        class BinOpNode extends ExpNode {
              // Represents a node that holds an operator.

           char op;        // The operator.
           ExpNode left;   // The left operand.
           ExpNode right;  // The right operand.

           BinOpNode( char op, ExpNode left, ExpNode right ) {
                 // Constructor.  Create a node to hold the given data.
              this.op = op;
              this.left = left;
              this.right = right;
           }

           int value() {
                 // To get the value, compute the value of the left and
                 // right operands, and combine them with the operator.
               int leftVal = left.value();
               int rightVal = right.value();
               switch ( op ) {
                   case '+':  return leftVal + rightVal;
                   case '-':  return leftVal - rightVal;
                   case '*':  return leftVal * rightVal;
                   case '/':  return leftVal / rightVal;
                   default:   return 0;  // Bad operator.
                }
           }

        } // end class BinOpNode

    //  stack class to handle postfix calculation temporary storage
  class operandStack {
    private int maxSize;
    private ConstNode[] stackArray;
    private int top;
    public operandStack(int size) {
      maxSize = size;
      stackArray = new ConstNode[maxSize];
      top = -1;
    }
    public void push(ConstNode j) {
      stackArray[++top] = j;
    }
    public ConstNode pop() {
      return stackArray[top--];
    }
    public ConstNode peek() {
      return stackArray[top];
    }
    public boolean isEmpty() {
      return (top == -1);
    }
    public boolean isFull() {
      return (top == maxSize - 1);
    }
    public int size() {
      return top + 1;
    }
    public ConstNode peekN(int n) {
      return stackArray[n];
    }

  }

  class operatorStack {
    private int maxSize;
    private BinOpNode[] stackArray;
    private int top;
    public operatorStack(int size) {
      maxSize = size;
      stackArray = new BinOpNode[maxSize];
      top = -1;
    }
    public void push(BinOpNode j) {
      stackArray[++top] = j;
    }
    public BinOpNode pop() {
      return stackArray[top--];
    }
    public BinOpNode peek() {
      return stackArray[top];
    }
    public boolean isEmpty() {
      return (top == -1);
    }
    public boolean isFull() {
      return (top == maxSize - 1);
    }
    public int size() {
      return top + 1;
    }
    public BinOpNode peekN(int n) {
      return stackArray[n];
    }

  }

    }
}

0
Get your problem seen by more experts

Be seen. Boost your question’s priority for more expert views and faster solutions

 
jjackson2004Author Commented:
Also, as I look over this code, I have a question.  Why are the left and right variables in:

        class BinOpNode extends ExpNode {
              // Represents a node that holds an operator.

           char op;        // The operator.
           ExpNode left;   // The left operand.
           ExpNode right;  // The right operand.

Why are they of type ExpNode?  Why are they not ConstNode?
0
 
jjackson2004Author Commented:
Is by it being ExpNode, it can hold either the BinOpNode and ConstNode?
0
 
ValeriCommented:
>> Is by it being ExpNode, it can hold either the BinOpNode and ConstNode?
Exactly! That's the answer
0
 
jjackson2004Author Commented:
I have to accept an 'x' in the infix expression.  Currently I can't handle it with the nodes I have.  Should I create a third node class that extends the first one.  This one will only hold 'x'.  Should I just hard code it that way?  And so my operand stack would hold either the binopnode or the xnode?
0
 
jjackson2004Author Commented:
I tried to create a third node, but it violated the abstract value method.  So now I am stuck.  Can someone help me with the logic.

let's say i use  (4 + 5/2) as infix string.

I parse the '(' and put on a stack (what stack should I use here)
next the 4 is pushed on a different stack.
'+' is put on an operand stack.
5 is pushed on number stack
/ is pushed on operand stack
2 is pushed on number stack
) causes me to start popping things off stack.
now I should be creating the expression tree, but how?
0
 
jjackson2004Author Commented:
ok, I have the following code, but now I need to change the passed variable to expTree from scanner to String.  Also want to change from double to int.  for the string, what do I use instead of hasNextInt(),nextInt() and next()?

public class ExpressionTree
{
    private static class TreeNode
   {
      private final boolean  leaf;   // ?Is this a leaf? else internal
      private final char     op;     // For an internal node, the operator
      private       double   value;  // For a leaf, the value
      private       TreeNode left,   // Left subexpression for an internal node
                             right;  // Right subexpression

      // Bare-bones constructor
      private TreeNode ( boolean leaf, char op, double value )
      {
         this.leaf    = leaf;
         this.op      = op;
         this.value   = value;
         this.left    = null;   // Empty to start
         this.right   = null;
      }

      // For leaf nodes, show the value; for internal, the operator.
      public String toString()    // To override Object.toString, must be public.
      {  return leaf ? Double.toString(value) : Character.toString(op) ;  }
   }

   TreeNode root = null;

   public ExpressionTree ( Scanner input )
   {  root = build(input);  }

/**
 * Based on a white-space delimited prefix expression, build the
 * corresponding binary expression tree.
 * @param  input  The scanner with the expression
 * @return reference to the corresponding binary expression tree
 */
   private TreeNode build ( Scanner input )
   {
      boolean  leaf;
      String   token;
      double   value;
      TreeNode node;

      leaf = input.hasNextDouble();
      if ( leaf )
      {
         value = input.nextDouble();
         node = new TreeNode ( leaf, '\0', value );
      }
      else
      {
         token = input.next();
         node  = new TreeNode ( leaf, token.charAt(0), 0.0 );
         node.left  = build ( input );
         node.right = build ( input );
      }
      return node;
   }

0
 
jjackson2004Author Commented:
Has this question been abandoned by the experts?  Should I even bother continue to ask questions.  T
he last three entries are mine.

I have another question that is now the relevant question.
0
 
ValeriCommented:
Here is the continuation for "x"
http://math.hws.edu/eck/cs124/javanotes3/c11/ex-11-6-answer.html
Hope it will help you.
Btw you can not expect answers immediately. Some of the peoples sleep when other works, because they live on the other side of earth :-)
0
 
ValeriCommented:
...and when you consider a question as abandoned or you are not satisfied by the answers you can delete it.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

  • 7
  • 4
Tackle projects and never again get stuck behind a technical roadblock.
Join Now