基于堆栈的计算器实现算法

基于堆栈的计算器实现算法

运算符的优先级

对于计算器，有很多成熟的理论。本文章讨论的是利用一个操作数堆栈和一个运算符堆栈进行运算的方法。这种算法已经有很完善的解决方案，此处讨论的是最简化的模型，旨在让初学者在最短的时间内学到此算法的精髓，并能灵活的应用到科研的任何一个领域。

简单表达式的计算

首先请看这个表达式：

3＋5＋6＊7＊8＾2＾3 （8＾2指的是82）

这里运算有三种优先级“＾”--＞

“＊”--＞“＋”，如何实现优先级运算呢？

当扫描字符串3＋5＋6＊7＊8＾2＾3的时候。

1.先移进3＋5，发现下一个运算符是＋，优先级与上一个相同，于是就先计算3＋5，将它们改为8。于是式子变为：8＋6＊7＊8＾2＾3

2.现在下一运算符＊优先级比上一个＋要高，于是继续前移：8＋6

＊7＊8＾2＾3

3.现在下一个运算符是＊，与上一个相同，于是先计算6＊7，式子变为：8＋42＊8＾2＾3

4.继续：8＋42＊8＾2＾3

5.8＋42＊64＾3

6.8＋42＊262144

7.8＋1．101＊107

8.1．101＊107

现在式子变成一个数，整个运算也就结束了。

但怎样在计算机中完成这个过程呢？当遇到8＋6＊7时必须先运算6＊7，但这时8和＋保存在哪里呢？这里使用的方法是：建立一个操作数堆栈和一个运算符堆栈，把8和＋分别压到两个堆栈中。

对于式子：3＋5＋6＊7-8＾2

剩余式子操作数堆栈运算符堆栈优先级比较操作

3＋5＋6＊7-8＾2

±6＊7 -8＾2 3，5 ±相等计算3＋5＝8

＋6＊7-8＾2 8

＊7 -8＾2 8，6 ±大于

-8＾2 8，6，7 ＋，＊小于计算6＊7＝42

-8＾2 8，42 ＋等于计算8＋42＝50

-8＾2 50

＾2 50，8 - 大于

50，8，2 -，＾计算8＾2＝64 50，64 - 计算50-64＝-14

-14 ＾

--------------------------------------------------------------------------------------------------------------

可以看出，如果利用操作数堆栈和运算符堆栈的话，只要：

1．步进扫描表达式。

2．遇到操作数就压入操作数堆栈中，遇到运算符就将它的优先级与运算符堆栈栈顶运算符的优先级比较，如果它的优先级更大，就将它压入堆栈，否则就将栈顶运算符弹出来进行运算。

只要这样就可以实现优先级的运算。

优先级的改变

在我的示例程序中规定了3种优先级

＋、-、自反运算（-x，-y，-z，-1，-2）

：优先级为

1（较低）

＊、／：优先级为2

＾：优先级为3（最高）

但“（”的优先级应该是多少，括号指的是开始一个新的运算，对于3＋5＊（6-2），当扫描到“（”时，原先的

优先级就全部失效了，一切需要重新计算，因此扫描时遇到“（”，就将它无条件压入栈中，同时置最低优先级-

1。与此操作相同的还有“sin（”、“cos（”、“tan（”、“tg（”、“lg （”、“ln（”等.

遇到“）”，就应该不停出栈运算直至找到“（”、“sin（”、“cos（”、“tan（”、“tg（”、“lg（”、“ln（”等。

程序流程

对于一个合法的简单数学表达式，肯定是一个操作数跟着一个运算符，

第一个和最后一个都是操作数。因此最简单的程序编写方法就是写一个取操作数的程序CCalc：：GetOperand（），再写一个取运算符的程序CCalc：：GetOperator（），然后循环执行。

while(!GetOperand()&&!GetOperator()&&!vError);

这样就可以计算出最终的结果。

1．取操作数GetOperand（）：

（1）取操作数时首先遇到的不一定就是操作数本身，而可能是“（”、“sin（”、“cos（”、“tan（”、“tg（”、“lg（”、“ln（”或自反运算符“-”或无意义的“＋”号，首先将它们压入运算符栈中。

（2）然后检查是不是“x”、“y”、“z”等变量或“PI”等常量，有的话将它们的值压到操作数栈中。

（3）如果不是变量或常量，则检查数的合法性，如果不是合法数，就退出全部运算。

2．取运算符GetOperator（）：

（1）取运算符时首先遇到的不一定就是运算符，而可能是“）”，先要对它进行处理。

（2）然后检查是不是扫描到了最后，如果是就清栈输出结果。（3）取出新运算符并给它对应的优先级。

（4）如果运算符堆栈不为空，从中弹出一个运算符，比较优先级，如果新的运算符优先级小于等于弹出运算符优先级，就把弹出运算符重新压回去，否则对弹出运算符进行运算。

（5）将新运算符压入堆栈中。