Skip to content Search Apps Documentation Source Content Run Reset Eval Playground File Folder Download Copy Actions State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

Community realm. Read the code first. Community realm, deployed by its author. Read the code before you interact or send coins.

Shunting-yard

Dijkstra's 1961 algorithm, demoing the p/moul/x/daily/shuntingyard library: an infix expression becomes reverse Polish notation in one left-to-right pass, with one stack and no recursion, and the RPN evaluates with one more stack.

Worked examples

expression RPN value why it is here
2+3*4 2 3 4 * + 14 multiplication binds tighter
(2+3)*4 2 3 + 4 * 20 parentheses beat precedence
10-3-2 10 3 - 2 - 5 subtraction associates left
2^3^2 2 3 2 ^ ^ 512 but power associates right
-3^2 3 2 ^ u- -9 a prefix minus binds looser than a power
3*-2 3 2 u- * -6 the same byte, now unary, after an operator
-7/2 7 u- 2 / -3 integer division truncates toward zero
-7%2 7 u- 2 % -1 and the remainder keeps the dividend's sign

Every cell above is computed by the library at render time. The RPN column is the whole output of the conversion: an expression that groups surprisingly groups visibly.

The precedence table is the parser

Grouping is data here, not control flow. These eight rows are the only thing that decides how an expression reads, which is why adding an operator is a row rather than a branch.

operator precedence associativity arity
+ 1 left binary
- 1 left binary
* 2 left binary
/ 2 left binary
% 2 left binary
u- 3 right unary prefix
u+ 3 right unary prefix
^ 4 right binary

u- and u+ are the prefix forms. They are separate operators rather than a flag on - and + because they take one operand instead of two and sit at a different precedence, and conflating the two is how a parser ends up reading -3^2 as 9.

What it refuses

None of these panics. A realm that evaluates a stored expression inside Render cannot be made permanently unreadable by one bad input, and an expression that would wrap int64 says so instead of returning a plausible wrong amount.

expression error
1/0 shuntingyard: division by zero
2^-1 shuntingyard: negative exponent
9223372036854775807+1 shuntingyard: int64 overflow
2^64 shuntingyard: int64 overflow
1 2 shuntingyard: unexpected number at offset 2
(1 shuntingyard: unbalanced "(" at offset 0
1$2 shuntingyard: unexpected character "$" at offset 1

Try one

2+3*4 · (2+3)*4 · 10-3-2 · 2^3^2 · -3^2 · 3*-2 · -7/2 · -7%2

Or append your own: ?e=2*(3+4).