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

Design and implementation of infix expression algorithm based on dual stack structure

作　　者：许晓宇[1] 

机构地区：[1]常州纺织服装职业技术学院,江苏常州213164

出　　处：《智能计算机与应用》2017年第6期108-110,共3页Intelligent Computer and Applications

摘　　要：中缀表达式求解的常规算法是将中缀表达式转换成后缀表达式后计算,存在转换中间过程;本文基于双栈结构设计的一种算法,能按人类固有思维从左到右直接计算中缀表达式,只使用简单数组充当数据结构,预处理时,分别将运算符存入符号数组栈,将数值存入实型数组栈,计算时,借助C语言强大循环控制能力,遍历符号栈,依据优先级压入、弹出运算符,以此来调用实型数组栈顶的单数据、双数据参与单目、双目运算,计算中间结果,再次存入栈顶,直至符号栈为空时,实型数组中的栈顶就是计算结果,实验证明本算法能较好地处理单目、双目、甚至多括号的情况。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.

关 键 词：中缀表达式 预处理 栈结构 循环控制 运算符优先级 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]