中缀算术表达式的轻量化求值算法  

Lightweight evaluation algorithm for infix arithmetic expression

作　　者：白宇[1] 郭显娥[1] 

机构地区：[1]山西大同大学数学与计算机科学学院,山西大同037009

出　　处：《计算机应用》2013年第11期3163-3166,共4页journal of Computer Applications

摘　　要：针对当前中缀算术表达式求值算法笨重或者复杂的问题,提出了一种轻量化的中缀算术表达式求值算法。该算法基于逆向拆分中缀算术表达式的思路,使用递归解析的方法,等价于中缀算术表达式的构造二叉树表示。实验结果表明,该算法与传统逆波兰表达式(RPN)转换、求值算法相比,该算法无需做逆波兰表达式转换,无需人工栈辅助,实现代码量仅有其1/6,而效率仅下降6.9%。与W3Eval算法相比,该算法无需符号转置表,支持算符自定义或重定义,实现代码量不到其1/2。该算法实现代价低,适用于Web应用的Browser端,及嵌入式应用等轻量化应用场合。Concerning the bulky or complex current evaluation algorithm of infix arithmetic expression, a lightweight evaluation algorithm for infix arithmetic expression was proposed. The algorithm was based on the idea of the reverse split infix arithmetic expression, using the method of reeursive analysis, equivalent to infix arithmetic expressions of constructing binary tree. The experimental results show that compared with the algorithm of traditional Reverse Polish Notation （RPN） transformation and evaluation, the proposed algorithm did not need to do RPN transform and assist of hand-operated stack, its amount of code was only 1/6 of RPN transformation, and the efficiency declined by only 6.9%. To compared with W3Eval algorithm, it did not need to use transpose table of symbol, supporting define or redefine of operator, and its amount of code was less than half of W3Eval algorithm. The algorithm demands low-cost implementation, and it is suitable for lightweight aoolications such as browser-side of Web aoDlications and embedded aoolications.

关 键 词：轻量化算法 中缀算术表达式 逆向拆分 逆波兰表达式 W3Eval 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]