天貓精靈Sound Pro體驗：智能音箱沒有音質？來聽聽我的
這幾年除了手機作為智能生活終端最主要的核心之外，第二個可以成為中心點的產品是什么？——是智能音箱。 手機在執行命令的時候有兩種操作方式，手和智能語音助手，而智能音箱只
表達式解析、計算是一種基本和常見的任務，例如最常見的算術表達式，計算的方法有很多，比如逆波蘭表達式、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://m.www897cc.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號