本文完整代码：https://github.com/rosedblabs/rust-practice
表达式解析、计算是一种基本和常见的任务，例如最常见的算术表达式，计算的方法有很多，比如逆波兰表达式、LL、LR 算法等等。
这一次介绍一种最简单的、容易理解的基于运算符优先级的算法来完成这个任务。
基于运算符优先级的算法叫做 Precedence Climbing，它本质上是一种递归下降解析表达式的方法，通过递归地处理运算符和操作数来解析表达式，并根据运算符的优先级和结合性来确定表达式的计算顺序。
这种算法的核心思想是利用运算符的优先级进行“爬升”（Climbing），以决定表达式的结构和计算顺序。
首先我们做一些约束，由于运算符众多，我们可以支持几种最常用的：
并且我们知道，幂运算的优先级是最高的，其次是 * 和 /，优先级最低的是 + 和 -。
所以约定其运算符的优先级分别为 3（^）、2（* /）、1（+ -）
1
2
3
4
5
| 2 + 3 ^ 2 * 3 + 4
|---------------| : prec 1
|-------| : prec 2
|---| : prec 3
|
约定优先级的主要作用是在计算的时候，需要根据优先级来确定计算的顺序。
确定了优先级的问题，第二个问题是结合性，运算符的结合性其实也是确定的，例如加法是左结合的，这意味着 2 + 3 + 4 等价于 (2 + 3) + 4，而幂运算是右结合的，这意味着 2 ^ 3 ^ 4 实际上等价于 2 ^ (3 ^ 4)。
最后还需要注意一个问题，那就是子表达式，也就是用括号包裹的部分，这部分实际上是需要单独进行计算的，并且比运算符的优先级更高。
其实也很容易理解，比如 2 * (3 + 5) * 7，尽管 * 的优先级比 + 高，但是需要先计算括号内的部分。
确定了这些需求，我们再来看如何用 Rust 代码来进行实现。
首先我们需要将表达式进行解析，也就是词法分析的阶段，将一个表达式解析为不同的 Token，下面是约定的几种 Token：
1
2
3
4
5
6
7
8
9
10
11
12
| // Token 表示，数字、运算符号、括号
#[derive(Debug, Clone, Copy)]
enum Token {
Number(i32),
Plus, // 加
Minus, // 减
Multiply, // 乘
Divide, // 除
Power, // 幂
LeftParen, // 左括号
RightParen, // 右括号
}
|
然后定义了一个 Tokenizer 结构体，主要是利用 Peekable 接口将表达式解析为不同的 Token：
1
2
3
4
5
| // 将一个算术表达式解析成连续的 Token
// 并通过 Iterator 返回，也可以通过 Peekable 接口获取
struct Tokenizer<'a> {
tokens: Peekable<Chars<'a>>,
}
|
然后自定义实现了一个 Iterator，让解析后的 Token 可以通过迭代器进行返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| impl<'a> Iterator for Tokenizer<'a> {
type Item = Token;
fn next(&mut self) -> Option<Self::Item> {
// 消除前面的空格
self.consume_whitespace();
// 解析当前位置的 Token 类型
match self.tokens.peek() {
Some(c) if c.is_numeric() => self.scan_number(),
Some(_) => self.scan_operator(),
None => return None,
}
}
}
|
假如我们的表达式是 2 + 3 ^ 2 * 3 + 4，实际上解析后的 Token 就是：
1
2
3
4
5
6
7
8
9
| Token::Number(2)
Token::Plus
Token::Number(3)
Token::Power
Token::Number(2)
Token::Multiply
Token::Number(3)
Token::Plus
Token::Number(4)
|
拿到 Token 之后，进入到了语法分析的阶段，需要根据每个表达式的含义，以及其优先级，计算对应的结果。
首先定义一个方法，计算单个 Token 以及子表达式，这只存在两种情况，分别是 Number 这个 Token，以及带括号的子表达式。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| fn compute_atom(&mut self) -> Result<i32> {
match self.iter.peek() {
// 如果是数字的话，直接返回
Some(Token::Number(n)) => {
let val = *n;
self.iter.next();
return Ok(val);
}
// 如果是左括号的话，递归计算括号内的值
Some(Token::LeftParen) => {
self.iter.next();
let result = self.compute_expr(1)?;
match self.iter.next() {
Some(Token::RightParen) => (),
_ => return Err(ExprError::Parse("Unexpected character".into())),
}
return Ok(result);
}
_ => {
return Err(ExprError::Parse(
"Expecting a number or left parenthesis".into(),
))
}
}
}
|
这里其实比较好理解，如果是 Number 直接返回，如果是子表达式，则重新调用计算表达式的方法进行计算。
然后是另一个核心的方法计算表达式：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| fn compute_expr(&mut self, min_prec: i32) -> Result<i32> {
// 计算第一个 Token
let mut atom_lhs = self.compute_atom()?;
loop {
let cur_token = self.iter.peek();
if cur_token.is_none() {
break;
}
let token = *cur_token.unwrap();
// 1. Token 一定是运算符
// 2. Token 的优先级必须大于等于 min_prec
if !token.is_operator() || token.precedence() < min_prec {
break;
}
let mut next_prec = token.precedence();
if token.assoc() == ASSOC_LEFT {
next_prec += 1;
}
self.iter.next();
// 递归计算右边的表达式
let atom_rhs = self.compute_expr(next_prec)?;
// 得到了两边的值，进行计算
match token.compute(atom_lhs, atom_rhs) {
Some(res) => atom_lhs = res,
None => return Err(ExprError::Parse("Unexpected expr".into())),
}
}
Ok(atom_lhs)
}
|
这个方法中核心的逻辑可以分几个步骤来理解：
一是使用了 min_prec 参数控制当前层级的优先级，如果表达式的优先级小于 min_prec 则直接跳出循环，返回当前的值。
比如 2 * 3 + 4，* 会先解析到，然后 + 运算符的优先级明显比 * 更低，会直接返回当前值 3。
二是如果运算符的结合性是左边的话，则下一次迭代的 min_prec 需要递增。
比如表达式是 2 * 3 * 4，解析到第二个 * 的时候，* 的优先级本来是 2，但它是左结合的，所以此时 min_prec 是 3，会直接跳出循环，所以实际上会先计算 2 * 3。
最后是得到了运算符两边的值，就可以进行计算了，这里是根据运算符的实际含义来进行的：
1
2
3
4
5
6
7
8
9
10
11
| // 根据当前运算符进行计算
fn compute(&self, l: i32, r: i32) -> Option<i32> {
match self {
Token::Plus => Some(l + r),
Token::Minus => Some(l - r),
Token::Multiply => Some(l * r),
Token::Divide => Some(l / r),
Token::Power => Some(l.pow(r as u32)),
_ => None,
}
}
|
这就是根据运算符优先级来进行表达式计算的整体流程，这个算法看起来还是非常简洁优雅的，非常巧妙的利用优先级来解决运算的顺序和结合等问题。
完整的代码也只有 200 多行，比较适合用来练手，通过这个项目，可以学习到：
- 一个优雅、简洁的表达式计算的算法
- 解决类似写一个计算器的面试问题
- Rust 基础数据类型、枚举、结构体基本用法
- 函数、递归
- match 表达式
- 自定义 Result 错误处理
- 迭代器的常见用法 next、peekable 等
- 自定义迭代器
- Option 使用
最后附上项目地址：
https://github.com/rosedblabs/rust-practice
对你有帮助的话，欢迎给个 star ⭐️ 哦！