基于双栈结构的中缀表达式算法设计与实现

许晓宇

摘要： 关键词： 中图分类号： 文献标志码： A文章编号： 2095-2163（2017）06-0108-03

Abstract： The conventional algorithm calculating infix expression is to convert infix expressions into postfix expression，which has conversion intermediate process； this paper designs an algorithm based on dual stack structure， according to the inherent human thinking from left to right to directly calculate the infix expression， using only simple singular group to act as a data structure. During the process of the pretreatment， respectively restore the operators into symbol array stack and store values into real array stack. In the next calculation section， with the help of C language powerful circulation control ability， traverse the symbols stack， according to priority push and pop operators， call the real array double stack data in monocular and binocular operation， calculate the deposit， once again store in the top of the stack until the symbol stack is empty. Therefore， real array in the top of the stack is the calculation results. The experimental results show that the algorithm can effectively deal with monocular and binocular calculations， as well as Brackets.

0引言

中缀表达式的求解是算法与数据结构中的经典问题，也是程序设计中的一个不可回避的热点问题，算法的逻辑描述相对简单，但实现起来很多细节处理偏难。对于中缀表达式的算法设计，大致可以分为两类：一类是依据物理计算机固有处理方式的特性去设计算法，另一类是依据人的固有思维习惯去设计算法。

多数学者，都只选择第一类算法[1]，由于计算机擅长处理不带优先级的逆波兰表达式（即后缀表达式），因此，这类算法中对“中缀表达式的求值”问题转换成了两步：第一步将中缀表达式转换成后缀表达式，第二步对后缀表达式的求值计算。在算法设计的过程中，根据具体选择数据结构的不同，又分为基于数组的栈结构实现和基于二叉树的栈结构实现。每种实现又可以引出基于不同的程序设计语言的各种版本的源代码。还有一些学者将中缀表达式转换成前缀表达式[2-3]进行求值。

本文算法则另辟蹊径，选择了依据人的固有思维习惯去设计算法，人类处理算术问题方法就是中缀表示式的直接处理方式，一般是按从左到右的顺序，依据运算符的优先级进行计算。让计算机模拟人类，直接对中缀表达式提供处理，需要从左到右遍历中缀表达式，需要分优先级设计计算，需要一次性直接完成计算[4-5]。但计算机毕竟不是人类，所以就隐含了一定的问题，内容分析如下

1）从键盘或文本输入框中，输入的是字符串，如何变成运算符、数值。

2）优先级的设置能否与人类一样。

3）如何一次性从左到右，直接装入一目、二目运算符如“（、）、+、-、*、/、^、正、负”，并按优先级展开计算。

本文在算法设计时，使用了两个数组栈结构[6-8]：一個放运算符，一个放操作数值，同时在算法的实现方式上用两重循环控制的递推方式替代递归方式，用数组和下标指针的移动替代栈结构栈顶元素的弹出与压入。

1算法描述

1.1对中缀表达式的预处理

优先级次数高低遵循人类的纯粹的数学中的计算优先级，设置的数值越大代表优先级越高，特别“（”入栈前及入栈后略有不同，压栈前“（”优先级最高，压栈后“（” 最低，假定只针对上述运算符，那么优先级设置如表1所示。

1.2计算核心为双重循环控制遍历双栈结构

本文在算法设计时，使用了两个数组充当栈结构[9-10]：一个放运算符，一个放操作数值，同时在算法的实现方式上用两重循环控制的递推方式替代递归方式，用数组和下标指针的移动替代栈结构栈顶元素的弹出与压入。

从左到右依次遍历预处理后的字符串，每次遍历1个，直到遇到“等号”结束。设计解析阐释如下：

1）如果遇到字符串是数值X，那么就压入数值栈内。

2）如果遇到的是运算符，判断栈是否为空：若为空，当前的符号压栈，本次循环结束；否则，将当前的符号，与符号栈内所有的运算符进行循环比较，直到本次循环结束。

若当前的符号是“）”并且符号栈栈顶是“（”，那么直接弹出栈顶“（”，右括号“）”直接丢弃，循环结束。

若当前的符号的优先级小于等于栈顶的运算符，弹出栈顶运算符，同时依据此栈顶运算符的目次，从数值栈内弹出数值进行计算，然后再将计算结果，压入数值栈。继续做当前符号和栈顶元素的判断，直到栈空，将当前符号压入栈内，结束循环。endprint

若当前的符号的优先级大于栈顶运算符直接压栈。

3）如果当前栈不空，则依次弹出栈内运算符，依次计算，栈顶数据[9]为最终计算结果。

2算法实现

2.1數据定义

用户输入的中缀表达式字符串定义为：char origin1[200]；预处理后的标准形式字符串char s[80]；存放运算符的字符数组char fuhao[80]；初次存放临时数值字符串chrar shuzhi[80]，存放操作数数值的双精度数组double num[20]；2个栈顶下标指示器int j，k；

2.2数据的赋值

4结束语

通过实验不难发现本算法计算能力较强，对于人为多重括号的情况、正负号的情况都可以进行良好优化处理，使用数组栈结构，程序的空间效率较高。当然，文中没有过多考虑程序健壮性，比如中缀表达式合法性检查，也未能增加各种进制的转换函数，不能方便进行各种进制的中缀表达式计算。

参考文献：

[1] 胡云，毛万年. 一种将中缀表达式转换为后缀表达式的新方法[J]. 成都大学学报（自然科学版），2008，27（1）：52-55.

[2] 曹晓丽，潘颖. 一种利用栈实现中缀表达式向前缀表达式转换方法的改进[J]. 甘肃科技，2006，22（11）：64-66，38.

[3] 刘任任. 中缀表达式到前缀表达式的快速算法[J]. 湘潭大学自然科学学报，1988，10（4）：96-99.

[4] 李艳玲. 数据结构中实现表达式求值算法的巧妙转换[J]. 职大学报（自然科学版），2005（4）：62-63.

[5] 王迤冉，王华东. 表达式求值的一种实现方法[J]. 周口师范高等专科学校学报，2001，18（2）：31-33.

[6] 王淑礼，王新霞. 算术表达式求值算法实现的难点剖析[J]. 福建电脑，2012，28（3）：55-56.

[7] 李世华，刘晓娟，姜晨，等. 关于表达式求值的算法研究与实现[J]. 甘肃科技，2011，27（1）：11-15.

[8] 兰美辉，杨平. 基于栈结构的算术表达式求值算法研究[J]. 曲靖师范学院学报，2014，33（3）：57-59.

[9] 王红奎，肖荣. 基于栈结构的浮点型数据表达式求值算法[J]. 南昌航空工业学院学报（自然科学版），2004，18（3）：87-89.

[10]李橙，丁国栋. 栈在表达式求值中的应用[J]. 电脑知识与技术，2014，10（34）：8156-8157，8164.endprint