Generate syntax tree for simple math operations
- by M28
I am trying to generate a syntax tree, for a given string with simple math operators (+, -, *, /, and parenthesis).
Given the string "1 + 2 * 3":
It should return an array like this:
["+",
[1,
["*",
[2,3]
]
]
]
I made a function to transform "1 + 2 * 3" in [1,"+",2,"*",3].
The problem is: I have no idea to give priority to certain operations.
My code is:
function isNumber(ch){
switch (ch) {
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
case '.':
return true;
break;
default:
return false;
break;
}
}
function generateSyntaxTree(text){
if (typeof text != 'string') return [];
var code = text.replace(new RegExp("[ \t\r\n\v\f]", "gm"), "");
var codeArray = [];
var syntaxTree = [];
// Put it in its on scope
(function(){
var lastPos = 0;
var wasNum = false;
for (var i = 0; i < code.length; i++) {
var cChar = code[i];
if (isNumber(cChar)) {
if (!wasNum) {
if (i != 0) {
codeArray.push(code.slice(lastPos, i));
}
lastPos = i;
wasNum = true;
}
} else {
if (wasNum) {
var n = Number(code.slice(lastPos, i));
if (isNaN(n)) {
throw new Error("Invalid Number");
return [];
} else {
codeArray.push(n);
}
wasNum = false;
lastPos = i;
}
}
}
if (wasNum) {
var n = Number(code.slice(lastPos, code.length));
if (isNaN(n)) {
throw new Error("Invalid Number");
return [];
} else {
codeArray.push(n);
}
}
})();
// At this moment, codeArray = [1,"+",2,"*",3]
return syntaxTree;
}
alert('Returned: ' + generateSyntaxTree("1 + 2 * 3"));
