鱼C论坛

 找回密码
 立即注册
查看: 3319|回复: 3

[技术交流] 关于数据结构中的算术表达式

[复制链接]
发表于 2013-2-4 23:07:51 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
Expression.rar (10.67 KB, 下载次数: 33) 我想大家如果学习了数据结构,当然会知道算术表达式求值,意思就是给个表达式,要你给出结果,编程实现
比如:(3+5)^2-3*4-5/3的结果,当然结果是50,如果你算出的结果是50.333333,那么你的算法不错啦!我在这个版块中看到有人再发帖讨论算术表达式的求值方法,我下面告诉大家如何求去表达的值,可能我的解法不是很好!

下面我详细的讲求值的几个步骤:
1.把中缀表达式转换为前缀表达式(或者后缀)
2.按照优先级出栈运算

大家可能会问什么事中缀表达式,这个大家可以百度或者谷歌,我这里简要的讲下,中缀表达式即是我们日常的算术表达式,为什么在求值的过程中我们要把中缀表达式转换为前缀表达式,那是因为计算机他不懂我们写的表示,但是如果用后缀表达式,按照一定的运算,计算机就能读懂.

a.中缀表达式转换为前缀表达式的一般算法
(1) 首先构造一个运算符栈(也可放置括号),运算符(以括号分界点)在栈内遵循越往栈顶优先级不降低的原则进行排列。 

(2)从右至左扫描中缀表达式,从右边第一个字符开始判断: 

如果当前字符是数字,则分析到数字串的结尾并将数字串直接输出。 

如果是运算符,则比较优先级。如果当前运算符的优先级大于等于栈顶运算符的优先级(当栈顶是括号时,直接入栈),则将运算符直接入栈;否则将栈顶运算符出栈并输出,直到当前运算符的优先级大于等于栈顶运算符的优先级(当栈顶是括号时,直接入栈),再将当前运算符入栈。 

如果是括号,则根据括号的方向进行处理。如果是右括号,则直接入栈;否则,遇左括号前将所有的运算符全部出栈并输出,遇左括号后将左右的两括号一起删除。 

(3) 重复上述操作(2)直至扫描结束,将栈内剩余运算符全部出栈并输出,再逆缀输出字符串。中缀表达式也就转换为前缀表达式了。
b.当我们得到这样的最缀表达式的时候,这个时候离结果只差一步之遥了,求值的方法如下:
(1)从表达式最后取值(如果是后缀从前面取值),判断是数字还是运算符,如果是数字压入数据栈,是运算符依次出栈数据栈里的两个元素,按照运算符进行运算,把结果计算的结果再次压入数据栈,直到表达式的每个元素取完为止.
最后的结果就是栈底元素的值.
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 2013-2-4 23:10:14 | 显示全部楼层
这是我写的一个欢迎大家指正缺点和不足,写的实在不好,不好意思贴上源码,如果需要学习的童鞋,评论中说要源码我马上上传!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-3-4 22:11:29 | 显示全部楼层
有点牛逼啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-3-27 00:19:33 | 显示全部楼层
我这运行后显示Expression.exe-无法找到组件,没有找到MSVCR100D.dll,因此这个应用程序未能启动。重新安装应用程序可能会修复此问题。
请问此结果如何解决,谢谢
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 18:12

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表