Evaluating Math Expressions with the Shunting Yard Algorithm
Greetings, friends! This is my fourth post in the math expression parser series. In this tutorial, we'll learn how to build a math expression evaluator using the Shunting yard algorithm that works directly on standard infix notation.
Introduction
In the previous tutorial, we built an implementation of the Shunting Yard algorithm to convert infix form to RPN/postfix form and then fed that into an RPN evaluator to evaluate the math expression. In this tutorial, we'll skip the RPN conversion step and directly evaluate infix expressions using a modified version of the Shunting Yard algorithm we built in the previous tutorial.
The math expression evaluator we build in this tutorial will still only be able to calculate math expressions with one-digit numbers. In the next tutorial, we'll finally build a tokenizer, so we can calculate math expressions with numbers that have multiple digits.
Revisiting the Implementation
Let's revisit the Shunting Yard algorithm implementation we learned about in the previous tutorial. As you may recall, we cleaned up the code at the very end of the tutorial and added a few utility functions: peek, addToOutput, and handlePop.
const operators = {
'^': {
prec: 4,
assoc: 'right',
},
'*': {
prec: 3,
assoc: 'left',
},
'/': {
prec: 3,
assoc: 'left',
},
'+': {
prec: 2,
assoc: 'left',
},
'-': {
prec: 2,
assoc: 'left',
},
};
const assert = (predicate) => {
if (predicate) return;
throw new Error('Assertion failed due to invalid token');
};
const toRPN = (input) => {
const opSymbols = Object.keys(operators);
const stack = [];
let output = '';
const peek = () => {
return stack.at(-1);
};
const addToOutput = (token) => {
output += ' ' + token;
};
const handlePop = () => {
return stack.pop();
}
const handleToken = (token) => {
switch (true) {
case !isNaN(parseFloat(token)):
addToOutput(token);
break;
case opSymbols.includes(token):
const o1 = token;
let o2 = peek();
while (
o2 !== undefined &&
o2 !== '(' &&
(operators[o2].prec > operators[o1].prec ||
(operators[o2].prec === operators[o1].prec &&
operators[o1].assoc === 'left'))
) {
addToOutput(handlePop());
o2 = peek();
}
stack.push(o1);
break;
case token === '(':
stack.push(token);
break;
case token === ')':
let topOfStack = peek();
while (topOfStack !== '(') {
assert(stack.length !== 0);
addToOutput(handlePop());
topOfStack = peek();
}
assert(peek() === '(');
handlePop();
break;
default:
throw new Error(`Invalid token: ${token}`);
}
};
for (let i of input) {
if (i === ' ') continue;
handleToken(i);
}
while (stack.length !== 0) {
assert(peek() !== '(');
addToOutput(stack.pop());
}
return output;
};
const input = '1 + 2 * 3 - 4'
const result = toRPN(input);
console.log(result); // 1 2 3 * + 4 -
We made a function called toRPN that implements the Shunting yard algorithm and converts a math expression from infix notation to RPN/postfix notation. We could then feed the RPN/postfix form of the expression into our RPNEvaluate function we built a couple tutorials ago. Well, it's time to say goodbye to that function because we won't need it anymore!
Modifying the Algorithm
We were evaluating math expressions after the Shunting yard algorithm finished. Now, it's time to modify the function, so that we evaluate math expressions during the algorithm. This only requires a few modifications!
First, let's rename the toRPN function to evaluate, since we're no longer converting an expression to RPN/postfix form. We're evaluating a math expression on the fly.
The stack.pop method can be thought of as a special action that takes place as we parse the math expression. I intentionally made a function called handlePop because this is where code will run every time the stack.pop action occurs.
const handlePop = () => {
return stack.pop();
}
Every time we popped a value from the stack, we were adding it to the output string in the handleToken function. What if we did something different when a "pop" event happens? Instead of adding a value to the string, let's evaluate a mathematical operation on the fly.
We'll change the output variable to be an empty array instead instead of a string.
let output = [];
We'll also change the addToOutput function to account for the change in type (from string to array).
const addToOutput = (token) => {
output.push(token);
};
The idea is that we're no longer appending tokens to a string. We will use an array to hold the numbers in our mathematical expression and then evaluate them once we reach a "pop" action. Therefore, we need to heavily modify our handlePop method.
const handlePop = () => {
const op = stack.pop();
if (op === '(') return;
const right = parseFloat(output.pop());
const left = parseFloat(output.pop());
switch (op) {
case '+':
return left + right;
case '-':
return left - right;
case '*':
return left * right;
case '/':
return left / right;
case '^':
return left ** right;
default:
throw new Error(`Invalid operation: ${op}`);
}
};
Does this code look familiar? Most of the code is the same code and arithmetic logic we used in the RPNEvaluator function we built a couple tutorials ago!
Finally, we need to modify the return value inside the evaluate (previously named toRPN) function to return the first element of the output array. Once the input is completely parsed, we are left with one value in the array, the final result of the mathematical expression.
return output[0];
Finished Code for the Shunting Yard Evaluator
Now that our modifications are complete, let's take a look at the finished code of the modified implementation of the Shunting yard algorithm. Remember, we renamed the toRPN function to evaluate because we're no longer converting an expression to RPN/postfix form. We're evaluating a math expression and returning the result.
const operators = {
'^': {
prec: 4,
assoc: 'right',
},
'*': {
prec: 3,
assoc: 'left',
},
'/': {
prec: 3,
assoc: 'left',
},
'+': {
prec: 2,
assoc: 'left',
},
'-': {
prec: 2,
assoc: 'left',
},
};
const assert = (predicate) => {
if (predicate) return;
throw new Error('Assertion failed due to invalid token');
};
const evaluate = (input) => {
const opSymbols = Object.keys(operators);
const stack = [];
let output = [];
const peek = () => {
return stack.at(-1);
};
const addToOutput = (token) => {
output.push(token);
};
const handlePop = () => {
const op = stack.pop();
if (op === '(') return;
const right = parseFloat(output.pop());
const left = parseFloat(output.pop());
switch (op) {
case '+':
return left + right;
case '-':
return left - right;
case '*':
return left * right;
case '/':
return left / right;
case '^':
return left ** right;
default:
throw new Error(`Invalid operation: ${op}`);
}
};
const handleToken = (token) => {
switch (true) {
case !isNaN(parseFloat(token)):
addToOutput(token);
break;
case opSymbols.includes(token):
const o1 = token;
let o2 = peek();
while (
o2 !== undefined &&
o2 !== '(' &&
(operators[o2].prec > operators[o1].prec ||
(operators[o2].prec === operators[o1].prec &&
operators[o1].assoc === 'left'))
) {
addToOutput(handlePop());
o2 = peek();
}
stack.push(o1);
break;
case token === '(':
stack.push(token);
break;
case token === ')':
let topOfStack = peek();
while (topOfStack !== '(') {
assert(stack.length !== 0);
addToOutput(handlePop());
topOfStack = peek();
}
assert(peek() === '(');
handlePop();
break;
default:
throw new Error(`Invalid token: ${token}`);
}
};
for (let i of input) {
if (i === ' ') continue;
handleToken(i);
}
while (stack.length !== 0) {
assert(peek() !== '(');
addToOutput(handlePop());
}
return output[0];
};
const input = '1 + 2 * 3 - 4';
const result = evaluate(input);
console.log(result); // 3
Conclusion
Congrats! You have now built a math expression parser and evaluator! For real this time! 🎉
You can now evaluate mathematical expressions that are provided to you in infix notation. However, there's still one important thing we need to add to our parser and evaluator. Our calculator only works with one-digit numbers...
In the next tutorial, we'll finally build a tokenizer! Then, we'll be able to use numbers that have multiple digits!