太優(yōu)雅了！Rust 200 行代碼實現(xiàn)表達式解析
表達式解析、計算是一種基本和常見的任務，例如最常見的算術表達式，計算的方法有很多，比如逆波蘭表達式、LL、LR 算法等等。
這一次介紹一種最簡單的、容易理解的基于運算符優(yōu)先級的算法來完成這個任務。
基于運算符優(yōu)先級的算法叫做 Precedence Climbing，它本質上是一種遞歸下降解析表達式的方法，通過遞歸地處理運算符和操作數(shù)來解析表達式，并根據(jù)運算符的優(yōu)先級和結合性來確定表達式的計算順序。
這種算法的核心思想是利用運算符的優(yōu)先級進行“爬升”（Climbing），以決定表達式的結構和計算順序。
首先我們做一些約束，由于運算符眾多，我們可以支持幾種最常用的：
- + 加
- - 減
- * 乘
- / 除
- ^ 冪
并且我們知道，冪運算的優(yōu)先級是最高的，其次是 * 和 /，優(yōu)先級最低的是 + 和 -。所以約定其運算符的優(yōu)先級分別為 3（^）、2（* /）、1（+ -）
2 + 3 ^ 2 * 3 + 4
|---------------| : prec 1
|-------| : prec 2
|---| : prec 3約定優(yōu)先級的主要作用是在計算的時候，需要根據(jù)優(yōu)先級來確定計算的順序。
確定了優(yōu)先級的問題，第二個問題是結合性，運算符的結合性其實也是確定的，例如加法是左結合的，這意味著 2 + 3 + 4 等價于 (2 + 3) + 4，而冪運算是右結合的，這意味著 2 ^ 3 ^ 4 實際上等價于 2 ^ (3 ^ 4)。
最后還需要注意一個問題，那就是子表達式，也就是用括號包裹的部分，這部分實際上是需要單獨進行計算的，并且比運算符的優(yōu)先級更高。
其實也很容易理解，比如 2 * (3 + 5) * 7，盡管 * 的優(yōu)先級比 + 高，但是需要先計算括號內的部分。
確定了這些需求，我們再來看如何用 Rust 代碼來進行實現(xiàn)。
首先我們需要將表達式進行解析，也就是詞法分析的階段，將一個表達式解析為不同的 Token，下面是約定的幾種 Token：
// Token 表示，數(shù)字、運算符號、括號
#[derive(Debug, Clone, Copy)]
enum Token {
Number(i32),
Plus, // 加
Minus, // 減
Multiply, // 乘
Divide, // 除
Power, // 冪
LeftParen, // 左括號
RightParen, // 右括號
}然后定義了一個 Tokenizer 結構體，主要是利用 Peekable 接口將表達式解析為不同的 Token：
// 將一個算術表達式解析成連續(xù)的 Token
// 并通過 Iterator 返回，也可以通過 Peekable 接口獲取
struct Tokenizer<'a> {
tokens: Peekable<Chars<'a>>,
}然后自定義實現(xiàn)了一個 Iterator，讓解析后的 Token 可以通過迭代器進行返回。
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 就是：
Token::Number(2)
Token::Plus
Token::Number(3)
Token::Power
Token::Number(2)
Token::Multiply
Token::Number(3)
Token::Plus
Token::Number(4)拿到 Token 之后，進入到了語法分析的階段，需要根據(jù)每個表達式的含義，以及其優(yōu)先級，計算對應的結果。
首先定義一個方法，計算單個 Token 以及子表達式，這只存在兩種情況，分別是 Number 這個 Token，以及帶括號的子表達式。
fn compute_atom(&mut self) -> Result<i32> {
match self.iter.peek() {
// 如果是數(shù)字的話，直接返回
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 直接返回，如果是子表達式，則重新調用計算表達式的方法進行計算。
然后是另一個核心的方法計算表達式：
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 的優(yōu)先級必須大于等于 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 參數(shù)控制當前層級的優(yōu)先級，如果表達式的優(yōu)先級小于 min_prec 則直接跳出循環(huán)，返回當前的值。
比如 2 * 3 + 4，* 會先解析到，然后 + 運算符的優(yōu)先級明顯比 * 更低，會直接返回當前值 3。
二是如果運算符的結合性是左邊的話，則下一次迭代的 min_prec 需要遞增。
比如表達式是 2 * 3 * 4，解析到第二個 * 的時候，* 的優(yōu)先級本來是 2，但它是左結合的，所以此時 min_prec 是 3，會直接跳出循環(huán)，所以實際上會先計算 2 * 3。
最后是得到了運算符兩邊的值，就可以進行計算了，這里是根據(jù)運算符的實際含義來進行的：
// 根據(jù)當前運算符進行計算
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,
}
}這就是根據(jù)運算符優(yōu)先級來進行表達式計算的整體流程，這個算法看起來還是非常簡潔優(yōu)雅的，非常巧妙的利用優(yōu)先級來解決運算的順序和結合等問題。
完整的代碼也只有 200 多行，比較適合用來練手，通過這個項目，可以學習到：
- 一個優(yōu)雅、簡潔的表達式計算的算法
- 解決類似寫一個計算器的面試問題
- Rust 基礎數(shù)據(jù)類型、枚舉、結構體基本用法
- 函數(shù)、遞歸
- match 表達式
- 自定義 Result 錯誤處理
- 迭代器的常見用法 next、peekable 等
- 自定義迭代器
- Option 使用
