什么是 Shunting Yard 算法？

在编程语言或解释器的实现中，如何处理数学表达式一直是一个经典问题。我们希望能够像人一样理解“中缀表达式”（如 3 + 4 * 2），并正确考虑运算符优先级与括号。

1961 年，Edsger Dijkstra 提出了著名的 Shunting Yard 算法，它提供了一种机械化的方式来将中缀表达式转换为后缀表达式（RPN）或抽象语法树（AST）。算法的名字来源于铁路编组场：火车车厢通过在轨道之间来回调度实现排序，而在表达式处理中，我们通过两个栈来存储和调度操作数与操作符。想象一下你在脑子里计算 3 + 4 * 2 的过程：

1. 你知道乘法优先级更高，所以要先算 4 * 2。
2. 在此过程中，你会把前面的 3 和 + 临时“记在心里”。
3. 等乘法结果出来，再把它和 3 相加。

Dijkstra 的洞见在于：这种人类计算时“临时记住某些东西再回来处理”的思维过程，其实可以用栈（stack）来模拟。就像铁路编组场会把火车车厢先临时停放在侧轨，再根据需要调度一样，算法通过把数字和运算符在不同的栈之间移动，来实现对运算顺序的控制。“Shunting Yard”（调度场算法）的名字正是来自这种铁路类比：

• 火车车厢通过在轨道间移动来完成排序；
• 数学表达式中的运算符和数字，也可以通过在栈之间移动来完成正确的排序与计算。

Dijkstra 把我们人类零散、混乱的计算过程，抽象成了一个清晰、机械化的流程，让计算机也能按照同样的逻辑来处理算式。

Shunting Yard 算法的基本流程

Shunting Yard 算法通过维护两个栈来保证表达式按照正确的优先级和结合性进行解析：

1. 初始化

   建立两个空栈：

   • 运算符栈（op_stack），用于临时存放尚未处理的运算符和括号；
   • 值栈（val_stack），用于存放操作数以及已经构造好的部分子表达式。

2. 逐一扫描输入 token

   • 若 token 为数字或变量：直接压入 val_stack。

   • 若 token 为运算符：

     1. 检查 op_stack 栈顶元素。
     2. 当且仅当栈顶运算符的优先级高于当前运算符，或优先级相等且为左结合时，将该栈顶运算符弹出，并结合 val_stack 中的两个操作数，合成一个新的子表达式，再压回 val_stack。
     3. 重复此过程，直到不满足条件为止，然后将当前运算符压入 op_stack。

   • 若 token 为左括号：压入 op_stack，作为分界标记。

   • 若 token 为右括号：不断从 op_stack 弹出运算符，并用 val_stack 顶部的操作数组合成子表达式，直到遇到左括号为止；左括号本身丢弃，不会进入 val_stack。

3. 清空运算符栈

   当所有 token 扫描完成后，若 op_stack 中仍有运算符，则依次弹出，并与 val_stack 中的操作数组合成更大的表达式，直到运算符栈为空。

4. 结束条件

   最终，val_stack 中应只剩下一个元素，该元素即为完整的抽象语法树或后缀表达式。若栈内元素数量不为一，或存在未匹配的括号，则说明输入表达式存在错误。

演算示例

接下来我们以解析 (1 + 2) * (3 - 4) ^ 2 为例，来展示在读入 token 的过程中，两个栈是如何变化的，从而更好地理解 Shunting Yard 算法：

