DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

Expression Tree Builder

06.22.2007
| 4505 views |
  • submit to reddit
        EvalExp(s) turns the string s into an expression tree and returns it.

Inorder, preorder and postorder can then be used to turn transform the tree into inorder, preorder or postorder expressions.

function inorder(T) {
  if ((T.cargo  == '+') || (T.cargo  == '-') || (T.cargo  == '*') || (T.cargo  == '/'))
    return [].concat(inorder(T.left)).concat(T.cargo).concat(inorder(T.right));

  return new Array(T.cargo);
}

function preorder(T) {
  if ((T.cargo  == '+') || (T.cargo  == '-') || (T.cargo  == '*') || (T.cargo  == '/'))
    return [].concat(T.cargo).concat(preorder(T.left)).concat(preorder(T.right));

  return new Array(T.cargo);
}

function postorder(T) {
  if ((T.cargo  == '+') || (T.cargo  == '-') || (T.cargo  == '*') || (T.cargo  == '/'))
    return [].concat(postorder(T.left)).concat(postorder(T.right)).concat(T.cargo);

  return new Array(T.cargo);
}

function Tree(cargo, left, right) {
  this.cargo = cargo;
  this.left = left;
  this.right = right;
}

function split(s) {
  var r = [];
  var cur = '';
  for (var i = 0; i < s.length; ++i) {
    var c = s.charAt(i);
    if ((c == '+') || (c == '-') || (c == '*') || (c == '/') || (c == '(') || (c == ')')) {
      cur.replace(" ", "");
      if (cur.length > 0) {
        r.push(cur);
        cur = '';
      }
      r.push(c);
    } else {
      cur += c;
    }
  }
  if (cur.length > 0)
    r.push(cur);

  return r;
}

function getToken(tokens, expected) {
  if (tokens[0] == expected) {
    tokens.splice(0, 1);
    return true;
  }
    return false;
}

function getVar(tokens) {
  if (getToken(tokens, '(')) {
    var a = getSum(tokens);
    getToken(tokens, ')');

    return a;
  } else {
    var aux = tokens[0];
    tokens.splice(0, 1);

    return new Tree(aux, undefined, undefined);
  }
}

function getProduct(tokens) {
  var a = getVar(tokens);

  if (getToken(tokens, '*')) {
    var b = getProduct(tokens);

    return new Tree('*', a, b);
  } else if (getToken(tokens, '/')) {
    var b = getProduct(tokens);

    return new Tree('/', a, b);
  }

  return a;
}

function getSum(tokens) {
  var a = getProduct(tokens);

  if (getToken(tokens, '+')) {
    var b = getSum(tokens);

    return new Tree('+', a, b);
  } else if (getToken(tokens, '-')) {
    var b = getSum(tokens);

    return new Tree('-', a, b);
  }

  return a;
}

function evalExp(s) {
  var tokens = split(s);

  //alert(tokens);

  return t = getSum(tokens);
}
    

Comments

Snippets Manager replied on Mon, 2006/06/19 - 6:43pm

Cool stuff. I think you can make this code a bit shorter by using regular expressions. For example I rewrote your split() using jQuery as follows (I renamed your split() function to avoid confusion with javascript's native split() method): function tokenize(s) { var r = []; var c = ""; var result = s.split(/(AND|OR|\(|\))/); $.each(result,function(i,val){ c = val.replace(/ /g,''); // strip whitespace if(c.length < 1) return true; // continue in jQuery's $.each utility r.push(c); }); return r; } I'm using custom tokens; it doesn't matter -- the code will tokenize on whatever delimeters you put in that regex. Note that since the regex has parentheses around the outside it will also return the split() delimiters. Regexes also make the main recursion slightly less repetitive by removing the need for an else if block to represent each token case: // (Destructively) pop an item off the beginning of an array // and return the shifted value for (optional) assignment. function shift(arr) { return arr.splice(0,1); } function get_tree(tokens) { var a = get_var(tokens); var match = /(AND)|(OR)/i.exec(tokens[0]); if(match !== null) { shift(tokens); var b = get_tree(tokens); return new Tree(match[1],a,b); } return a; } I'm sure this can still be improved; in any event, thanks for giving me a head start on the algorithm. Noah