tree.js

"use strict";

var operatorPrecedence = {
	"+": 1,
	"*": 2,
	"**": 3
};

function Tree() {
}

Tree.prototype.first = function(token) {
	this.root = {name: null, left: token, right: null, precedence: null, parent: null};
	this.current = this.root;
};

Tree.prototype.add = function(token) {
	var precedence = operatorPrecedence[token];

	if(precedence) {
		if(this.current.right) {
			while(this.current && precedence <= this.current.precedence) {
				this.current = this.current.parent;
			}

			if(this.current) {
				this.current.right = {name: token, left: this.current.right, right: null, precedence: precedence, parent: this.current};
				this.current = this.current.right;
			} else {
				this.root = {name: token, left: this.root, right: null, precedence: precedence, parent: null};
				this.current = this.root;
			}
		} else {
			if(this.current.name) {
				throw new SyntaxError("Unexpected " + token);
			} else {
				this.current.name = token;
				this.current.precedence = precedence;
			}
		}
	} else {
		if(this.current.right) {
			throw new SyntaxError("Unexpected " + token);
		}

		this.current.right = token;
	}
};

function orderTraverse(node) {
	if(typeof node === "string") {
		return node;
	}

	return "(" + orderTraverse(node.left) + node.name + orderTraverse(node.right) + ")";
}

var tree = new Tree();
var tokens = process.argv[2].split(" ");
tree.first(tokens[0]);
for(var i = 1; i < tokens.length; i++) {
	tree.add(tokens[i]);
}

console.log(orderTraverse(tree.root));
//console.log(require("treet")(tree.root));