“四則運算”算法

quasiceo 2017-10-30

展開全文

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

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

4.1 基本概念介紹

4.1.1 中綴表達式與后綴表達式

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

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

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

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

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

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

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

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

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

一個操作符棧 —— 后進先出 LIFO

一個字符隊列 —— 先進先出 FIFO

定義操作符優(yōu)先級

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

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

* / 優(yōu)先級相同，+ - 優(yōu)先級相同

優(yōu)先級： * / > + -；

同一優(yōu)先級(比如 + - )：先進棧 < 后進棧；

井號 # 優(yōu)先級最低

在棧外，左括號 ( 優(yōu)先級最高；在棧內(nèi)，( 優(yōu)先級除井號 # 外最低

總的來說，在棧外 ( > * / > + - > ) > '#'；在棧內(nèi) * / > + - > ) > ( > #

計算后綴表達式，需要

一個操作數(shù)棧 —— 后進先出 LIFO

一個字符隊列 —— 先進先出 FIFO

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

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

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

主要的過程為：

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