Solved

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

Posted on 2010-11-29
12
497 Views
Last Modified: 2012-05-10
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
Comment
Question by:jjackson2004
  • 7
  • 4
12 Comments
 
LVL 16

Accepted Solution

by:
Valeri earned 400 total points
ID: 34236741
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
 
LVL 16

Assisted Solution

by:imladris
imladris earned 100 total points
ID: 34239954
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
 

Author Comment

by:jjackson2004
ID: 34245531
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
 

Author Comment

by:jjackson2004
ID: 34245593
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
 

Author Comment

by:jjackson2004
ID: 34245662
Is by it being ExpNode, it can hold either the BinOpNode and ConstNode?
0
 
LVL 16

Assisted Solution

by:Valeri
Valeri earned 400 total points
ID: 34245935
>> Is by it being ExpNode, it can hold either the BinOpNode and ConstNode?
Exactly! That's the answer
0
How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

 

Author Comment

by:jjackson2004
ID: 34250431
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
 

Author Comment

by:jjackson2004
ID: 34251432
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
 

Author Comment

by:jjackson2004
ID: 34253361
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
 

Author Comment

by:jjackson2004
ID: 34253939
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
 
LVL 16

Assisted Solution

by:Valeri
Valeri earned 400 total points
ID: 34255355
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
 
LVL 16

Expert Comment

by:Valeri
ID: 34255389
...and when you consider a question as abandoned or you are not satisfied by the answers you can delete it.
0

Featured Post

How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

Join & Write a Comment

For beginner Java programmers or at least those new to the Eclipse IDE, the following tutorial will show some (four) ways in which you can import your Java projects to your Eclipse workbench. Introduction While learning Java can be done with…
Introduction This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used by…
Viewers learn about the “for” loop and how it works in Java. By comparing it to the while loop learned before, viewers can make the transition easily. You will learn about the formatting of the for loop as we write a program that prints even numbers…
The viewer will learn how to implement Singleton Design Pattern in Java.

758 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now