What is the Shunting Yard Algorithm?

In the implementation of programming languages or interpreters, how to handle mathematical expressions has always been a classic problem. We want to be able to understand "infix expressions" (like 3 + 4 * 2) just like humans do, and correctly consider operator precedence and parentheses.

In 1961, Edsger Dijkstra proposed the famous Shunting Yard algorithm, which provides a mechanical way to convert infix expressions to postfix expressions (RPN) or abstract syntax trees (AST). The algorithm's name comes from railway marshalling yards: train cars are sorted by shunting between tracks, and in expression processing, we use two stacks to store and manage operands and operators. Imagine the process of calculating 3 + 4 * 2 in your head:

1. You know that multiplication has higher precedence, so you need to calculate 4 * 2 first.
2. During this process, you temporarily "remember" the preceding 3 and +.
3. Once the multiplication result is available, you add it to 3.

Dijkstra's insight is that this human thought process of "temporarily remembering something and coming back to process it" can actually be simulated using stacks. Just like railway marshalling yards temporarily park train cars on sidings and then shunt them as needed, the algorithm controls the order of operations by moving numbers and operators between different stacks. The name "Shunting Yard" comes from this railway analogy:

• Train cars are sorted by moving between tracks;
• Operators and numbers in mathematical expressions can also be correctly sorted and calculated by moving between stacks.

Dijkstra abstracted our scattered, chaotic human calculation process into a clear, mechanical workflow, allowing computers to process expressions using the same logic.

Basic Flow of the Shunting Yard Algorithm

The Shunting Yard algorithm ensures that expressions are parsed with correct precedence and associativity by maintaining two stacks:

1. Initialization

   Create two empty stacks:

   • Operator stack (op_stack), used to temporarily store unprocessed operators and parentheses;
   • Value stack (val_stack), used to store operands and partially constructed sub-expressions.

2. Scan input tokens one by one

   • If token is a number or variable: Push directly into val_stack.

   • If token is an operator:

     1. Check the top element of op_stack.
     2. If and only if the precedence of the top operator is higher than the current operator, or they have equal precedence and the top operator is left-associative, pop the top operator, combine it with two operands from val_stack to form a new sub-expression, and push it back into val_stack.
     3. Repeat this process until the condition is no longer met, then push the current operator into op_stack.

   • If token is a left parenthesis: Push into op_stack as a delimiter marker.

   • If token is a right parenthesis: Continuously pop operators from op_stack and combine them with operands from the top of val_stack to form sub-expressions, until a left parenthesis is encountered; the left parenthesis itself is discarded and does not enter val_stack.

3. Clear the operator stack

   After all tokens have been scanned, if there are still operators in op_stack, pop them one by one and combine them with operands from val_stack to form larger expressions, until the operator stack is empty.

4. End condition

   Finally, val_stack should contain only one element, which is the complete abstract syntax tree or postfix expression. If the number of elements in the stack is not one, or there are unmatched parentheses, it indicates that the input expression contains errors.

Example Walkthrough

Let's use the parsing of (1 + 2) * (3 - 4) ^ 2 as an example to demonstrate how the two stacks change during the token reading process, helping us better understand the Shunting Yard algorithm:

