Pattern Reference
Expression Parsing
"Shunting yard, recursive descent, prefix/postfix conversion, basic calculator."
Loading...
Deep Dive Tutorial
The two-stack algorithm: maintain a values stack and an operators stack. When current operator has lower or equal precedence than stack top, pop and apply. This implements the Shunting-Yard algorithm inline. For complex grammars with multiple precedence levels, recursive descent is cleaner: expr() calls term() which calls factor(), mirroring the grammar rules.
Two-stack expression evaluator
function evaluate(s) {
const vals = [], ops = [];
const prec = {'+': 1, '-': 1, '*': 2, '/': 2};
const apply = () => {
const b = vals.pop(), a = vals.pop(), op = ops.pop();
if (op === '+') vals.push(a + b);
else if (op === '-') vals.push(a - b);
else if (op === '*') vals.push(a * b);
else vals.push(Math.trunc(a / b));
};
let i = 0;
while (i < s.length) {
const c = s[i];
if (c === ' ') { i++; continue; }
if (c >= '0' && c <= '9') {
let num = 0;
while (i < s.length && s[i] >= '0' && s[i] <= '9') num = num * 10 + +s[i++];
vals.push(num);
} else if (c === '(') { ops.push(c); i++; }
else if (c === ')') {
while (ops.at(-1) !== '(') apply();
ops.pop(); i++;
} else { // operator
while (ops.length && ops.at(-1) !== '(' && prec[ops.at(-1)] >= prec[c]) apply();
ops.push(c); i++;
}
}
while (ops.length) apply();
return vals[0];
}Worked Problems
calculator
Expression parsing approaches:
- Two-stack (Shunting-Yard inline): O(n), handles precedence via stack comparison
- Recursive descent: each function = one grammar rule, easiest to extend
- Postfix (RPN): no precedence needed, simple stack evaluation
Two-stack rules:
- Number: push to value stack
- Operator: pop and apply while stack operator has higher/equal precedence
- '(': push to op stack
- ')': pop and apply until '(' found
When to use recursive descent: Multiple operators, unary operators, or complex grammar. Structure: expr → term (('+'/'-') term)*; term → factor (('*'/'/') factor)*; factor → number | '(' expr ')'.
- Two-stack (Shunting-Yard inline): O(n), handles precedence via stack comparison
- Recursive descent: each function = one grammar rule, easiest to extend
- Postfix (RPN): no precedence needed, simple stack evaluation
Two-stack rules:
- Number: push to value stack
- Operator: pop and apply while stack operator has higher/equal precedence
- '(': push to op stack
- ')': pop and apply until '(' found
When to use recursive descent: Multiple operators, unary operators, or complex grammar. Structure: expr → term (('+'/'-') term)*; term → factor (('*'/'/') factor)*; factor → number | '(' expr ')'.