Skip to content Search Apps Documentation Source Content 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.

v0 source pure

Package shuntingyard turns an infix arithmetic expression into reverse Polish notation and evaluates it over int64, w...

Readme View source

gno.land/p/moul/x/daily/shuntingyard/v0

Infix arithmetic to reverse Polish notation, and back to a number: Tokenize, ToRPN, EvalRPN, Eval, FormatRPN, Operators.

 1import "gno.land/p/moul/x/daily/shuntingyard/v0"
 2
 3shuntingyard.Eval("2+3*4")        // 14, nil
 4shuntingyard.Eval("-3^2")         // -9, nil        a prefix minus binds looser than ^
 5shuntingyard.Eval("1/0")          // 0, ErrDivByZero
 6shuntingyard.Eval("2^64")         // 0, ErrOverflow
 7
 8toks, _ := shuntingyard.Tokenize("(2+3)*4")
 9rpn, _ := shuntingyard.ToRPN(toks)
10shuntingyard.FormatRPN(rpn)       // "2 3 + 4 *"

A realm that wants to take a formula from a caller has two bad options and this one. Hard-coding the arithmetic means a new package path for every new formula, and a public path can never be redeployed. Accepting a pre-built RPN string pushes the parsing onto whoever is sending the transaction, who then has to be trusted to have parsed it the same way the realm would have. Parsing infix on chain keeps the formula a piece of data and the meaning a piece of code.

Every arithmetic result is checked, deliberately. An expression that would wrap int64 returns ErrOverflow rather than a plausible wrong number. The usual reason to evaluate a caller's formula is to compute an amount, and a wrapped amount is indistinguishable from a correct one until it is spent.

Four behaviours worth knowing before you use it:

  • Nothing panics. Every refusal is an error value, including a malformed expression, an overflow and a division by zero. A Render that evaluates a stored expression therefore cannot be made permanently unreadable by one bad input, which matters because the page cannot be redeployed to fix it.
  • The prefix minus is its own operator, u-. It takes one operand and sits below ^ in the precedence table, so -3^2 is -9 and not 9. Treating it as a flag on binary - is the classic way to get that wrong, and the RPN is where it becomes visible: 3 2 ^ u-, never 3 u- 2 ^.
  • Parsing and evaluation are separate passes. ToRPN answers whether an expression is well formed; the RPN it returns is a bounded program a realm can store and re-run without parsing again. EvalRPN re-validates what it is given rather than trusting it, because by the time a stored program is read back it is an input like any other.
  • Integers only, and division truncates toward zero. -7/2 is -3 and -7%2 is -1. There is no float type worth having on chain: a Render has to be byte-identical on every validating node, and that is exactly what floating point does not promise. A caller who needs a fraction scales by a power of ten and divides at the end.

Syntax errors carry the byte offset where the problem was noticed (shuntingyard: unexpected number at offset 2), so a realm can point at the character rather than reporting that something, somewhere, was wrong.

MaxTokens caps an expression at 1024 tokens. Evaluation is linear in the token count, so the cap is not about time: it is there so a caller cannot size the two stacks from unbounded input and make the allocation itself the attack.

The operator set is + - * / % ^, parentheses, and the two prefix forms. There are no variables, no functions and no floats. Adding an operator is a row in operators, which Operators() hands out as a copy.

Live demo: r/moul/x/daily/shuntingyarddemo.

Part of moul/gno-contracts — moul's versioned gno.land contracts. See the repository for the full catalog, build/test tooling, and usage.

🧪 Highly experimental — potentially vibe-coded. Not audited; may break, change, or be removed at any time. Do not use with anything of value. Full disclaimer: DISCLAIMER.

Overview

Package shuntingyard turns an infix arithmetic expression into reverse Polish notation and evaluates it over int64, with Dijkstra's shunting-yard algorithm (1961).

A realm that wants to take a formula from a caller has two bad options and this one. Hard-coding the arithmetic means a new package path for every new formula, and a public path can never be redeployed. Accepting a pre-built RPN string pushes the parsing onto whoever is sending the transaction, who then has to be trusted to have parsed it the same way. Parsing infix on chain keeps the formula a piece of data and the meaning a piece of code.

Three properties make it usable for that rather than only interesting:

  • Every arithmetic result is checked. An expression that would wrap int64 returns ErrOverflow instead of a plausible wrong number, which matters because the usual reason to evaluate a caller's formula is to compute an amount.
  • Nothing panics. Every refusal is an error value, so a Render that evaluates a stored expression cannot be made permanently unreadable by one bad input.
  • Parsing and evaluation are separate. ToRPN answers whether an expression is well formed, and the RPN it returns is a bounded program a realm can store and re-run without parsing it again.

