1 Reply Latest reply: Apr 16, 2007 9:49 PM by 807606 RSS

    Binary Expression Tree

    807606
      Okay, so I have a project for a class at school in which I have to make a binary tree to evaluate a compound expression.

      A String is input in the format "((5*2)+(3*(5-4)))", and a BinaryExpressionTree should be made... but I have no clue how to make it from user input.

      Here's the full class (well, what I have of it so far):
      public class BinaryExpressionTree{
          static class Node{
              Node left;
              Node right;
              Character value;
          
              public Node(char newValue) {
                  value = new Character(newValue);
              }
          }
        
          public BinaryExpressionTree(char rootVal){
              Node root = new Node(rootVal);
          }
          
          public void insert(Node node, char value) {
              if (value < node.value) {
                  if (node.left != null) {
                      insert(node.left, value);
                  } else {
                      System.out.println("  Inserted " + value + " to left of " + node.value);
                      node.left = new Node(value);
                  }
              } else if (value > node.value) {
                  if (node.right != null) {
                      insert(node.right, value);
                  } else {
                      System.out.println("  Inserted " + value + " to right of " + node.value);
                      node.right = new Node(value);
                  }
              }
          }
          
          public void insertLeft(Node node, char value) {
              if (node.left != null) {
                  insertLeft(node.left, value);
              } else {
                  System.out.println("  Inserted " + value + " to left of " + node.value);
                  node.left = new Node(value);
              }
          }
          
          public void insertRight(Node node, char value) {
              if (node.right != null) {
                  insertRight(node.right, value);
              } else {
                  System.out.println("  Inserted " + value + " to right of " + node.value);
                  node.right = new Node(value);
              }
          }
          
          public void printInOrder(Node node) {
              if (node != null) {
                  printInOrder(node.left);
                  System.out.println("  Traversed " + node.value);
                  printInOrder(node.right);
              }
          }
        
          public void printPreOrder(Node node) {
              if (node != null) {
                  System.out.println("  Traversed " + node.value);
                  printPreOrder(node.left);
                  printPreOrder(node.right);
              }
          }
        
          public void printPostOrder(Node node) {
              if (node != null) {
                  printPostOrder(node.left);
                  printPostOrder(node.right);
                  System.out.println("  Traversed " + node.value);
              }
          }
          
          public int evaluateTree(Node node){
              if(node.value.equals('*')){
                  return (evaluateTree(node.left) * evaluateTree(node.right));
              } else if(node.value.equals('/')){
                  return (evaluateTree(node.left) / evaluateTree(node.right));
              } else if(node.value.equals('+')){
                  return (evaluateTree(node.left) + evaluateTree(node.right));
              } else if(node.value.equals('-')){
                  return (evaluateTree(node.left) - evaluateTree(node.right));
               } else {
                    return (int) node.value;
               }
           }
      }
      Any pokes in the right direction are appreciated...
        • 1. Re: Binary Expression Tree
          807606
          Well, you have a string, right? And that string can be broken down into meaningful "tokens", which in this case would mean parentheses, numbers, and operator identifiers. Right?

          So first you'd have to break down that string into a sequence of tokens. This is called "tokenizing".
          Then you just go through that sequence, look at each token, and decide what to do. What you'll be doing generally is creating the tree, typically by either adding nodes, or going back up nodes you've already created. What to do in particular will depend a lot on where you are in the three that you're creating. This is called "parsing".