步骤	读入 token	运算符栈（op_stack）	值栈（val_stack）	说明
1	(	[(]	[]	左括号压入运算符栈
2	1	[(]	[1]	数字压入值栈
3	+	[(, +]	[1]	运算符压入运算符栈
4	2	[(, +]	[1, 2]	数字压入值栈
5	)	[]	[1 + 2]	弹出直到左括号：1 与 2 结合为 1+2
6	*	[*]	[1 + 2]	运算符压入运算符栈
7	(	[*, (]	[1 + 2]	左括号压入运算符栈
8	3	[*, (]	[1 + 2, 3]	数字压入值栈
9	-	[*, (, -]	[1 + 2, 3]	运算符压入运算符栈
10	4	[*, (, -]	[1 + 2, 3, 4]	数字压入值栈
11	)	[*]	[1 + 2, 3 - 4]	弹出直到左括号：3 与 4 结合为 3-4
12	^	[*, ^]	[1 + 2, 3 - 4]	幂运算符压入栈（右结合，不会触发弹出）
13	2	[*, ^]	[1 + 2, 3 - 4, 2]	数字压入值栈
14	输入结束	[]	[(1 + 2) * (3 - 4) ^ 2]	清空运算符栈：先弹出 ^，结合 3-4 与 2；再弹出 *，结合 1+2 与结果

在这个例子中，有以下几点值得注意：

• 括号优先处理 在第一组括号 (1 + 2) 中，运算符 + 被延迟存放在运算符栈中，直到遇到右括号才与 1 和 2 结合。第二组括号 (3 - 4) 的处理过程完全相同。

• 优先级的体现 当遇到 * 时，它被压入运算符栈。但随后遇到幂运算符 ^ 时，由于 ^ 的优先级高于 *，且是右结合，因此直接压栈，而不会触发 * 的弹出。

• 结合性的作用 幂运算符 ^ 通常定义为右结合，这意味着表达式 a ^ b ^ c 会被解析为 a ^ (b ^ c)。在本例中，(3-4) ^ 2 保持这种结合方式，正确构建了子表达式。

• 最终结果 在输入结束后，运算符栈依次被清空，最终形成完整的表达式：

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

在 MoonBit 中实现 Shunting Yard 算法

首先我们需要定义表达式和 token 的类型：

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)

我们可以利用 MoonBit 中的正则表达式匹配语法，快速的实现一个简单的 tokenizer：

pub fn 
fn tokenize(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
}

tokenize 函数的作用是把输入字符串分割成一系列 token：

• 匹配数字 [0-9]+，转换为 Token::Literal；
• 匹配四则运算符和幂运算符 [-+*/^]，转换为 Token::Op；
• 匹配括号 ( 与 )，分别转换为 LeftParen 和 RightParen；
• 匹配空格、换行等空白字符则直接跳过；
• 如果遇到不符合规则的字符，则报错。 通过 lexmatch 和正则表达式，整个分词过程既简洁又高效。

接下来我们定义一个全局的操作符表，用于存储操作符的优先级和结合性：

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 : 
struct Map[K, V] {
  // private fields
}
Mutable linked hash map that maintains the order of insertion, not thread safe.
Example
test {
  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 },
}

这里通过 op_table 定义了常见运算符的优先级与结合性：

• + 和 - 的优先级最低（10），是左结合；

• * 和 / 的优先级更高（20），同样是左结合；

• ^（幂运算）的优先级最高（30），但它是右结合。

接下来我们定义一个辅助函数，用于判断在遇到一个新的运算符时，是否需要先处理（弹出）栈顶的运算符：

fn 
fn should_pop(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 
fn Compare::op_gt(x : Int, y : Int) -> Bool
> 
OpInfo
incoming_op_info.
Int
precedence 
(Bool, Bool) -> Bool
||
  (
    
OpInfo
top_op_info.
Int
precedence 
fn Eq::equal(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:
test {
  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
  )
}

should_pop 的逻辑是 Shunting Yard 算法的核心之一：

• 如果栈顶运算符的优先级高于新运算符，则应当先处理栈顶运算符；
• 如果两者优先级相等，并且栈顶运算符是左结合，同样应当先处理栈顶运算符；
• 否则，保留栈顶运算符，把新运算符直接压入栈。

接下来我们实现表达式的解析函数：

pub fn 
fn parse_expr(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.
fn[T] Array::pop(self : Array[T]) -> T?
Removes the last element from an array and returns it, or None if it is empty.
Example
test {
  let v = [1, 2, 3]
  assert_eq(v.pop(), Some(3))
  assert_eq(v, [1, 2])
}
pop().
fn[X] Option::unwrap(self : X?) -> X
Extract the value in Some.
If the value is None, it throws a panic.
unwrap()
    let 
Expr
left = 
Array[Expr]
val_stack.
fn[T] Array::pop(self : Array[T]) -> T?
Removes the last element from an array and returns it, or None if it is empty.
Example
test {
  let v = [1, 2, 3]
  assert_eq(v.pop(), Some(3))
  assert_eq(v, [1, 2])
}
pop().
fn[X] Option::unwrap(self : X?) -> X
Extract the value in Some.
If the value is None, it throws a panic.
unwrap()
    
Array[Expr]
val_stack.
fn[T] Array::push(self : Array[T], value : T) -> Unit
Adds an element to the end of the array.
If the array is at capacity, it will be reallocated.
Example
test {
  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.
fn[T] Array::push(self : Array[T], value : T) -> Unit
Adds an element to the end of the array.
If the array is at capacity, it will be reallocated.
Example
test {
  let v = []
  v.push(3)
}
push(Expr::
(Int) -> Expr
Literal(
Int
n))
      
(String) -> Token
Op(
String
incoming_op) => {
        let 
OpInfo
incoming_op_info = 
let op_table : Map[String, OpInfo]
op_table
fn[K : Hash + Eq, V] Map::op_get(self : Map[K, V], key : K) -> V
Get value with at access semantics.
[incoming_op]
        while true {
          match 
Array[String]
op_stack.
fn[A] Array::last(self : Array[A]) -> A?
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:
test {
  let arr = [1, 2, 3]
  debug_inspect(arr.last(), content="Some(3)")
  let empty : Array[Int] = []
  debug_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
&&
                
fn should_pop(top_op_info~ : OpInfo, incoming_op_info~ : OpInfo) -> Bool
should_pop(
OpInfo
top_op_info=
let op_table : Map[String, OpInfo]
op_table
fn[K : Hash + Eq, V] Map::op_get(self : Map[K, V], key : K) -> V
Get value with at access semantics.
[top_op], 
OpInfo
incoming_op_info~) {
                
Array[String]
op_stack.
fn[T] Array::pop(self : Array[T]) -> T?
Removes the last element from an array and returns it, or None if it is empty.
Example
test {
  let v = [1, 2, 3]
  assert_eq(v.pop(), Some(3))
  assert_eq(v, [1, 2])
}
pop() |> 
fn[T] ignore(t : T) -> 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:
test {
  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.
fn[T] Array::push(self : Array[T], value : T) -> Unit
Adds an element to the end of the array.
If the array is at capacity, it will be reallocated.
Example
test {
  let v = []
  v.push(3)
}
push(
String
incoming_op)
      }
      
Token
LeftParen => 
Array[String]
op_stack.
fn[T] Array::push(self : Array[T], value : T) -> Unit
Adds an element to the end of the array.
If the array is at capacity, it will be reallocated.
Example
test {
  let v = []
  v.push(3)
}
push("(")
      
Token
RightParen =>
        while 
Array[String]
op_stack.
fn[T] Array::pop(self : Array[T]) -> T?
Removes the last element from an array and returns it, or None if it is empty.
Example
test {
  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.
fn[T] Array::pop(self : Array[T]) -> T?
Removes the last element from an array and returns it, or None if it is empty.
Example
test {
  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.
fn[T] Array::pop(self : Array[T]) -> T?
Removes the last element from an array and returns it, or None if it is empty.
Example
test {
  let v = [1, 2, 3]
  assert_eq(v.pop(), Some(3))
  assert_eq(v, [1, 2])
}
pop().
fn[X] Option::unwrap(self : X?) -> X
Extract the value in Some.
If the value is None, it throws a panic.
unwrap()
}

parse_expr 是整个 Shunting Yard 算法的核心实现：

1. 数据结构准备

   • op_stack 存储运算符和括号；
   • val_stack 存储操作数或部分构造好的子表达式；
   • 内部函数 push_binary_expr 封装了一个小步骤：从值栈中弹出两个操作数，结合运算符，生成一个新的 BinExpr 节点，并压回值栈。

2. 遍历 token

   • 数字：直接压入 val_stack。
   • 运算符：不断检查 op_stack 栈顶的运算符，如果优先级更高或需要先计算，则弹出并构造子表达式；直到不满足条件时，把新运算符压入栈。
   • 左括号：压入 op_stack，用于分隔子表达式。
   • 右括号：持续弹出运算符，并结合值栈中的操作数形成子表达式，直到遇到匹配的左括号。

3. 清空运算符栈

   遍历完成后，可能仍有运算符滞留在 op_stack 中，这时需要逐一弹出，并结合值栈中的操作数，直到运算符栈为空。

4. 返回结果

   最终，值栈中应当只剩下一个元素，它就是完整的抽象语法树。若不是这种情况，说明输入表达式存在语法错误。

最后我们可以定义一个简单的 eval 函数，以便于进行测试：

pub fn 
fn eval(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 {
        "+" => 
fn eval(expr : Expr) -> Int
eval(
Expr
left) 
fn Add::add(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:
test {
  inspect(42 + 1, content="43")
  inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
}
+ 
fn eval(expr : Expr) -> Int
eval(
Expr
right)
        "-" => 
fn eval(expr : Expr) -> Int
eval(
Expr
left) 
fn Sub::sub(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:
test {
  let a = 42
  let b = 10
  inspect(a - b, content="32")
  let max = 2147483647 // Int maximum value
  inspect(max - -1, content="-2147483648") // Overflow case
}
- 
fn eval(expr : Expr) -> Int
eval(
Expr
right)
        "*" => 
fn eval(expr : Expr) -> Int
eval(
Expr
left) 
fn Mul::mul(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:
test {
  inspect(42 * 2, content="84")
  inspect(-10 * 3, content="-30")
  let max = 2147483647 // Int.max_value
  inspect(max * 2, content="-2") // Overflow wraps around
}
* 
fn eval(expr : Expr) -> Int
eval(
Expr
right)
        "/" => 
fn eval(expr : Expr) -> Int
eval(
Expr
left) 
fn Div::div(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:
test {
  inspect(10 / 3, content="3") // truncates towards zero
  inspect(-10 / 3, content="-3")
  inspect(10 / -3, content="-3")
}
/ 
fn eval(expr : Expr) -> Int
eval(
Expr
right)
        "^" => {
          fn 
(Int, Int) -> Int
pow(
Int
base : 
Int
Int, 
Int
exp : 
Int
Int) -> 
Int
Int {
            if 
Int
exp 
fn Eq::equal(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:
test {
  inspect(42 == 42, content="true")
  inspect(42 == -42, content="false")
}
== 0 {
              1
            } else {
              
Int
base 
fn Mul::mul(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:
test {
  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 
fn Sub::sub(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:
test {
  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(
fn eval(expr : Expr) -> Int
eval(
Expr
left), 
fn eval(expr : Expr) -> Int
eval(
Expr
right))
        }
        _ => 
fn[T] abort(_ : String) -> T
abort("Invalid operator")
      }
  }
}

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

并通过一些简单的测试用例来验证我们的实现：

test "parse_and_eval" {
  
fn inspect(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:
test {
  inspect(42, content="42")
  inspect("hello", content="hello")
  debug_inspect([1, 2, 3], content="[1, 2, 3]")
}
inspect(
fn parse_and_eval(input : String) -> Int raise
parse_and_eval("1 + 2 * 3"), 
String
content="7")
  
fn inspect(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:
test {
  inspect(42, content="42")
  inspect("hello", content="hello")
  debug_inspect([1, 2, 3], content="[1, 2, 3]")
}
inspect(
fn parse_and_eval(input : String) -> Int raise
parse_and_eval("2 ^ 3 ^ 2"), 
String
content="512")
  
fn inspect(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:
test {
  inspect(42, content="42")
  inspect("hello", content="hello")
  debug_inspect([1, 2, 3], content="[1, 2, 3]")
}
inspect(
fn parse_and_eval(input : String) -> Int raise
parse_and_eval("(2 ^ 3) ^ 2"), 
String
content="64")
  
fn inspect(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:
test {
  inspect(42, content="42")
  inspect("hello", content="hello")
  debug_inspect([1, 2, 3], content="[1, 2, 3]")
}
inspect(
fn parse_and_eval(input : String) -> Int raise
parse_and_eval("(1 + 2) * 3"), 
String
content="9")
  
fn inspect(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:
test {
  inspect(42, content="42")
  inspect("hello", content="hello")
  debug_inspect([1, 2, 3], content="[1, 2, 3]")
}
inspect(
fn parse_and_eval(input : String) -> Int raise
parse_and_eval("10 - (3 + 2)"), 
String
content="5")
  
fn inspect(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:
test {
  inspect(42, content="42")
  inspect("hello", content="hello")
  debug_inspect([1, 2, 3], content="[1, 2, 3]")
}
inspect(
fn parse_and_eval(input : String) -> Int raise
parse_and_eval("2 * (3 + 4)"), 
String
content="14")
  
fn inspect(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:
test {
  inspect(42, content="42")
  inspect("hello", content="hello")
  debug_inspect([1, 2, 3], content="[1, 2, 3]")
}
inspect(
fn parse_and_eval(input : String) -> Int raise
parse_and_eval("(5 + 3) / 2"), 
String
content="4")
  
fn inspect(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:
test {
  inspect(42, content="42")
  inspect("hello", content="hello")
  debug_inspect([1, 2, 3], content="[1, 2, 3]")
}
inspect(
fn parse_and_eval(input : String) -> Int raise
parse_and_eval("10 / 2 - 1"), 
String
content="4")
  
fn inspect(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:
test {
  inspect(42, content="42")
  inspect("hello", content="hello")
  debug_inspect([1, 2, 3], content="[1, 2, 3]")
}
inspect(
fn parse_and_eval(input : String) -> Int raise
parse_and_eval("1 + 2 + 3"), 
String
content="6")
  
fn inspect(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:
test {
  inspect(42, content="42")
  inspect("hello", content="hello")
  debug_inspect([1, 2, 3], content="[1, 2, 3]")
}
inspect(
fn parse_and_eval(input : String) -> Int raise
parse_and_eval("10 - 5 - 2"), 
String
content="3")
  
fn inspect(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:
test {
  inspect(42, content="42")
  inspect("hello", content="hello")
  debug_inspect([1, 2, 3], content="[1, 2, 3]")
}
inspect(
fn parse_and_eval(input : String) -> Int raise
parse_and_eval("5"), 
String
content="5")
  
fn inspect(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:
test {
  inspect(42, content="42")
  inspect("hello", content="hello")
  debug_inspect([1, 2, 3], content="[1, 2, 3]")
}
inspect(
fn parse_and_eval(input : String) -> Int raise
parse_and_eval("(1 + 2) * (3 + 4)"), 
String
content="21")
  
fn inspect(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:
test {
  inspect(42, content="42")
  inspect("hello", content="hello")
  debug_inspect([1, 2, 3], content="[1, 2, 3]")
}
inspect(
fn parse_and_eval(input : String) -> Int raise
parse_and_eval("2 ^ (1 + 2)"), 
String
content="8")
  
fn inspect(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:
test {
  inspect(42, content="42")
  inspect("hello", content="hello")
  debug_inspect([1, 2, 3], content="[1, 2, 3]")
}
inspect(
fn parse_and_eval(input : String) -> Int raise
parse_and_eval("1 + 2 * 3 - 4 / 2 + 5"), 
String
content="10")
  
fn inspect(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:
test {
  inspect(42, content="42")
  inspect("hello", content="hello")
  debug_inspect([1, 2, 3], content="[1, 2, 3]")
}
inspect(
fn parse_and_eval(input : String) -> Int raise
parse_and_eval("((1 + 2) * 3) ^ 2 - 10"), 
String
content="71")
  
fn inspect(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:
test {
  inspect(42, content="42")
  inspect("hello", content="hello")
  debug_inspect([1, 2, 3], content="[1, 2, 3]")
}
inspect(
fn parse_and_eval(input : String) -> Int raise
parse_and_eval("100 / (2 * 5) + 3 * (4 - 1)"), 
String
content="19")
  
fn inspect(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:
test {
  inspect(42, content="42")
  inspect("hello", content="hello")
  debug_inspect([1, 2, 3], content="[1, 2, 3]")
}
inspect(
fn parse_and_eval(input : String) -> Int raise
parse_and_eval("2 ^ 2 * 3 + 1"), 
String
content="13")
  
fn inspect(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:
test {
  inspect(42, content="42")
  inspect("hello", content="hello")
  debug_inspect([1, 2, 3], content="[1, 2, 3]")
}
inspect(
fn parse_and_eval(input : String) -> Int raise
parse_and_eval("1 + 2 * 3 ^ 2 - 4 / 2"), 
String
content="17")
}

小结

Shunting Yard 算法的核心思想在于使用两个栈来显式管理运算过程：

• 值栈（val_stack） 用于保存数字和已经组合好的部分子表达式；
• 运算符栈（op_stack） 用于保存尚未处理的运算符和括号。

通过定义运算符的优先级与结合性，并在扫描 token 的过程中不断比较和弹出栈顶运算符，Shunting Yard 能够保证表达式被按照正确的顺序组合成抽象语法树（AST）。 最终，当所有 token 被读取并且运算符栈清空后，值栈中剩下的就是完整的表达式树。

这种方法直观地模拟了我们手工计算时的思路：先把暂时不能计算的内容“记下来”，等条件合适时再取出处理。它的流程清晰、实现简洁，非常适合作为学习表达式解析的起点。

之前 MoonBit Pearl 中发布过一篇介绍 Pratt parsing 的文章，两者都是解决“如何正确解析表达式优先级和结合性”的经典方法，但它们的思路截然不同。 Shunting Yard 使用循环和显式的数据结构，通过运算符栈和值栈来管理尚未处理的符号和部分子表达式，整个过程像是手工操纵两个栈，逻辑清晰且容易跟踪。Pratt Parser 则基于递归下降，每个 token 定义在不同上下文下的解析方式，解析的推进依赖语言运行时的调用栈：每一次递归调用都相当于把尚未完成的状态压入栈中，返回时再继续组合。换句话说，Pratt Parser 将“栈”的存在隐藏在递归调用里，而 Shunting Yard 则把这种状态管理显式化，用循环和数据结构来直接模拟出来。因此，可以认为 Shunting Yard 是将 Pratt Parser 中隐含在调用栈里的机制转写为显式的栈操作。前者步骤机械化，适合快速实现固定的运算符解析；后者更灵活，尤其在处理前缀、后缀或自定义运算符时更为自然。