|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
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)从表达式最后取值(如果是后缀从前面取值),判断是数字还是运算符,如果是数字压入数据栈,是运算符依次出栈数据栈里的两个元素,按照运算符进行运算,把结果计算的结果再次压入数据栈,直到表达式的每个元素取完为止.
最后的结果就是栈底元素的值.
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2013-2-4 23:07:51
置顶卡
千斤顶
显身卡
楼主