468,257 Members | 1,427 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,257 developers. It's quick & easy.

Help with a java program (binary tree)

Hey guys, is there anyone who could help me..?

I have file ExpressionBinaryTree.java :


Expand|Select|Wrap|Line Numbers
  1.  
  2. /** class ExpressionBinaryTree
  3. *   uses a binary tree to represent binary expressions
  4. *   does not implement BinaryTree - all iterators return String
  5. */
  6. package foundations;
  7. import java.util.*;
  8. public class ExpressionBinaryTreeE implements Container {
  9.     // Fields
  10.     private SearchTreeNode root = null;
  11.     private int size = 0;
  12.     private String postfixString;
  13.     // Constructors
  14.     /** Create an empty expression tree
  15.     */
  16.     public ExpressionBinaryTreeE () {
  17.     }
  18.     /** Create and initialize an expression tree on infix
  19.     */
  20.     public ExpressionBinaryTreeE (String infix) {
  21.         postfixString = (new FunctionEvaluation(infix)).postfix();
  22.         buildExpressionTree();
  23.     }
  24.     // Commands
  25.     /** Set a new value for infix
  26.     *   updates postfixString and rebuilds expression tree
  27.     */
  28.     public void setInfixString (String infix) {
  29.         postfixString = (new FunctionEvaluation(infix)).postfix();
  30.         buildExpressionTree();
  31.     }
  32.     /** Set a new value for postfixString
  33.     */
  34.     public void setPostfixString (String postfix) {
  35.         //  remove blanks then build expression tree
  36.         //   left as an exercise
  37.     }
  38.     /** Remove all objects from the container if found
  39.     */
  40.     public void makeEmpty () {
  41.         root = null;
  42.     }
  43.     // Queries
  44.     /** Return a reference to the root
  45.     */
  46.     public SearchTreeNode root () {
  47.         return root;
  48.     }
  49.     /** Return true if the container is empty
  50.     */
  51.     public boolean isEmpty () {
  52.         return root == null;
  53.     }
  54.     /** Return the number of objects in the container
  55.     *   postfixString has been trimmed
  56.     */
  57.     public int size () {
  58.         return size;
  59.     }
  60.     /** Return the infix string on elements in the tree
  61.     */
  62.     public String traverseInorder () {
  63.         // left as an exercise
  64.         return "";
  65.     }
  66.     /** return the prefix string on elements in the tree
  67.     */
  68.     public String traversePreorder () {
  69.         // left as an exercise
  70.         return "";
  71.     }
  72.     /** Return the postfix on elements in the tree
  73.     */
  74.     public String traversePostorder () {
  75.         //left as an exercise
  76.         return "";
  77.     }
  78.     // Internal methods
  79.     /** Build an expression tree from postfixString
  80.     *   - use a Stack of SearchTreeNode
  81.     *   throw NoSuchElementException for caught Stack error
  82.     */
  83.     private void buildExpressionTree () {
  84.         // left as an exercise
  85.     }
  86.     private boolean isOperand (char ch) {
  87.         // left as an exercise
  88.         return false;
  89.     }
  90.     private boolean isOperator (char ch) {
  91.         //left as an exercise
  92.         return false;
  93.     }
  94. }
  95.  
Also I have a supporting class (SearchTreeNode.java) for ExpressionBinaryTree and a test class ExpressionTest.java

