Implementing the Shunting Yard algorithm in JavaScript
Following on from my recent post on implementing a small RPN parser using JavaScript, we can expand on this by handling infix expressions. This can be achieved by initially parsing the expression into its postfix (RPN) counterpart, highlighting another use case where a stack-based approach works well. Looping over each token, we either push the token to the output if it is numeric, pop from the operator stack based on precedence if it is an operator, or handle brackets accordingly. You can find a more in-depth description of the algorithm, using Java as the example language, in a previous post.
let yard = infix => {
let ops = { '+': 1, '-': 1, '*': 2, '/': 2 };
let peek = a => a[a.length - 1];
let stack = [];
return infix
.split('')
.reduce((output, token) => {
if (parseFloat(token)) {
output.push(token);
}
if (token in ops) {
while (peek(stack) in ops && ops[token] <= ops[peek(stack)])
output.push(stack.pop());
stack.push(token);
}
if (token == '(') {
stack.push(token);
}
if (token == ')') {
while (peek(stack) != '(') output.push(stack.pop());
stack.pop();
}
return output;
}, [])
.concat(stack.reverse())
.join(' ');
};
yard('3 + 4 * 5 / (3 + 2)'); // 3 4 5 * 3 2 + / +
rpn(yard('3 + 4 * 5 / (3 + 2)')); // 7