Integers only, deliberately: see the package README.

A live demo of this package is at r/moul/x/daily/shuntingyarddemo(/r/moul/x/daily/shuntingyarddemo/v0).

Constants 3

const OpAdd, OpSub, OpMul, OpDiv, OpMod, OpPow, OpNeg, OpPos 

 1const (
 2	OpAdd = "+"
 3	OpSub = "-"
 4	OpMul = "*"
 5	OpDiv = "/"
 6	OpMod = "%"
 7	OpPow = "^"
 8	OpNeg = "u-"
 9	OpPos = "u+"
10)
source

Operator spellings, as they appear in a Token. The two unary forms are separate operators rather than a flag, because a prefix minus and a binary minus have different arities and different precedence, and conflating them is the classic way a shunting-yard implementation evaluates -3^2 as 9.

const MaxTokens 

1const MaxTokens = 1024
source

MaxTokens bounds how long an expression may be, so a caller cannot size the two stacks from unbounded input and make the allocation itself the attack. It is a token count, not a byte count: whitespace and long literals are free.

Variables 1

var ErrDivByZero, ErrOverflow, ErrNegExponent, ErrTooLong, ErrMalformedRPN 

1var (
2	ErrDivByZero    = errors.New("shuntingyard: division by zero")
3	ErrOverflow     = errors.New("shuntingyard: int64 overflow")
4	ErrNegExponent  = errors.New("shuntingyard: negative exponent")
5	ErrTooLong      = errors.New("shuntingyard: too many tokens")
6	ErrMalformedRPN = errors.New("shuntingyard: malformed RPN")
7)
source

Evaluation failures. Each one is a value rather than a panic: see the package doc.

Functions 6

func Eval 

1func Eval(src string) (int64, error)
source

Eval tokenizes, converts and evaluates an infix expression in one call.

func EvalRPN 

1func EvalRPN(rpn []Token) (int64, error)
source

EvalRPN evaluates a reverse Polish token stream over int64.

It re-checks everything ToRPN guarantees, because the RPN is the part a realm would store and re-run, and a stored program is an input like any other by the time it is read back.

func FormatRPN 

1func FormatRPN(toks []Token) string
source

FormatRPN renders a token stream space-separated, the usual way RPN is written down.

func Operators 

1func Operators() []OpInfo
source

Operators returns the precedence table, lowest precedence first. The slice is a copy: a caller rendering it must not be able to reorder the parser.

func ToRPN 

1func ToRPN(in []Token) ([]Token, error)
source

ToRPN converts an infix token stream to reverse Polish notation, rejecting anything that is not a well-formed expression.

The validity check is one bit of state: whether an operand or an operator is expected next. That single bit is what rejects "1 2", "1+" and "()", and it costs nothing on top of the conversion the function is doing anyway.

func Tokenize 

1func Tokenize(src string) ([]Token, error)
source

Tokenize splits an infix expression into tokens, resolving a leading '+' or '-' to its unary form (OpPos, OpNeg) from what came before it.

It validates characters and literals only. Whether the tokens form an expression is ToRPN's question, because that is the pass that knows what may follow what.

Types 4

type OpInfo

struct 
1type OpInfo struct {
2	Op    string
3	Prec  int
4	Right bool
5	Unary bool
6}
source

OpInfo describes one operator: its precedence, whether it associates to the right, and whether it is the prefix unary form.

type SyntaxError

struct 
1type SyntaxError struct {
2	Pos int
3	Msg string
4}
source

SyntaxError is returned by Tokenize and ToRPN. Pos is the byte offset in the source where the problem was noticed, so a caller can point at it.

Methods on SyntaxError

func Error

method on SyntaxError 
1func (e *SyntaxError) Error() string
source

Error implements the error interface.

type Token

struct 
1type Token struct {
2	Kind Kind
3	Num  int64
4	Op   string
5	Pos  int
6}
source

Token is one lexical unit of an expression. Num is meaningful only for KindNumber and Op only for KindOperator. Pos is the byte offset the token started at, kept so an error can name a place rather than a symbol.

Methods on Token

func String

method on Token 
1func (t Token) String() string
source

String renders a token the way it is written in an expression, which is also how FormatRPN prints it.

Dependencies

Imports 4

/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/daily/shuntingyard/v0

Imported by indexer

Find the packages that import it

Source Files 4