四、“四則運(yùn)算”算法基礎(chǔ)知識

數(shù)學(xué)意義上，加減乘除運(yùn)算被稱為“四則運(yùn)算”，如1+2*3-4，“四則運(yùn)算”算法主要分兩步：第一步是中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式，第二步是計(jì)算后綴表達(dá)式得到結(jié)果。

4.1 基本概念介紹

4.1.1 中綴表達(dá)式與后綴表達(dá)式

一般情況下，四則運(yùn)算的表達(dá)式為中綴表達(dá)式，比如表達(dá)式 A+(B-C/D)*E，該表達(dá)式的中綴表達(dá)式與后綴表達(dá)式如下：

• 中綴表達(dá)式：A+(B-C/D)*E
• 后綴表達(dá)式：ABCD/-E*+

中綴表達(dá)式將操作符置于兩個(gè)操作數(shù)中；后綴表達(dá)式將操作符置于兩個(gè)操作數(shù)之后；另外，后綴表達(dá)式已經(jīng)去除括號，并且定義了運(yùn)算的先后順序，稍后我們來分析。

4.1.2 操作符與操作數(shù)

中后綴表達(dá)式中的字符有操作數(shù)和操作符之分：

• 操作符：表達(dá)式中的 +-*/()（稍后運(yùn)算用到的#符號也是）
• 操作數(shù)：表達(dá)式中的 ABCDE

也就是說，我們將加(+)、減(-)、乘(*)、除(/)、和括號("()")稱作操作符，將運(yùn)算的字符A、B、C、D、E稱作操作數(shù)。

4.1.3 棧、隊(duì)列與操作符優(yōu)先級

將中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式，需要

• 一個(gè)操作符棧 —— 后進(jìn)先出 LIFO
• 一個(gè)字符隊(duì)列 —— 先進(jìn)先出 FIFO
• 定義操作符優(yōu)先級

其中，操作符棧 存儲(chǔ)操作符，并對操作符進(jìn)行入棧出棧操作；字符隊(duì)列存儲(chǔ)轉(zhuǎn)換前后的表達(dá)式；操作符優(yōu)先級定義了棧內(nèi)以及棧外各個(gè)操作符的優(yōu)先級。

操作符優(yōu)先級規(guī)則如下：

• * / 優(yōu)先級相同，+ - 優(yōu)先級相同
• 優(yōu)先級： * / > + -；
• 同一優(yōu)先級(比如 + - )：先進(jìn)棧 < 后進(jìn)棧；
• 井號 # 優(yōu)先級最低
• 在棧外，左括號 ( 優(yōu)先級最高；在棧內(nèi)，( 優(yōu)先級除井號 # 外最低
• 總的來說，在棧外 ( > * / > + - > ) > '#'；在棧內(nèi) * / > + - > ) > ( > #

計(jì)算后綴表達(dá)式，需要

• 一個(gè)操作數(shù)棧 —— 后進(jìn)先出 LIFO
• 一個(gè)字符隊(duì)列 —— 先進(jìn)先出 FIFO

4.2 中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式的過程

4.2.1 轉(zhuǎn)換過程流程圖

圖18：中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式過程

主要的過程為：

• 循環(huán)讀取表達(dá)式字符隊(duì)列的字符
  
  • 如果是操作數(shù)
    
    • 直接入隊(duì)列
  • 如果是操作符
    
    • 如果是 ")" 操作符
      
      • 棧頂元素出棧，入隊(duì)列，直到遇到第一個(gè) “(”
      • 如果還沒讀取到 ”(“，就已經(jīng)讀到了 "#"，說明表達(dá)式左括號和右括號不匹配
    • 否則，如果是 “(” 操作符
      
      • 直接入棧
    • 否則，比較指針讀取的當(dāng)前操作符，與棧頂操作符的優(yōu)先級
      
      • 如果當(dāng)前元素 <= 棧頂元素
        
        • 棧頂元素出棧，入隊(duì)列
        • 直到遇到優(yōu)先級 > 當(dāng)前元素的棧頂單詞，或者遇到“#”，當(dāng)前元素入棧
      • 否則，（當(dāng)前元素優(yōu)先級 > 棧頂元素）當(dāng)前元素入棧
  • 當(dāng)隊(duì)列讀取到末尾，棧中所有元素依次出棧，并入隊(duì)列（#也入隊(duì)列）

4.2.2 轉(zhuǎn)換過程詳細(xì)示例

表達(dá)式 A+(B-C/D)*E 中綴轉(zhuǎn)后綴流程參見如下 PPT 演示：中綴轉(zhuǎn)后綴流程

4.3 計(jì)算后綴表達(dá)式過程

4.3.1 計(jì)算過程流程圖

圖19：計(jì)算過程流程圖

主要的過程為：

• 循環(huán)讀取表達(dá)式字符隊(duì)列的字符
  
  • 如果是操作數(shù)（不是操作符）
    
    • 直接入棧
  • 否則是操作符
    
    • 棧頂彈出兩個(gè)操作符，做四則運(yùn)算，結(jié)果重新入棧
  • 如果遇到隊(duì)列尾，結(jié)束

4.3.2 計(jì)算過程示例

表達(dá)式 ABCD/-E*+ 計(jì)算后綴表達(dá)式流程參見如下 PPT 演示：計(jì)算后綴表達(dá)式流程

4.4 簡單示例

下面演示一個(gè)簡單的示例，演示通過中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式，并計(jì)算后綴表達(dá)式來計(jì)算 1+(3-4/2)*5 的過程：

表達(dá)式 1+(3-4/2)*5 中綴轉(zhuǎn)后綴流程參見如下 PPT 演示：中綴轉(zhuǎn)后綴示例

表達(dá)式 1342/-5*+ 計(jì)算后綴表達(dá)式流程參見如下 PPT 演示：計(jì)算后綴表達(dá)式示例