影音體驗是真的強 簡單聊聊iQOO Pad
大公司的好處就是產(chǎn)品線豐富，非常細分化的東西也能給你做出來，例如早先我們看到了新的vivo Pad2，之后我們又在iQOO Neo8 Pro的發(fā)布會上看到了iQOO的首款平板產(chǎn)品iQOO Pad。雖
表達式解析、計算是一種基本和常見的任務(wù)，例如最常見的算術(shù)表達式，計算的方法有很多，比如逆波蘭表達式、LL、LR 算法等等。
這一次介紹一種最簡單的、容易理解的基于運算符優(yōu)先級的算法來完成這個任務(wù)。
基于運算符優(yōu)先級的算法叫做 Precedence Climbing，它本質(zhì)上是一種遞歸下降解析表達式的方法，通過遞歸地處理運算符和操作數(shù)來解析表達式，并根據(jù)運算符的優(yōu)先級和結(jié)合性來確定表達式的計算順序。
這種算法的核心思想是利用運算符的優(yōu)先級進行“爬升”（Climbing），以決定表達式的結(jié)構(gòu)和計算順序。
首先我們做一些約束，由于運算符眾多，我們可以支持幾種最常用的：
并且我們知道，冪運算的優(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)先級的問題，第二個問題是結(jié)合性，運算符的結(jié)合性其實也是確定的，例如加法是左結(jié)合的，這意味著 2 + 3 + 4 等價于 (2 + 3) + 4，而冪運算是右結(jié)合的，這意味著 2 ^ 3 ^ 4 實際上等價于 2 ^ (3 ^ 4)。
最后還需要注意一個問題，那就是子表達式，也就是用括號包裹的部分，這部分實際上是需要單獨進行計算的，并且比運算符的優(yōu)先級更高。
其實也很容易理解，比如 2 * (3 + 5) * 7，盡管 * 的優(yōu)先級比 + 高，但是需要先計算括號內(nèi)的部分。
確定了這些需求，我們再來看如何用 Rust 代碼來進行實現(xiàn)。
首先我們需要將表達式進行解析，也就是詞法分析的階段，將一個表達式解析為不同的 Token，下面是約定的幾種 Token：
// Token 表示，數(shù)字、運算符號、括號#[derive(Debug, Clone, Copy)]enum Token { Number(i32), Plus, // 加 Minus, // 減 Multiply, // 乘 Divide, // 除 Power, // 冪 LeftParen, // 左括號 RightParen, // 右括號}然后定義了一個 Tokenizer 結(jié)構(gòu)體，主要是利用 Peekable 接口將表達式解析為不同的 Token：
// 將一個算術(shù)表達式解析成連續(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::PlusToken::Number(3)Token::PowerToken::Number(2)Token::MultiplyToken::Number(3)Token::PlusToken::Number(4)拿到 Token 之后，進入到了語法分析的階段，需要根據(jù)每個表達式的含義，以及其優(yōu)先級，計算對應(yīng)的結(jié)果。
首先定義一個方法，計算單個 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); } // 如果是左括號的話，遞歸計算括號內(nèi)的值 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 直接返回，如果是子表達式，則重新調(diào)用計算表達式的方法進行計算。
然后是另一個核心的方法計算表達式：
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。
二是如果運算符的結(jié)合性是左邊的話，則下一次迭代的 min_prec 需要遞增。
比如表達式是 2 * 3 * 4，解析到第二個 * 的時候，* 的優(yōu)先級本來是 2，但它是左結(jié)合的，所以此時 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)先級來解決運算的順序和結(jié)合等問題。
完整的代碼也只有 200 多行，比較適合用來練手，通過這個項目，可以學(xué)習到：
本文鏈接：http://www.tebozhan.com/showinfo-26-86686-0.html太優(yōu)雅了！Rust 200 行代碼實現(xiàn)表達式解析
聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請聯(lián)系：2376512515@qq.com 津ICP備18001702號
津公網(wǎng)安備 12010102000574號