Step	Token Read	Operator Stack (op_stack)	Value Stack (val_stack)	Description
1	(	[(]	[]	Left parenthesis pushed into operator stack
2	1	[(]	[1]	Number pushed into value stack
3	+	[(, +]	[1]	Operator pushed into operator stack
4	2	[(, +]	[1, 2]	Number pushed into value stack
5	)	[]	[1 + 2]	Pop until left parenthesis: 1 and 2 combined into 1+2
6	*	[*]	[1 + 2]	Operator pushed into operator stack
7	(	[*, (]	[1 + 2]	Left parenthesis pushed into operator stack
8	3	[*, (]	[1 + 2, 3]	Number pushed into value stack
9	-	[*, (, -]	[1 + 2, 3]	Operator pushed into operator stack
10	4	[*, (, -]	[1 + 2, 3, 4]	Number pushed into value stack
11	)	[*]	[1 + 2, 3 - 4]	Pop until left parenthesis: 3 and 4 combined into 3-4
12	^	[*, ^]	[1 + 2, 3 - 4]	Power operator pushed into stack (right-associative, won't trigger pop)
13	2	[*, ^]	[1 + 2, 3 - 4, 2]	Number pushed into value stack
14	End of input	[]	[(1 + 2) * (3 - 4) ^ 2]	Clear operator stack: first pop ^, combine 3-4 with 2; then pop *, combine 1+2 with result

In this example, there are several noteworthy points:

• Parentheses processed first In the first group of parentheses (1 + 2), the operator + is delayed in the operator stack until a right parenthesis is encountered, then combined with 1 and 2. The second group of parentheses (3 - 4) is processed in exactly the same way.

• Precedence manifestation When * is encountered, it's pushed into the operator stack. But when the power operator ^ is encountered later, since ^ has higher precedence than * and is right-associative, it's pushed directly without triggering the pop of *.

• Role of associativity The power operator ^ is typically defined as right-associative, meaning the expression a ^ b ^ c will be parsed as a ^ (b ^ c). In this example, (3-4) ^ 2 maintains this associativity, correctly constructing the sub-expression.

• Final result After input ends, the operator stack is cleared sequentially, ultimately forming the complete expression:

(1 + 2) * ((3 - 4) ^ 2)

Implementing the Shunting Yard Algorithm in MoonBit

First, we need to define the types for expressions and tokens:

enum Expr {
  
(Int) -> Expr
Literal(
Int
Int)
  
(String, Expr, Expr) -> Expr
BinExpr(
String
String, 
enum Expr {
  Literal(Int)
  BinExpr(String, Expr, Expr)
} derive(Show)
Expr, 
enum Expr {
  Literal(Int)
  BinExpr(String, Expr, Expr)
} derive(Show)
Expr)
} derive(
trait Show {
  output(Self, &Logger) -> Unit
  to_string(Self) -> String
}
Trait for types that can be converted to String
Show)

enum Token {
  
(Int) -> Token
Literal(
Int
Int)
  
(String) -> Token
Op(
String
String)
  
Token
LeftParen
  
Token
RightParen
} derive(
trait Show {
  output(Self, &Logger) -> Unit
  to_string(Self) -> String
}
Trait for types that can be converted to String
Show)

We can leverage MoonBit's regular expression matching syntax to quickly implement a simple tokenizer:

pub fn 
(input : StringView) -> Array[Token] raise
tokenize(
StringView
input : 
type StringView
StringView) -> 
type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[
enum Token {
  Literal(Int)
  Op(String)
  LeftParen
  RightParen
} derive(Show)
Token] raise {
  let 
Array[Unit]
tokens = []
  for 
StringView
str = 
StringView
input {
    lexmatch 
StringView
str {
      "[0-9]+" as n, rest => {
        tokens.push(Token::Literal(@strconv.parse_int(n)))
        continue rest
      }
      
Unit
"[\-+*/^]" as o, rest => {
        tokens.push(Token::Op(o.to_string()))
        continue 
StringView
rest
      }
      "\(", rest => {
        tokens.push(Token::LeftParen)
        continue 
Unit
rest
      }
      "\)", rest => {
        tokens.push(Token::RightParen)
        continue rest
      }
      "[ \n\r\t]+", rest => continue rest
      "$", _ => break
      _ => fail("Invalid input")
    }
  }
  tokens
}

The tokenize function splits the input string into a series of tokens:

• Matches numbers [0-9]+ and converts them to Token::Literal;
• Matches arithmetic and power operators [-+*/^] and converts them to Token::Op;
• Matches parentheses ( and ) and converts them to LeftParen and RightParen respectively;
• Skips whitespace characters like spaces and newlines;
• Reports an error if encountering characters that don't match the rules. Through lexmatch and regular expressions, the entire tokenization process is both concise and efficient.

Next, we define a global operator table to store operator precedence and associativity:

priv enum Associativity {
  
Associativity
Left
  
Associativity
Right
}

priv struct OpInfo {
  
Int
precedence : 
Int
Int
  
Associativity
associativity : 
enum Associativity {
  Left
  Right
}
Associativity
}

let 
Map[String, OpInfo]
op_table : 
type Map[K, V]
Mutable linked hash map that maintains the order of insertion, not thread safe.
Example
  let map = { 3: "three", 8 :  "eight", 1 :  "one"}
  assert_eq(map.get(2), None)
  assert_eq(map.get(3), Some("three"))
  map.set(3, "updated")
  assert_eq(map.get(3), Some("updated"))
Map[
String
String, 
struct OpInfo {
  precedence: Int
  associativity: Associativity
}
OpInfo] = {
  "+": { 
Int
precedence: 10, 
Associativity
associativity: 
Associativity
Left },
  "-": { 
Int
precedence: 10, 
Associativity
associativity: 
Associativity
Left },
  "*": { 
Int
precedence: 20, 
Associativity
associativity: 
Associativity
Left },
  "/": { 
Int
precedence: 20, 
Associativity
associativity: 
Associativity
Left },
  "^": { 
Int
precedence: 30, 
Associativity
associativity: 
Associativity
Right },
}

Here, we define the precedence and associativity of common operators through op_table:

• + and - have the lowest precedence (10) and are left-associative;

• * and / have higher precedence (20) and are also left-associative;

• ^ (power operation) has the highest precedence (30) but is right-associative.

Next, we define a helper function to determine whether we need to process (pop) the top operator when encountering a new operator:

fn 
(top_op_info~ : OpInfo, incoming_op_info~ : OpInfo) -> Bool
should_pop(
OpInfo
top_op_info~ : 
struct OpInfo {
  precedence: Int
  associativity: Associativity
}
OpInfo, 
OpInfo
incoming_op_info~ : 
struct OpInfo {
  precedence: Int
  associativity: Associativity
}
OpInfo) -> 
Bool
Bool {
  
OpInfo
top_op_info.
Int
precedence 
(x : Int, y : Int) -> Bool
> 
OpInfo
incoming_op_info.
Int
precedence 
(Bool, Bool) -> Bool
||
  (
    
OpInfo
top_op_info.
Int
precedence 
(self : Int, other : Int) -> Bool
Compares two integers for equality.
Parameters:

self : The first integer to compare.
other : The second integer to compare.
Returns true if both integers have the same value, false otherwise.
Example:
  inspect(42 == 42, content="true")
  inspect(42 == -42, content="false")
== 
OpInfo
incoming_op_info.
Int
precedence 
(Bool, Bool) -> Bool
&&
    
OpInfo
top_op_info.
Associativity
associativity is 
Associativity
Left
  )
}

The logic of should_pop is one of the cores of the Shunting Yard algorithm:

• If the precedence of the top operator is higher than the new operator, we should process the top operator first;
• If they have equal precedence and the top operator is left-associative, we should also process the top operator first;
• Otherwise, keep the top operator and push the new operator directly into the stack.

Next, we implement the expression parsing function:

pub fn 
(tokens : Array[Token]) -> Expr
parse_expr(
Array[Token]
tokens : 
type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[
enum Token {
  Literal(Int)
  Op(String)
  LeftParen
  RightParen
} derive(Show)
Token]) -> 
enum Expr {
  Literal(Int)
  BinExpr(String, Expr, Expr)
} derive(Show)
Expr {
  let 
Array[String]
op_stack : 
type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[
String
String] = []
  let 
Array[Expr]
val_stack : 
type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[
enum Expr {
  Literal(Int)
  BinExpr(String, Expr, Expr)
} derive(Show)
Expr] = []
  fn 
(String) -> Unit
push_binary_expr(
String
top_op) {
    let 
Expr
right = 
Array[Expr]
val_stack.
(self : Array[Expr]) -> Expr?
Removes the last element from a array and returns it, or None if it is empty.
Example
  let v = [1, 2, 3]
  assert_eq(v.pop(), Some(3))
  assert_eq(v, [1, 2])
pop().
(self : Expr?) -> Expr
Extract the value in Some.
If the value is None, it throws a panic.
unwrap()
    let 
Expr
left = 
Array[Expr]
val_stack.
(self : Array[Expr]) -> Expr?
Removes the last element from a array and returns it, or None if it is empty.
Example
  let v = [1, 2, 3]
  assert_eq(v.pop(), Some(3))
  assert_eq(v, [1, 2])
pop().
(self : Expr?) -> Expr
Extract the value in Some.
If the value is None, it throws a panic.
unwrap()
    
Array[Expr]
val_stack.
(self : Array[Expr], value : Expr) -> Unit
Adds an element to the end of the array.
If the array is at capacity, it will be reallocated.
Example
  let v = []
  v.push(3)
push(Expr::
(String, Expr, Expr) -> Expr
BinExpr(
String
top_op, 
Expr
left, 
Expr
right))
  }

  for 
Token
token in 
Array[Token]
tokens {
    match 
Token
token {
      
(Int) -> Token
Literal(
Int
n) => 
Array[Expr]
val_stack.
(self : Array[Expr], value : Expr) -> Unit
Adds an element to the end of the array.
If the array is at capacity, it will be reallocated.
Example
  let v = []
  v.push(3)
push(Expr::
(Int) -> Expr
Literal(
Int
n))
      
(String) -> Token
Op(
String
incoming_op) => {
        let 
OpInfo
incoming_op_info = 
Map[String, OpInfo]
op_table
(Map[String, OpInfo], String) -> OpInfo
[incoming_op]
        while true {
          match 
Array[String]
op_stack.
(self : Array[String]) -> String?
Returns the last element of the array, or None if the array is empty.
Parameters:

array : The array to get the last element from.
Returns an optional value containing the last element of the array. The
result is None if the array is empty, or Some(x) where x is the last
element of the array.
Example:
  let arr = [1, 2, 3]
  inspect(arr.last(), content="Some(3)")
  let empty : Array[Int] = []
  inspect(empty.last(), content="None")
last() {
            
String?
None => break
            
(String) -> String?
Some(
String
top_op) =>
              if 
String
top_op 
(x : String, y : String) -> Bool
!= "(" 
(Bool, Bool) -> Bool
&&
                
(top_op_info~ : OpInfo, incoming_op_info~ : OpInfo) -> Bool
should_pop(
OpInfo
top_op_info=
Map[String, OpInfo]
op_table
(Map[String, OpInfo], String) -> OpInfo
[top_op], 
OpInfo
incoming_op_info~) {
                
Array[String]
op_stack.
(self : Array[String]) -> String?
Removes the last element from a array and returns it, or None if it is empty.
Example
  let v = [1, 2, 3]
  assert_eq(v.pop(), Some(3))
  assert_eq(v, [1, 2])
pop() |> 
(t : String?) -> Unit
Evaluates an expression and discards its result. This is useful when you want
to execute an expression for its side effects but don't care about its return
value, or when you want to explicitly indicate that a value is intentionally
unused.
Parameters:

value : The value to be ignored. Can be of any type.
Example:
  let x = 42
  ignore(x) // Explicitly ignore the value
  let mut sum = 0
  ignore([1, 2, 3].iter().each((x) => { sum = sum + x })) // Ignore the Unit return value of each()
ignore
                
(String) -> Unit
push_binary_expr(
String
top_op)
              } else {
                break
              }
          }
        }
        
Array[String]
op_stack.
(self : Array[String], value : String) -> Unit
Adds an element to the end of the array.
If the array is at capacity, it will be reallocated.
Example
  let v = []
  v.push(3)
push(
String
incoming_op)
      }
      
Token
LeftParen => 
Array[String]
op_stack.
(self : Array[String], value : String) -> Unit
Adds an element to the end of the array.
If the array is at capacity, it will be reallocated.
Example
  let v = []
  v.push(3)
push("(")
      
Token
RightParen =>
        while 
Array[String]
op_stack.
(self : Array[String]) -> String?
Removes the last element from a array and returns it, or None if it is empty.
Example
  let v = [1, 2, 3]
  assert_eq(v.pop(), Some(3))
  assert_eq(v, [1, 2])
pop() is 
(String) -> String?
Some(
String
top_op) {
          if 
String
top_op 
(x : String, y : String) -> Bool
!= "(" {
            
(String) -> Unit
push_binary_expr(
String
top_op)
          } else {
            break
          }
        }
    }
  }
  while 
Array[String]
op_stack.
(self : Array[String]) -> String?
Removes the last element from a array and returns it, or None if it is empty.
Example
  let v = [1, 2, 3]
  assert_eq(v.pop(), Some(3))
  assert_eq(v, [1, 2])
pop() is 
(String) -> String?
Some(
String
top_op) {
    
(String) -> Unit
push_binary_expr(
String
top_op)
  }
  
Array[Expr]
val_stack.
(self : Array[Expr]) -> Expr?
Removes the last element from a array and returns it, or None if it is empty.
Example
  let v = [1, 2, 3]
  assert_eq(v.pop(), Some(3))
  assert_eq(v, [1, 2])
pop().
(self : Expr?) -> Expr
Extract the value in Some.
If the value is None, it throws a panic.
unwrap()
}

parse_expr is the core implementation of the entire Shunting Yard algorithm:

1. Data structure preparation

   • op_stack stores operators and parentheses;
   • val_stack stores operands or partially constructed sub-expressions;
   • The internal function push_binary_expr encapsulates a small step: pop two operands from the value stack, combine them with an operator, generate a new BinExpr node, and push it back into the value stack.

2. Iterate through tokens

   • Numbers: Push directly into val_stack.
   • Operators: Continuously check the top operator in op_stack, if it has higher precedence or needs to be calculated first, pop it and construct a sub-expression; when the condition is no longer met, push the new operator into the stack.
   • Left parenthesis: Push into op_stack to separate sub-expressions.
   • Right parenthesis: Continuously pop operators and combine them with operands from the value stack to form sub-expressions, until a matching left parenthesis is encountered.

3. Clear the operator stack

   After iteration is complete, there may still be operators remaining in op_stack, which need to be popped one by one and combined with operands from the value stack until the operator stack is empty.

4. Return result

   Finally, the value stack should contain only one element, which is the complete abstract syntax tree. If this is not the case, it indicates that the input expression contains syntax errors.

Finally, we can define a simple eval function for testing:

pub fn 
(expr : Expr) -> Int
eval(
Expr
expr : 
enum Expr {
  Literal(Int)
  BinExpr(String, Expr, Expr)
} derive(Show)
Expr) -> 
Int
Int {
  match 
Expr
expr {
    
(Int) -> Expr
Literal(
Int
n) => 
Int
n
    
(String, Expr, Expr) -> Expr
BinExpr(
String
op, 
Expr
left, 
Expr
right) =>
      match 
String
op {
        "+" => 
(expr : Expr) -> Int
eval(
Expr
left) 
(self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
  inspect(42 + 1, content="43")
  inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ 
(expr : Expr) -> Int
eval(
Expr
right)
        "-" => 
(expr : Expr) -> Int
eval(
Expr
left) 
(self : Int, other : Int) -> Int
Performs subtraction between two 32-bit integers, following standard two's
complement arithmetic rules. When the result overflows or underflows, it
wraps around within the 32-bit integer range.
Parameters:

self : The minuend (the number being subtracted from).
other : The subtrahend (the number to subtract).
Returns the difference between self and other.
Example:
  let a = 42
  let b = 10
  inspect(a - b, content="32")
  let max = 2147483647 // Int maximum value
  inspect(max - -1, content="-2147483648") // Overflow case
- 
(expr : Expr) -> Int
eval(
Expr
right)
        "*" => 
(expr : Expr) -> Int
eval(
Expr
left) 
(self : Int, other : Int) -> Int
Multiplies two 32-bit integers. This is the implementation of the *
operator for Int.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns the product of the two integers. If the result overflows the range of
Int, it wraps around according to two's complement arithmetic.
Example:
  inspect(42 * 2, content="84")
  inspect(-10 * 3, content="-30")
  let max = 2147483647 // Int.max_value
  inspect(max * 2, content="-2") // Overflow wraps around
* 
(expr : Expr) -> Int
eval(
Expr
right)
        "/" => 
(expr : Expr) -> Int
eval(
Expr
left) 
(self : Int, other : Int) -> Int
Performs integer division between two 32-bit integers. The result is
truncated towards zero (rounds down for positive numbers and up for negative
numbers).
Parameters:

dividend : The first integer operand to be divided.
divisor : The second integer operand that divides the dividend.
Returns the quotient of the division operation.
Throws a panic if divisor is zero.
Example:
  inspect(10 / 3, content="3") // truncates towards zero
  inspect(-10 / 3, content="-3")
  inspect(10 / -3, content="-3")
/ 
(expr : Expr) -> Int
eval(
Expr
right)
        "^" => {
          fn 
(Int, Int) -> Int
pow(
Int
base : 
Int
Int, 
Int
exp : 
Int
Int) -> 
Int
Int {
            if 
Int
exp 
(self : Int, other : Int) -> Bool
Compares two integers for equality.
Parameters:

self : The first integer to compare.
other : The second integer to compare.
Returns true if both integers have the same value, false otherwise.
Example:
  inspect(42 == 42, content="true")
  inspect(42 == -42, content="false")
== 0 {
              1
            } else {
              
Int
base 
(self : Int, other : Int) -> Int
Multiplies two 32-bit integers. This is the implementation of the *
operator for Int.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns the product of the two integers. If the result overflows the range of
Int, it wraps around according to two's complement arithmetic.
Example:
  inspect(42 * 2, content="84")
  inspect(-10 * 3, content="-30")
  let max = 2147483647 // Int.max_value
  inspect(max * 2, content="-2") // Overflow wraps around
* 
(Int, Int) -> Int
pow(
Int
base, 
Int
exp 
(self : Int, other : Int) -> Int
Performs subtraction between two 32-bit integers, following standard two's
complement arithmetic rules. When the result overflows or underflows, it
wraps around within the 32-bit integer range.
Parameters:

self : The minuend (the number being subtracted from).
other : The subtrahend (the number to subtract).
Returns the difference between self and other.
Example:
  let a = 42
  let b = 10
  inspect(a - b, content="32")
  let max = 2147483647 // Int maximum value
  inspect(max - -1, content="-2147483648") // Overflow case
- 1)
            }
          }

          
(Int, Int) -> Int
pow(
(expr : Expr) -> Int
eval(
Expr
left), 
(expr : Expr) -> Int
eval(
Expr
right))
        }
        _ => 
(msg : String) -> Int
Aborts the program with an error message. Always causes a panic, regardless
of the message provided.
Parameters:

message : A string containing the error message to be displayed when
aborting.
Returns a value of type T. However, this function never actually returns a
value as it always causes a panic.
abort("Invalid operator")
      }
  }
}

///|
pub fn 
(input : String) -> Int raise
parse_and_eval(
String
input : 
String
String) -> 
Int
Int raise {
  
(expr : Expr) -> Int
eval(
(tokens : Array[Token]) -> Expr
parse_expr(
(input : StringView) -> Array[Token] raise
tokenize(
String
input)))
}

And verify our implementation with some simple test cases:

test "parse_and_eval" {
  
(obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect(
(input : String) -> Int raise
parse_and_eval("1 + 2 * 3"), 
String
content="7")
  
(obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect(
(input : String) -> Int raise
parse_and_eval("2 ^ 3 ^ 2"), 
String
content="512")
  
(obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect(
(input : String) -> Int raise
parse_and_eval("(2 ^ 3) ^ 2"), 
String
content="64")
  
(obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect(
(input : String) -> Int raise
parse_and_eval("(1 + 2) * 3"), 
String
content="9")
  
(obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect(
(input : String) -> Int raise
parse_and_eval("10 - (3 + 2)"), 
String
content="5")
  
(obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect(
(input : String) -> Int raise
parse_and_eval("2 * (3 + 4)"), 
String
content="14")
  
(obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect(
(input : String) -> Int raise
parse_and_eval("(5 + 3) / 2"), 
String
content="4")
  
(obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect(
(input : String) -> Int raise
parse_and_eval("10 / 2 - 1"), 
String
content="4")
  
(obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect(
(input : String) -> Int raise
parse_and_eval("1 + 2 + 3"), 
String
content="6")
  
(obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect(
(input : String) -> Int raise
parse_and_eval("10 - 5 - 2"), 
String
content="3")
  
(obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect(
(input : String) -> Int raise
parse_and_eval("5"), 
String
content="5")
  
(obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect(
(input : String) -> Int raise
parse_and_eval("(1 + 2) * (3 + 4)"), 
String
content="21")
  
(obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect(
(input : String) -> Int raise
parse_and_eval("2 ^ (1 + 2)"), 
String
content="8")
  
(obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect(
(input : String) -> Int raise
parse_and_eval("1 + 2 * 3 - 4 / 2 + 5"), 
String
content="10")
  
(obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect(
(input : String) -> Int raise
parse_and_eval("((1 + 2) * 3) ^ 2 - 10"), 
String
content="71")
  
(obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect(
(input : String) -> Int raise
parse_and_eval("100 / (2 * 5) + 3 * (4 - 1)"), 
String
content="19")
  
(obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect(
(input : String) -> Int raise
parse_and_eval("2 ^ 2 * 3 + 1"), 
String
content="13")
  
(obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect(
(input : String) -> Int raise
parse_and_eval("1 + 2 * 3 ^ 2 - 4 / 2"), 
String
content="17")
}

Summary

The core idea of the Shunting Yard algorithm lies in using two stacks to explicitly manage the computation process:

• Value stack (val_stack) is used to store numbers and partially combined sub-expressions;
• Operator stack (op_stack) is used to store unprocessed operators and parentheses.

By defining operator precedence and associativity, and continuously comparing and popping top operators during token scanning, the Shunting Yard algorithm ensures that expressions are combined into abstract syntax trees (AST) in the correct order. Finally, when all tokens have been read and the operator stack is cleared, what remains in the value stack is the complete expression tree.

This method intuitively simulates our manual calculation approach: first "remember" content that cannot be calculated immediately, then retrieve and process it when conditions are appropriate. Its process is clear and implementation is concise, making it very suitable as a starting point for learning expression parsing.

Previously, MoonBit Pearl published an article introducing Pratt parsing. Both are classic methods for solving "how to correctly parse expression precedence and associativity," but their approaches are completely different. Shunting Yard uses loops and explicit data structures, managing unprocessed symbols and partial sub-expressions through operator and value stacks. The entire process is like manually manipulating two stacks, with clear logic that's easy to track. Pratt Parser, on the other hand, is based on recursive descent, where each token defines parsing methods in different contexts, and parsing progress depends on the language runtime's call stack: each recursive call is equivalent to pushing unfinished state onto the stack, then continuing to combine when returning. In other words, Pratt Parser hides the existence of the "stack" within recursive calls, while Shunting Yard makes this state management explicit, directly simulating it with loops and data structures. Therefore, it can be considered that Shunting Yard is a transcription of the mechanisms implicit in Pratt Parser's call stack into explicit stack operations. The former is mechanical in steps, suitable for quickly implementing fixed operator parsing; the latter is more flexible, especially more natural when handling prefix, postfix, or custom operators.