基于单链表的显示全计算过程计算器的设计

张慧宁

摘要：该文对过程全显示计算器的算法进行分析和探讨，采用单链表实现显示计算全过程的计算器。该计算器通过词法和语法分析，对数据和运算符分别进行拆分并存储于单链表中，采用递归运算，得到计算过程，运算后遍历输出，直至得到最终结果。支持的运算功能有：四则运算、括号运算、幂运算等。过程全显示计算器解决了常见计算器只能显示计算结果的问题。

关键词：全计算过程显示；计算器；单链表；算法；递归

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）34-0097-02

Abstract： In this paper ，we analyzed and discussed the calculators algorithm， using single table show the whole process of calculator to calculate. The calculator， the data and operator split respectively and stored in a single table by lexical and syntax analysis， using recursive algorithm， get the calculation process， then operation after traversal output， until get the final result. Support operation function are： arithmetic， bracket operation， power operation， etc. Process all the calculator have solved the problem of common calculator can only display results.

Key words： show the whole calculate process； calculator； single table； algorithm； recursive

1概述

计算器是生活和办公中最常用的工具之一，有着强大的计算功能以及便携等特性，使用场所非常广泛。目前市面上流通的计算器绝大部分都只能显示计算结果，对于计算过程的描述不做显示，对使用造成很多不便。为此，本文基于单链表对现有计算器进行改进，使其能显示每一步的计算过程，解决了计算器只能显示计算结果问题。

2 设计思想

系统首先对输入的计算过程进行词法分析，其任务是从左到右逐步扫描计算过程，并将其独立拆分为一个个具有完整意义的数据（1、2、3……等）、运算符（+、-、*、/、（）、[]等）。

其次，系统对拆分出来的数据进行语法分析。在这一步，系统在词法分析的基础上，对拆分出来的数据和运算符进行语法分析，主要功能是，判断输入数据是否合法（是否包含字母、中文等非法数据），判断运算符运用是否合理，是否有出现类似++、--、[+]等错误使用运算符情况，如无误，将数据和运算符依次存出单链表中。

最后，在保证语法无误后，遍历链表，判断运算符优先级，根据运算符优先级进行计算，并将结果存放回链表，单步遍历运算后得到的链表并输出单步计算结果，显示单步计算后的表达式信息，通过递归这一操作，直至运算符数目为0，则此步骤为最终结果，同时得到所有运算过程。

3 系统具体实现

3.1系统主要功能

计算器的主要功能如下：

运算表达式语法错误与否判断：如1+1、3*8、（20+10）^2等为正确表达式，可正常往下运行；而对于（*1）、^2+3、1+++5等则为错误表达式，计算器会提示用户输入运算表达式错误，要求用户重新输入。

基本四则运算：如+、-、*、/ 等。

指数幂运算等：主要是次方（^）、二次方根（$）等。

括号运算：（）。

3.2词法分析设计

词法分析从左到右依次扫描运算表达式，将表达式切割为数据和运算符，主要步骤如下：读取第一位字符，判断数据还是表达式；接着读取第二位，判断数据还是表达式，如果跟前一位类型相同，则继续读取下一位字符，直至后一位同前一位不同为数据或表达式，切割，存入单链表，然后继续从下一位字符开始进行递归操作，直至结束。流程图如下：

3.3语法分析设计

语法分析遍历单链表，依次判断表达式是否符合语法，若不符合，反馈错误信息。具体步骤如下：

1）判断第一位是否为符号，若是，则错误，反馈错误信息，否则，继续；

2）判断是否出现双符号或者多符号，若出现，则错误，返回错误信息，否则，继续；

3）判断最后一位是否为符号位，所是，则错误，反馈错误信息，否则，结束。

流程图如图3。

3.4运算符优先级判定及计算输出设计

运算符优先级判定主要是根据数学运算规则对运算符优先级进行判定，并根据高优先级先运算原则进行运算。运算符优先级定义如下：

^、$为第一级运算符；

（）、[]为二级运算符；

*、/为三级运算符；

+、-为四级运算符；

运算时，先判定是否有上一级运算符，如有，则先计算上一级运算符，并将上一级运算符计算所得结果存回单链表中，然后遍历输出，递归执行，直至运算符数目为0，所得结果即为最终结果。具体如下：

遍历整个单链表，判断是否有第一级运算符，如有，则进行第一级运算符运算，得到运算结果，假设运算符所在位置为N，则将结果保存到N-1节点中，接着删除N、N+1节点，遍历链表并输出，得到一级运算符计算过程。

重复步骤，依次判断是否有第二级运算符，第三级运算符，第四级运算符直至运算符数目为空，所得结果即为最终结果，运算结束。具体流程图如下：

5 结论

本文基于常用的数据结构单链表，拓展生活中最常用的计算器的功能，使其能显示计算过程，虽然其目前功能较为简单，但由于其基于词法分析，较容易拓展。由于使用单链表结构，没有运算字符上限，较为实用。

参考文献：

[1] Cormen T H，Leiserson C E，Rivest R L，ed al.算法导论[M].3版.北京：机械工业出版社，2012.

[2] 严蔚敏.数据结构[M].2版.北京：清华大学出版社，2008.

[3] 戴建国.递归算法应用分析[J].软件设计开发，2008（28）.

[4] 张耀民.递归法在程序设计中的应用与分析[J].设计研发，2013（13）.

[5] 黎远松.基于树的递归算法分析技术[J]. 四川理工学院学报：自然科学版， 2012（4）.