表达式解析、计算是一种基本和常见的任务，例如最常见的算术表达式，计算的方法有很多，比如逆波兰表达式、LL、LR 算法等等。
这一次介绍一种最简单的、容易理解的基于运算符优先级的算法来完成这个任务。
基于运算符优先级的算法叫做 Precedence Climbing，它本质上是一种递归下降解析表达式的方法，通过递归地处理运算符和操作数来解析表达式，并根据运算符的优先级和结合性来确定表达式的计算顺序。
这种算法的核心思想是利用运算符的优先级进行“爬升”（Climbing），以决定表达式的结构和计算顺序。
首先我们做一些约束，由于运算符众多，我们可以支持几种最常用的：
并且我们知道，幂运算的优先级是最高的，其次是 * 和 /，优先级最低的是 + 和 -。所以约定其运算符的优先级分别为 3（^）、2（* /）、1（+ -）
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：
// Token 表示，数字、运算符号、括号#[derive(Debug, Clone, Copy)]enum Token { Number(i32), Plus, // 加 Minus, // 减 Multiply, // 乘 Divide, // 除 Power, // 幂 LeftParen, // 左括号 RightParen, // 右括号}然后定义了一个 Tokenizer 结构体，主要是利用 Peekable 接口将表达式解析为不同的 Token：
// 将一个算术表达式解析成连续的 Token// 并通过 Iterator 返回，也可以通过 Peekable 接口获取struct Tokenizer<'a> { tokens: Peekable<Chars<'a>>,}然后自定义实现了一个 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::PlusToken::Number(3)Token::PowerToken::Number(2)Token::MultiplyToken::Number(3)Token::PlusToken::Number(4)拿到 Token 之后，进入到了语法分析的阶段，需要根据每个表达式的含义，以及其优先级，计算对应的结果。
首先定义一个方法，计算单个 Token 以及子表达式，这只存在两种情况，分别是 Number 这个 Token，以及带括号的子表达式。
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 直接返回，如果是子表达式，则重新调用计算表达式的方法进行计算。
然后是另一个核心的方法计算表达式：
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。
最后是得到了运算符两边的值，就可以进行计算了，这里是根据运算符的实际含义来进行的：
// 根据当前运算符进行计算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 多行，比较适合用来练手，通过这个项目，可以学习到：
本文链接：http://www.28at.com/showinfo-26-86686-0.html太优雅了！Rust 200 行代码实现表达式解析
声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。邮件：2376512515@qq.com
上一篇： 深入剖析：如何使用Pulsar和Arthas高效排查消息队列延迟问题
下一篇： C#实战：图像清晰度增强介绍和案例实践
Copyright © 2016-2023 天津谷骐科技有限公司 版权所有 sitemap.xml
违法及侵权请联系：2376512515@qq.com 津ICP备18001702号
津公网安备 12010102000574号
