计算机应用 ›› 2013, Vol. 33 ›› Issue (11): 3163-3166.

• 先进计算 • 上一篇    下一篇

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

白宇,郭显娥   

  1. 山西大同大学 数学与计算机科学学院,山西 大同 037009
  • 收稿日期:2013-05-13 修回日期:2013-07-15 出版日期:2013-11-01 发布日期:2013-12-04
  • 通讯作者: 白宇
  • 作者简介:白宇(1976-),男,山西大同人,讲师,硕士,主要研究方向:图论算法、并行算法、云计算;郭显娥(1964-),女,山西大同人,教授,主要研究方向:概念格、数据挖掘、知识发现。

Lightweight evaluation algorithm for infix arithmetic expression

BAI Yu,GUO Xiane   

  1. School of Mathematics and Computer Science, Shanxi Datong University, Datong Shanxi 037009, China
  • Received:2013-05-13 Revised:2013-07-15 Online:2013-12-04 Published:2013-11-01
  • Contact: BAI Yu

摘要: 针对当前中缀算术表达式求值算法笨重或者复杂的问题,提出了一种轻量化的中缀算术表达式求值算法。该算法基于逆向拆分中缀算术表达式的思路,使用递归解析的方法,等价于中缀算术表达式的构造二叉树表示。实验结果表明,该算法与传统逆波兰表达式(RPN)转换、求值算法相比,该算法无需做逆波兰表达式转换,无需人工栈辅助,实现代码量仅有其1/6,而效率仅下降6.9%。与W3Eval算法相比,该算法无需符号转置表,支持算符自定义或重定义,实现代码量不到其1/2。该算法实现代价低,适用于Web应用的Browser端,及嵌入式应用等轻量化应用场合。

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

Abstract: 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 recursive 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 applications such as browser-side of Web applications and embedded applications.

Key words: lightweight algorithm, infix arithmetic expression, reverse split, Reverse Polish Notation (RPN), W3Eval

中图分类号: