基于堆栈的四则运算总结及优化
2017-12-28郭晓颖陈勇涛叶中华陶慧杰河北农业大学信息科学与技术学院
郭晓颖 陈勇涛 叶中华 陶慧杰 河北农业大学信息科学与技术学院
基于堆栈的四则运算总结及优化
郭晓颖 陈勇涛 叶中华 陶慧杰 河北农业大学信息科学与技术学院
本文用c语言对算数表达式进行分析与设计，该算法可以实现整数，浮点数，带括号的加、减、乘、除四则运算。四则表达式的算法实现是堆栈的典型应用，在此基础上，首先介绍分析后缀的计算，进而然后介绍中缀的两类算法，基于优先级表的后缀转中缀算法、基于优先级表的边扫描边计算法以及优化过后的加二法。
算数表达式 算法 栈 括号
算数表达式由操作数，运算符和分界符构成，可以用中缀和后缀表达式来表示。中缀中的运算符位于两个操作数之间，后缀的运算符位于操作数之后。中缀与后缀表达式的操作数的先后次序完全一样，但运算符的先后次序不一致，后缀中没有括号，后缀的运算顺序就是其执行顺序。
1 后缀表达式的实现算法
算法流程：
（1）建立数据栈
（2）扫描后缀表达式，判断扫描到的符号，如果后缀表达式遍历完毕，转到5）
（3）如果符号为操作数，进栈
（4）如果符号是运算符，判断栈是否为空，为空，转到5），否则取出数据栈栈顶元素，进行计算，运算结构入栈。转到2）
（5）算法结束
2 中缀表达式的实现算法
2.1 利用中缀转后缀的算法实现
算法流程：
（1）建立符号栈
（2）扫描中序表达式 ，判断扫描到的符号
I:如果扫描到的是操作数， 直接输出
II:如果扫描到的是运算符，判断运算符
i : ‘(‘ 直接入栈
ii : ‘)’ 将符号栈中的元素依次出栈并输出 , 直到 ‘(‘, ‘(‘只出栈, 不输出
iii: 如果是其他的运算符, 将符号栈中的元素依次出栈并输出,直到遇到’(‘或者比当前符号优先级更低的符号， 将这个操作符入栈。
（3）扫描完后, 将栈中剩余符号依次输出
2.2 利用优先级表实现
算法实现：
直接用中缀表达式求解需要两个栈，一个是用于存放操作数的“数字”栈，一个是用于存放运算符的“符号”栈。从左到右扫描表达式
I:如果遇到的是数字直接进数字栈
II:如果扫描到的是运算符,拿此运算符和符号栈顶的运算符进行比较
i:若这个符号的优先级大，则把这个符号进符号栈，继续扫描
ii:若小于从数字栈中连续出栈两个操作数，在从符号栈出栈一个符号，在把刚从符号栈出栈的运算符和刚从数字栈出栈的两个操作数进行运算，将运算结果放到数字栈，然后，在把扫面到的运算符和栈顶比较。
iii:若相等则从符号栈出栈一个，继续扫描
III:当扫描到表达式结尾时，若符号栈不空，则从数字栈中出栈两个，从符号栈出栈一个，将运算结果放到数字栈，知道符号栈为空，此时数字栈的栈顶就是表达式的值
2.3 优化加二法
算法流程：
（1）遍历中缀表达式，初始化+，-优先级为1，乘除优先级为2，（优先级变量为temp即当前优先级加2，）为temp当前优先级减2
（2）扫描到的当前符号为运算符
I:当前运算符的优先级为当前优先级变量temp=temp+grade
II：如果是第一个运算符，将当前运算符和优先级无条件入栈，转到4）
III:否则，取出当前栈顶的运算符及其优先级，判断当前扫描到的运算符和栈顶运算符的优先级
IV:若当前扫描到的运算符优先级高，将当前运算符及其优先级入栈，转到4）
V:若取出的栈顶运算符的优先级高，接连取出数据栈的栈顶元素及其符号栈的栈顶元素，进行运算，结果保存到数据栈。计算完毕，取出符号栈的栈顶元素，如果是’#’，循环结束,否则转到V，继续循环。
VI：将扫描到的元素及其优先级入栈
（3）扫描到的当前符号为操作数，将操作数入栈
（4）扫描下一个符号，转到1），若扫描完毕，转到5)
（5）中缀表达式遍历完毕
i:将数据栈栈顶元素依次出栈(两次),将符号栈栈顶元素出栈，计算结果压入数据栈，取出当前符号栈栈顶元素，若是’#’，循环结束，转到ii）否则，转到i）继续执行
ii）取出数据栈栈顶元素即为所求
该算法巧妙之处在于，对于括号的处理，加二法省去了优先级表的构造，仅仅利用一个变量temp加减2判定出了优先级，遇’(’temp加2，遇’)’temp减2，实现了在’(‘括号中的运算符比括号外的运算符高，遇到’)’，temp减2，运算符恢复原优先级。
3 总结
本文主要对优化的加二法进行阐述，体现出算法在设计时的精巧，三类算法的时间复杂度都是O(N)，不过在大部分计算器应用中，采用后缀表达式的算法，该算法省去了优先级的判断，将算法时间集中在了运算上，更加符合计算器特点。在日常计算中，人们往往喜欢带上括号运算，便于理解与交互，中缀表达式的优化运算也是很重要。
[1]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，1997
[2]周桂红.数据结构 1版[M].北京：北京邮电大学出版社，2010
