So in part 1 of this series, we tokenized our mathematical expression. In part 2, we parsed our tokens into RPN and built our Abstract Syntax Tree (AST). Here in part 3, we are going to go ahead and evaluate our AST and evaluate our expressions down to an actual answer. Just to reiterate, our AST for '1 + 1 - 2' looks like this:
{
"value": "-",
"left": {
"value": "+",
"left": {
"value": "1"
},
"right": {
"value": "1"
}
},
"right": {
"value": "2"
}
}
So we have our AST and now we have to traverse it to evaluate. tree traversal is made easy with recursive functions, and we are going to do what is known as Preorder Traversal. This is a type of tree traversal where we visit the root node first, and then travel the left side of our tree, followed by the right side. Lets get started by defining the different operations we will need to evaluate, and writing some pseudo code for our tree traversal:
const ops = {
'+': (...ops) => ops.reduce((acc, cur) => acc + cur),
'-': (...ops) => ops.reduce((acc, cur) => acc - cur),
};
const evaluate = ast => {
let result = 0;
// if we have an operation
// grab operation func, call: operation(evaluate(left), evaluate(right))
// else we have a Number
// return value
return result;
};
Our operations object is straight forward enough, we only handle + and - (for now). As far as our evaluate function, we know we will have a result and to return it, and we pseudo coded out what we need to do. We will take our node and recursively call evaluate on the left and right nodes, which will travel down the tree until they hit values. The will then bring those values up and resolve the function calls by executing the operations. This is how we will evaluate the result of expressions and pass the values into the following expressions. We will bring the values "up" the tree and run our operator functions on them until we have gone through all our expressions and produce an answer.
const ops = {
'+': (...ops) => ops.reduce((acc, cur) => acc + cur),
'-': (...ops) => ops.reduce((acc, cur) => acc - cur),
};
const evaluate = ast => {
let result = 0;
if (ops[ast.value]) {
result += ops[ast.value](evaluate(ast.left), evaluate(ast.right));
} else {
return Number(ast.value);
}
return result;
}
And finally, putting it all together
console.log(evaluate(parseAST(tokenize('1 + 1 - 2')))) // 0
console.log(evaluate(parseAST(tokenize('1 + 7 - 2')))) // 7
console.log(evaluate(parseAST(tokenize('9 + 7 - 3')))) // 13
Looks like we are evaluating to the correct solutions! There are definitely a lot of optimizations we could make here, but we got to our initial goal of being able to parse out and evaluate mathetmatical expressions! This would be considered a basic interpreter, so it functions similarly to how programming languages are evaluated.
Now that we've reach our goal, let's work on adding in a bit more functionality. Namely, we want to be able to support multiplication and division. One of the nice parts about only handling addition and subtraction is that we don't need to work about priority of operations. When evaluating mathematical expressions, we must multiply and divide before we add and subtract, but how are we going to do that?
First, lets set up our tokens. All we have to do is change our generateToken function and we should be good to go.
const generateToken = value => {
let token = { value };
if (/[+\-/*]/.test(value)) token = { ...token, type: 'operator' };
if (/\d/.test(value)) token = { ...token, type: 'literal' };
return token;
};
const tokenize = (input => {
...
};
console.log(tokenize('1 + 1 / 2 * 8 + 1'));
// logs:
[
{ value: '1', type: 'literal' },
{ value: '+', type: 'operator' },
{ value: '1', type: 'literal' },
{ value: '/', type: 'operator' },
{ value: '2', type: 'literal' },
{ value: '*', type: 'operator' },
{ value: '8', type: 'literal' },
{ value: '+', type: 'operator' },
{ value: '1', type: 'literal' }
]
Super simple stuff. To evaluate our multiplications and divisions before our additions and subtractions, we are going to alter the way our parser works. What we want to do is set up different precedence levels.
const precedence = {
'+': 2,
'-': 2,
'/': 3,
'*': 3
};
These precedence levels will let us know what order we must parse our expressions. Essentially we are going to use our operatorStack to hold expressions, and only pop off certain expressions when they have a higher precedence. This way, we will build our AST in a way the higher precedence expressions are added first, so they will be evaluated first. This will work well since we won't have to change the way our evaluation occurs; we are simply moving the higher precendence expressions up higher so we evaluate them first.
const parseAST = tokens => {
const outputQueue = createASTQueue();
const operatorStack = createASTStack();
tokens.forEach(({ type, value }) => {
if (type === 'literal') outputQueue.push({ value });
if (type === 'operator') {
while(operatorStack.length && precedence[operatorStack.peek().value] >= precedence[value]) {
const op = operatorStack.pop();
outputQueue.addNode(op);
}
operatorStack.push({ type, value });
}
});
while(operatorStack.length) {
const op = operatorStack.pop();
outputQueue.addNode(op);
}
return outputQueue.pop();
}
The only real difference here is that we now peek at the operator stack and compare the values precedence with our current values precedence. While there are items with a higher precedence on the stack, pop them off and add them to our ouput queue. When that's done, push our current item on the stack. This is how we are going to evaluate our higher precendence expressions first; by putting them into the output queue earlier! The last bit is to clear out the output queue before the function is completed.
console.log(JSON.stringify(parseAST(tokenize('1 + 1 / 2 * 8 + 1')), null, 2))
// logs out:
{
"value": "+",
"left": {
"value": "+",
"left": {
"value": "1"
},
"right": {
"value": "*",
"left": {
"value": "/",
"left": {
"value": "1"
},
"right": {
"value": "2"
}
},
"right": {
"value": "8"
}
}
},
"right": {
"value": "1"
}
}
If you think about how this will get evaluated, you can see how our higher precedent expressions come first. They are deeper down the tree, and since that is where wembring values up from first those will be the first ones we get to. Notice how both of our + 1 expressions appear at the top of the tree, however they are on opposite ends of the expression we originally entered. Looks like its working well!
All we need is a slight change to our evaluator to account for our new operators and we are good to go.
const ops = {
'+': (...ops) => ops.reduce((acc, cur) => acc + cur),
'-': (...ops) => ops.reduce((acc, cur) => acc - cur),
'/': (...ops) => ops.reduce((acc, cur) => acc / cur),
'*': (...ops) => ops.reduce((acc, cur) => acc * cur),
};
That's the only change we need for this step, everything else about evaluation is the same. That's what is so nice about changing our parser to arrange things differently, that way we don't need to touch our evaluation code at all. When we run this.
console.log(evaluate(parseAST(tokenize('1 + 1 / 2 * 8 + 1')))) // 6
We start with 1 / 2 = .5, .5 * 8 = 4, 4 + 1 = 5, 1 + 5 = 6! If we hadn't implemented orders of operations, we would get 1 + 1 = 2, 2 / 2 = 1, 1 * 8 = 8, 8 + 1 = 9. It's working great! Now there are a lot of different directions you could go if you wanted to build on this. Adding in exponent, parenthesis, and functions are all great choices! Overall I hoped you enjoyed reading through my series, it was a lot of fun to write and feel like I have a great handle on how this stuff works now.