关于数据结构中的算术表达式
我想大家如果学习了数据结构,当然会知道算术表达式求值,意思就是给个表达式,要你给出结果,编程实现比如:(3+5)^2-3*4-5/3的结果,当然结果是50,如果你算出的结果是50.333333,那么你的算法不错啦!我在这个版块中看到有人再发帖讨论算术表达式的求值方法,我下面告诉大家如何求去表达的值,可能我的解法不是很好!
下面我详细的讲求值的几个步骤:
1.把中缀表达式转换为前缀表达式(或者后缀)
2.按照优先级出栈运算
大家可能会问什么事中缀表达式,这个大家可以百度或者谷歌,我这里简要的讲下,中缀表达式即是我们日常的算术表达式,为什么在求值的过程中我们要把中缀表达式转换为前缀表达式,那是因为计算机他不懂我们写的表示,但是如果用后缀表达式,按照一定的运算,计算机就能读懂.
a.中缀表达式转换为前缀表达式的一般算法
(1) 首先构造一个运算符栈(也可放置括号),运算符(以括号分界点)在栈内遵循越往栈顶优先级不降低的原则进行排列。
(2)从右至左扫描中缀表达式,从右边第一个字符开始判断:
如果当前字符是数字,则分析到数字串的结尾并将数字串直接输出。
如果是运算符,则比较优先级。如果当前运算符的优先级大于等于栈顶运算符的优先级(当栈顶是括号时,直接入栈),则将运算符直接入栈;否则将栈顶运算符出栈并输出,直到当前运算符的优先级大于等于栈顶运算符的优先级(当栈顶是括号时,直接入栈),再将当前运算符入栈。
如果是括号,则根据括号的方向进行处理。如果是右括号,则直接入栈;否则,遇左括号前将所有的运算符全部出栈并输出,遇左括号后将左右的两括号一起删除。
(3) 重复上述操作(2)直至扫描结束,将栈内剩余运算符全部出栈并输出,再逆缀输出字符串。中缀表达式也就转换为前缀表达式了。
b.当我们得到这样的最缀表达式的时候,这个时候离结果只差一步之遥了,求值的方法如下:
(1)从表达式最后取值(如果是后缀从前面取值),判断是数字还是运算符,如果是数字压入数据栈,是运算符依次出栈数据栈里的两个元素,按照运算符进行运算,把结果计算的结果再次压入数据栈,直到表达式的每个元素取完为止.
最后的结果就是栈底元素的值.
这是我写的一个欢迎大家指正缺点和不足,写的实在不好,不好意思贴上源码,如果需要学习的童鞋,评论中说要源码我马上上传! 有点牛逼啊 我这运行后显示Expression.exe-无法找到组件,没有找到MSVCR100D.dll,因此这个应用程序未能启动。重新安装应用程序可能会修复此问题。
请问此结果如何解决,谢谢
页:
[1]