基于堆栈的计算器实现算法
对于计算器,有很多成熟的理论。本文章讨论的是利用一个操作数堆栈和一个运算符堆栈进行运算的方法。这种算法已经有很完善的解决方案,此处讨论的是最简化的模型,旨在让初学者在最短的时间内学到此算法的精髓,并能灵活的应用到科研的任何一个领域。
简单表达式的计算
首先请看这个表达式:
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^23,5±相等计算3+5=8
+6*7-8^28
*7-8^28,6±大于
-8^28,6,7+,*小于计算6*7=42
-8^28,42+等于计算8+42=50
-8^250
^250,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)将新运算符压入堆栈中。
分享到:
相关推荐
堆栈 科学计算器 笔记
Java计算器源码含界面(基于堆栈算法实现) 本程序适合初学者练习使用。尤其是对栈算法的学习及有好处
C++利用堆栈实现计算器,设置优先级控制符号运算顺序,可以实现长的表达式计算
自己写的堆栈计算器,支持各级运算,括号等,采用边计算边压栈的算法,请指教,谢谢 DEVC++
C语言实现的堆栈计算器,通过输入整个算式进行计算,并且对简单错误进行判断输出,可识别括号等特殊符号。
堆栈实现后缀表达式算法,在winform基础上实现后缀表达式计算器
本文实例讲述了PHP基于堆栈实现的高级计算器功能。分享给大家供大家参考,具体如下: 当我们得到一个字符串运算式该如何去得出它的运算结果呢? 这时候我们就能使用堆栈的算法很巧妙的解决这个问题。 思路是这样的:...
通过本程序学习堆栈,可以深刻的了解计算器的实现算法。本程序在vs2010环境下调试成功。
一个用c语言实现的计算器,计算复合运算,其中用到了堆栈的算法。
在计算器用到的算法中,c语言算法可读性很强,一方面,是因为c语言是高级语言,是面向程序员的语言,二是c语言的功能是很完备的,可以达到事半功倍的效果,和其他语言相比量是比较少。栈的应用使该程序更出色。 ...
一个计算器,有多种功能,如取对数、求平方根。最重要的是利用堆栈算法实现运算符优先级。
###本设计运用汇编语言实现了计算器的基本功能,用户可以通过键盘输入包括负数的十进制数字并通过堆栈存储,以及键入“+”、“—”、“*”、“/”四种运算符号形成算式,调用相应算法并进行四则运算,最后显示出运算...
用linearLayout布局的简单计算器,实现了加减乘除的计算。没有用到堆栈,用了自己的算法。
数据结构课程设计报告 实验一:计算器 设计要求 1、问题描述:设计一个计算器,可以实现计算器的简单运算,输出并检验结果的 正确性,以及检验运算表达式的正确性。 2、输入:不含变量的数学表达式的中缀形式,可以...
该算法可以实现操作符优先级的判定,是非常好的算法。包括了对堆栈的操作
后缀符号计算器*此后缀表示法计算器可以在输入后输入后缀表示法时计算数字。 P2vivekraj
主要是考虑符号的优先级,然后配对和消除,使用堆栈来处理。算法描述如下: 建立两个动态栈A,B。A存放计算对象,B存放计算符号。 三、设计要求与内容 ................... 一、设计的内容及要求 编写时钟程序,...
这个小程序采用网格包布局,堆栈算法,正则表达式,代码量也不是很多,差不多350左右,看看吧
演示了一个利用堆栈作的RPN计算器2. 排序表。演示了一个利用排序表做的多项式表达式的加法运算3. 广义树。演示了深度遍历和广度遍历4. N叉树。演示了N叉树的生成插入删除等基本操作5. 表达式树。演示了一个用...