“四则运算”算法

quasiceo 2017-10-30

展开全文

四、“四则运算”算法基础知识

数学意义上，加减乘除运算被称为“四则运算”，如1+2*3-4，“四则运算”算法主要分两步：第一步是中缀表达式转后缀表达式，第二步是计算后缀表达式得到结果。

4.1 基本概念介绍

4.1.1 中缀表达式与后缀表达式

一般情况下，四则运算的表达式为中缀表达式，比如表达式 A+(B-C/D)*E，该表达式的中缀表达式与后缀表达式如下：

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

中缀表达式将操作符置于两个操作数中；后缀表达式将操作符置于两个操作数之后；另外，后缀表达式已经去除括号，并且定义了运算的先后顺序，稍后我们来分析。

4.1.2 操作符与操作数

中后缀表达式中的字符有操作数和操作符之分：

操作符：表达式中的 +-*/()（稍后运算用到的#符号也是）
操作数：表达式中的 ABCDE

也就是说，我们将加(+)、减(-)、乘(*)、除(/)、和括号("()")称作操作符，将运算的字符A、B、C、D、E称作操作数。

4.1.3 栈、队列与操作符优先级

将中缀表达式转为后缀表达式，需要

一个操作符栈 —— 后进先出 LIFO

一个字符队列 —— 先进先出 FIFO

定义操作符优先级

其中，操作符栈 存储操作符，并对操作符进行入栈出栈操作；字符队列存储转换前后的表达式；操作符优先级定义了栈内以及栈外各个操作符的优先级。

操作符优先级规则如下：

* / 优先级相同，+ - 优先级相同

优先级： * / > + -；

同一优先级(比如 + - )：先进栈 < 后进栈；

井号 # 优先级最低

在栈外，左括号 ( 优先级最高；在栈内，( 优先级除井号 # 外最低

总的来说，在栈外 ( > * / > + - > ) > '#'；在栈内 * / > + - > ) > ( > #

计算后缀表达式，需要

一个操作数栈 —— 后进先出 LIFO

一个字符队列 —— 先进先出 FIFO

4.2 中缀表达式转后缀表达式的过程

4.2.1 转换过程流程图

图18：中缀表达式转后缀表达式过程

主要的过程为：

循环读取表达式字符队列的字符
- 如果是操作数
  - 直接入队列
- 如果是操作符
  - 如果是 ")" 操作符
    - 栈顶元素出栈，入队列，直到遇到第一个 “(”
    - 如果还没读取到 ”(“，就已经读到了 "#"，说明表达式左括号和右括号不匹配
  - 否则，如果是 “(” 操作符
    - 直接入栈
  - 否则，比较指针读取的当前操作符，与栈顶操作符的优先级
    - 如果当前元素 <= 栈顶元素
      - 栈顶元素出栈，入队列
      - 直到遇到优先级 > 当前元素的栈顶单词，或者遇到“#”，当前元素入栈
    - 否则，（当前元素优先级 > 栈顶元素）当前元素入栈
- 当队列读取到末尾，栈中所有元素依次出栈，并入队列（#也入队列）