Expand|Select|Wrap|Line Numbers
  1. ** A test class for ExpressionBinaryTree (prefix input)
  2. */
  3. import foundations.*;
  4. import java.io.*;
  5. public class ExpressionTest{
  6.     public static void main(String[] args) throws IOException {
  7.         ExpressionBinaryTreeE expr = new ExpressionBinaryTreeE("a+b/(c-d)-e");
  8.         if (!expr.isEmpty()){
  9.             System.out.println("The number of terms in the tree is: " + expr.size());
  10.             System.out.println("Equiv infix string is:   " + expr.traverseInorder());
  11.             System.out.println("Equiv prefix string is:  " + expr.traversePreorder());
  12.             System.out.println("Equiv postfix string is: " + expr.traversePostorder());
  13.         }
  14.         System.out.println("Test makeEmpty()");
  15.         expr.makeEmpty();
  16.         System.out.println("The number of terms in the tree is: " + expr.size() + "\n");
  17.         expr.setInfixString("a*b/(c-d)*e");//"a*b-(c-d*e)+f/(g-h)" or "a+b-(c-d*e)"
  18.         if (!expr.isEmpty()){
  19.             System.out.println("The number of terms in the tree is: " + expr.size());
  20.             System.out.println("Equiv infix string is:   " + expr.traverseInorder());
  21.             System.out.println("Equiv prefix string is:  " + expr.traversePreorder());
  22.             System.out.println("Equiv postfix string is: " + expr.traversePostorder());
  23.         }
  24.         System.out.println("Test makeEmpty()");
  25.         expr.makeEmpty();
  26.         System.out.println("The number of terms in the tree is: " + expr.size() + "\n");
  27.         expr.setInfixString("a+(b-c)-d/e");//"a*b-(c-d*e)+f/(g-h)" or "a+b-(c-d*e)"
  28.         if (!expr.isEmpty()){
  29.             System.out.println("The number of terms in the tree is: " + expr.size());
  30.             System.out.println("Equiv infix string is:   " + expr.traverseInorder());
  31.             System.out.println("Equiv prefix string is:  " + expr.traversePreorder());
  32.             System.out.println("Equiv postfix string is: " + expr.traversePostorder());
  33.         }
  34.         System.out.println("Test makeEmpty()");
  35.         expr.makeEmpty();
  36.         System.out.println("The number of terms in the tree is: " + expr.size() + "\n");
  37.         expr.setInfixString("a*b-(c-d*e)+f/(g-h)");//"a*b-(c-d*e)+f/(g-h)" or "a+b-(c-d*e)"
  38.         if (!expr.isEmpty()){
  39.             System.out.println("The number of terms in the tree is: " + expr.size());
  40.             System.out.println("Equiv infix string is:   " + expr.traverseInorder());
  41.             System.out.println("Equiv prefix string is:  " + expr.traversePreorder());
  42.             System.out.println("Equiv postfix string is: " + expr.traversePostorder());
  43.         }
  44.         System.out.println("Test makeEmpty()");
  45.         expr.makeEmpty();
  46.         System.out.println("The number of terms in the tree is: " + expr.size() + "\n");
  47.         BufferedReader keyboard = new BufferedReader(new InputStreamReader(System.in));
  48.         String postfix = "";
  49.         do {
  50.             System.out.print("Enter a postfix string: ");
  51.             postfix = keyboard.readLine();
  52.             expr.setPostfixString(postfix);
  53.             if (!expr.isEmpty()){
  54.                 System.out.println("The number of terms in the tree is: " + expr.size());
  55.                 System.out.println("Equiv infix string is:   " + expr.traverseInorder());
  56.                 System.out.println("Equiv prefix string is:  " + expr.traversePreorder());
  57.                 System.out.println("Equiv postfix string is: " + expr.traversePostorder());
  58.             }
  59.             System.out.println("Test makeEmpty()");
  60.             expr.makeEmpty();
  61.             System.out.println("The number of terms in the tree is: " + expr.size() + "\n");
  62.         } while (postfix.length() >= 3);
  63.     }
  64. }
  65.  
  66.  
Batch file Go. bat compiles all source files and runs the test class:

Expand|Select|Wrap|Line Numbers
  1. javac ExpressionTest.java
  2. java ExpressionTest
  3. del *.class
  4. del foundations\*.class
  5.  
I am required to complete the details for class ExpressionBinaryTree. Additional statements may be added to class ExpressionTest to expand on the testing performed.

Any ideas....?
Nov 16 '08 #1
2 6984
JosAH
11,448 Expert 8TB
I am required to complete the details for class ExpressionBinaryTree. Additional statements may be added to class ExpressionTest to expand on the testing performed.

Any ideas....?
Yup, I'd say that additional statements have to be added to that class because
as it is now it is an empty class, i.e. there are no useful things in it at all.

You have to write an entire parser; an AST (Abstract Syntax Tree) and a few
methods that transfer that AST to postfix, prefix and infix form. We won't do
it for you but if you're stuck we're very willing to help so get going.

kind regards,

Jos
Nov 16 '08 #2
Thank You Jos!! :) Helped me a lot.
Nov 17 '08 #3

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

54 posts views Thread by Spammay Blockay | last post: by
1 post views Thread by Jerry Khoo | last post: by
4 posts views Thread by Tarique Jawed | last post: by
66 posts views Thread by genestarwing | last post: by
1 post views Thread by satan | last post: by
memoman
4 posts views Thread by memoman | last post: by
3 posts views Thread by KLonergan | last post: by
reply views Thread by kermitthefrogpy | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.