線程通訊的三種方法！通俗易懂
線程通信是指多個(gè)線程之間通過(guò)某種機(jī)制進(jìn)行協(xié)調(diào)和交互，例如，線程等待和通知機(jī)制就是線程通訊的主要手段之一。 在 Java 中，線程等待和通知的實(shí)現(xiàn)手段有以下幾種方式：Object 類下
表達(dá)式解析、計(jì)算是一種基本和常見(jiàn)的任務(wù)，例如最常見(jiàn)的算術(shù)表達(dá)式，計(jì)算的方法有很多，比如逆波蘭表達(dá)式、LL、LR 算法等等。
這一次介紹一種最簡(jiǎn)單的、容易理解的基于運(yùn)算符優(yōu)先級(jí)的算法來(lái)完成這個(gè)任務(wù)。
基于運(yùn)算符優(yōu)先級(jí)的算法叫做 Precedence Climbing，它本質(zhì)上是一種遞歸下降解析表達(dá)式的方法，通過(guò)遞歸地處理運(yùn)算符和操作數(shù)來(lái)解析表達(dá)式，并根據(jù)運(yùn)算符的優(yōu)先級(jí)和結(jié)合性來(lái)確定表達(dá)式的計(jì)算順序。
這種算法的核心思想是利用運(yùn)算符的優(yōu)先級(jí)進(jìn)行“爬升”（Climbing），以決定表達(dá)式的結(jié)構(gòu)和計(jì)算順序。
首先我們做一些約束，由于運(yùn)算符眾多，我們可以支持幾種最常用的：
并且我們知道，冪運(yùn)算的優(yōu)先級(jí)是最高的，其次是 * 和 /，優(yōu)先級(jí)最低的是 + 和 -。所以約定其運(yùn)算符的優(yōu)先級(jí)分別為 3（^）、2（* /）、1（+ -）
2 + 3 ^ 2 * 3 + 4|---------------| : prec 1 |-------| : prec 2 |---| : prec 3約定優(yōu)先級(jí)的主要作用是在計(jì)算的時(shí)候，需要根據(jù)優(yōu)先級(jí)來(lái)確定計(jì)算的順序。
確定了優(yōu)先級(jí)的問(wèn)題，第二個(gè)問(wèn)題是結(jié)合性，運(yùn)算符的結(jié)合性其實(shí)也是確定的，例如加法是左結(jié)合的，這意味著 2 + 3 + 4 等價(jià)于 (2 + 3) + 4，而冪運(yùn)算是右結(jié)合的，這意味著 2 ^ 3 ^ 4 實(shí)際上等價(jià)于 2 ^ (3 ^ 4)。
最后還需要注意一個(gè)問(wèn)題，那就是子表達(dá)式，也就是用括號(hào)包裹的部分，這部分實(shí)際上是需要單獨(dú)進(jìn)行計(jì)算的，并且比運(yùn)算符的優(yōu)先級(jí)更高。
其實(shí)也很容易理解，比如 2 * (3 + 5) * 7，盡管 * 的優(yōu)先級(jí)比 + 高，但是需要先計(jì)算括號(hào)內(nèi)的部分。
確定了這些需求，我們?cè)賮?lái)看如何用 Rust 代碼來(lái)進(jìn)行實(shí)現(xiàn)。
首先我們需要將表達(dá)式進(jìn)行解析，也就是詞法分析的階段，將一個(gè)表達(dá)式解析為不同的 Token，下面是約定的幾種 Token：
// Token 表示，數(shù)字、運(yùn)算符號(hào)、括號(hào)#[derive(Debug, Clone, Copy)]enum Token { Number(i32), Plus, // 加 Minus, // 減 Multiply, // 乘 Divide, // 除 Power, // 冪 LeftParen, // 左括號(hào) RightParen, // 右括號(hào)}然后定義了一個(gè) Tokenizer 結(jié)構(gòu)體，主要是利用 Peekable 接口將表達(dá)式解析為不同的 Token：
// 將一個(gè)算術(shù)表達(dá)式解析成連續(xù)的 Token// 并通過(guò) Iterator 返回，也可以通過(guò) Peekable 接口獲取struct Tokenizer<'a> { tokens: Peekable<Chars<'a>>,}然后自定義實(shí)現(xiàn)了一個(gè) Iterator，讓解析后的 Token 可以通過(guò)迭代器進(jìn)行返回。
impl<'a> Iterator for Tokenizer<'a> { type Item = Token; fn next(&mut self) -> Option<Self::Item> { // 消除前面的空格 self.consume_whitespace(); // 解析當(dāng)前位置的 Token 類型 match self.tokens.peek() { Some(c) if c.is_numeric() => self.scan_number(), Some(_) => self.scan_operator(), None => return None, } }}假如我們的表達(dá)式是 2 + 3 ^ 2 * 3 + 4，實(shí)際上解析后的 Token 就是：
Token::Number(2)Token::PlusToken::Number(3)Token::PowerToken::Number(2)Token::MultiplyToken::Number(3)Token::PlusToken::Number(4)拿到 Token 之后，進(jìn)入到了語(yǔ)法分析的階段，需要根據(jù)每個(gè)表達(dá)式的含義，以及其優(yōu)先級(jí)，計(jì)算對(duì)應(yīng)的結(jié)果。
首先定義一個(gè)方法，計(jì)算單個(gè) Token 以及子表達(dá)式，這只存在兩種情況，分別是 Number 這個(gè) Token，以及帶括號(hào)的子表達(dá)式。
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); } // 如果是左括號(hào)的話，遞歸計(jì)算括號(hào)內(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(), )) } } }這里其實(shí)比較好理解，如果是 Number 直接返回，如果是子表達(dá)式，則重新調(diào)用計(jì)算表達(dá)式的方法進(jìn)行計(jì)算。
然后是另一個(gè)核心的方法計(jì)算表達(dá)式：
fn compute_expr(&mut self, min_prec: i32) -> Result<i32> { // 計(jì)算第一個(gè) 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 一定是運(yùn)算符 // 2. Token 的優(yōu)先級(jí)必須大于等于 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(); // 遞歸計(jì)算右邊的表達(dá)式 let atom_rhs = self.compute_expr(next_prec)?; // 得到了兩邊的值，進(jìn)行計(jì)算 match token.compute(atom_lhs, atom_rhs) { Some(res) => atom_lhs = res, None => return Err(ExprError::Parse("Unexpected expr".into())), } } Ok(atom_lhs)}這個(gè)方法中核心的邏輯可以分幾個(gè)步驟來(lái)理解：
一是使用了 min_prec 參數(shù)控制當(dāng)前層級(jí)的優(yōu)先級(jí)，如果表達(dá)式的優(yōu)先級(jí)小于 min_prec 則直接跳出循環(huán)，返回當(dāng)前的值。
比如 2 * 3 + 4，* 會(huì)先解析到，然后 + 運(yùn)算符的優(yōu)先級(jí)明顯比 * 更低，會(huì)直接返回當(dāng)前值 3。
二是如果運(yùn)算符的結(jié)合性是左邊的話，則下一次迭代的 min_prec 需要遞增。
比如表達(dá)式是 2 * 3 * 4，解析到第二個(gè) * 的時(shí)候，* 的優(yōu)先級(jí)本來(lái)是 2，但它是左結(jié)合的，所以此時(shí) min_prec 是 3，會(huì)直接跳出循環(huán)，所以實(shí)際上會(huì)先計(jì)算 2 * 3。
最后是得到了運(yùn)算符兩邊的值，就可以進(jìn)行計(jì)算了，這里是根據(jù)運(yùn)算符的實(shí)際含義來(lái)進(jìn)行的：
// 根據(jù)當(dāng)前運(yùn)算符進(jìn)行計(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ùn)算符優(yōu)先級(jí)來(lái)進(jìn)行表達(dá)式計(jì)算的整體流程，這個(gè)算法看起來(lái)還是非常簡(jiǎn)潔優(yōu)雅的，非常巧妙的利用優(yōu)先級(jí)來(lái)解決運(yùn)算的順序和結(jié)合等問(wèn)題。
完整的代碼也只有 200 多行，比較適合用來(lái)練手，通過(guò)這個(gè)項(xiàng)目，可以學(xué)習(xí)到：
本文鏈接：http://www.tebozhan.com/showinfo-26-86686-0.html太優(yōu)雅了！Rust 200 行代碼實(shí)現(xiàn)表達(dá)式解析
聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。郵件：2376512515@qq.com
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請(qǐng)聯(lián)系：2376512515@qq.com 津ICP備18001702號(hào)
津公網(wǎng)安備 12010102000574號(hào)