About

Incorrect operator precedence parsing is the root cause of silent calculation errors in compilers, spreadsheets, and embedded firmware. The Shunting-Yard algorithm, published by Edsger Dijkstra in 1961, resolves this by converting human-readable infix notation (e.g., 3+4×2) into unambiguous postfix (Reverse Polish Notation): 3 4 2 × +. Postfix eliminates all parentheses and precedence ambiguity because the evaluation order is encoded directly in the token sequence. This tool implements the full Shunting-Yard conversion with step-by-step tracing, then evaluates the resulting postfix expression on a simple stack machine. It is restricted to single-digit operands (0 - 9) and the operators + − × / ^, matching the d8 interpreter constraint.

Limitation: fractional and negative literal operands are not supported. Division is floating-point; division by zero returns an error rather than infinity. Exponentiation is right-associative per mathematical convention (2^3^2 evaluates as 2⁹ = 512, not 8² = 64). Pro tip: if your expression yields an unexpected result, inspect the step table to see exactly where precedence or associativity diverged from your assumption.

Formulas

The Shunting-Yard algorithm processes each token t of the infix expression left-to-right, maintaining an operator stack S and an output queue Q.

{

If t ∈ {0…9}: enqueue t → QIf t ∈ {+,−,×,/,^}: while top(S) has higher prec or equal prec & left-assoc, pop S → Q; then push t → SIf t = (: push t → SIf t = ): pop S → Q until ( found; discard (End: pop all S → Q

Postfix evaluation scans Q left-to-right. For each token: if operand, push to evaluation stack E. If operator op, pop operands b then a, compute a op b, push result. Final value remaining in E is the answer.

Operator precedence function prec(op):

prec(op) =

{

1 if op ∈ {+, −}2 if op ∈ {×, /}3 if op = ^

Where Q = output queue, S = operator stack, E = evaluation stack, t = current token, op = operator, a = first operand (left), b = second operand (right).

Reference Data

Operator	Symbol	Precedence	Associativity	Example Infix	Postfix	Result
Addition	+	1	Left	3+4	3 4 +	7
Subtraction	−	1	Left	9−5	9 5 −	4
Multiplication	×	2	Left	3×4	3 4 ×	12
Division	/	2	Left	8/2	8 2 /	4
Exponentiation	^	3	Right	2^3	2 3 ^	8
Parentheses	( )	Override	N/A	(3+4)×2	3 4 + 2 ×	14
Nested Parens	( ( ) )	Override	N/A	(1+(2×3))	1 2 3 × +	7
Right-Assoc Chain	^	3	Right	2^3^2	2 3 2 ^ ^	512
Left-Assoc Chain	−	1	Left	9−3−2	9 3 − 2 −	4
Mixed Precedence	+ × ^	1/2/3	Mixed	2+3×4^2	2 3 4 2 ^ × +	50
All Operators	All	All	Mixed	1+2×3−4/2	1 2 3 × + 4 2 / −	5
Single Operand	None	N/A	N/A	7	7	7

Frequently Asked Questions

Mathematical convention defines exponentiation as right-associative. The expression 2^3^2 groups as 2^(3²) = 2⁹ = 512. Left-associative grouping would yield (2³)² = 64. The Shunting-Yard algorithm handles this by only popping operators of strictly higher precedence (not equal) when the current operator is right-associative.

If a closing parenthesis ) is encountered but no matching ( exists on the operator stack, the algorithm reports a mismatched parenthesis error. Similarly, if after processing all tokens the stack still contains a (, the expression has unclosed parentheses. Both cases halt conversion and display a specific error message rather than producing incorrect output.

This constraint matches the d8 interpreter specification. Without whitespace delimiters in the input, multi-digit numbers become ambiguous: does 12+3 mean 12 + 3 or 1 × 2 + 3 with implicit multiplication? Single-digit restriction eliminates this parsing ambiguity entirely.

When the evaluator encounters a / operator and the top of the evaluation stack (divisor b) is 0, it immediately terminates evaluation and returns a division-by-zero error. No IEEE 754 infinity or NaN is propagated. The step trace will show exactly which operation triggered the fault.

No. The tokenizer requires an explicit operator between every operand and parenthesis. The input 2(3+4) will trigger a validation error because there is no operator between 2 and (. Write it as 2*(3+4) instead.

Both the infix-to-postfix conversion and the postfix evaluation run in O(n) time where n is the number of tokens. Each token is pushed and popped at most once across all stack operations. Space complexity is also O(n) for the operator stack and output queue.