精易论坛

标题: 【转载】支持负数和无限精度的四则运算 [打印本页]

作者: 凌哥 时间: 2020-10-17 21:56
标题: 【转载】支持负数和无限精度的四则运算
举个栗子：1-2*(3+(4/5))，这是我们平时书写的方式，也叫中缀表达式，
这就涉及到优先级的问题了，又有乘又有加还有括号的，难搞哦，搞哦，哦，，
于是有个人，发明了一种方法，叫逆波兰式，也叫后缀表达式，就是把中缀表达式经过一串规则，转换成后缀表达式，
此时，括号没有了，优先级也解决了，终于适合计算机的从左往右一股脑地算过去得出结果来了，
比如上面的栗子，转换成后缀表达式就是：1,2,3,4,5,/,+,*,-，这样是不是就没括号啦，新手看又看不懂，没关系，下面就懂了，嗯，下面

一共需要两步，第一步就是把“中缀表达式”转换成“后缀表达式”，第二步就是用“后缀表达式”来计算出结果。
这两步里，每一步用到一个栈，两步就是两个栈咯，栈是啥，新手不知道没关系，这就说一下啥是栈，
例如：“羽毛球筒”只有一个开口，装羽毛球进去时，只能从那个开口装进去，
拿出来时也是只能从那个开口先拿出来最后放进的那个羽毛球，也就是后进先出的原则，
拿出来了一个羽毛球，羽毛球筒里面就少了最后放进去的那一个羽毛球，
那么这个“羽毛球筒”换个名字就叫“栈”了，“羽毛球”就是元素，栈内的元素，就是“羽毛球筒”里的羽毛球，
入栈：往里面添加一个元素（往羽毛球筒里放入一个羽毛球的意思），
出栈：从栈里拿出最后添加进去的那一个元素，并且栈内不再保留这个元素（入一个多一个，出一个少一个）
有点蒙吗，好吧，放大招了，哈~~优嗝，上图：

开始了，原理如下：
第一步：把“中缀表达式”转换成“后缀表达式”的方法(用到一个栈，用来存放运算符+-*/和左括号那些)：
首先处理负数："-"前面一个字符是数字或者)，则认为是减号；否则是负号；
1、从左往右扫描中缀表达式，遇到操作数：直接输出(就是添加到后缀表达式右边的意思)
2、栈为空时，遇到运算符：直接入栈
3、遇到左括号：将其入栈
4、遇到右括号：把栈内元素(操作符)依次出栈，依次添加到后缀表达式右边，直到栈内遇到左括号为止(此左括号丢弃，即不用加到后缀表达式上，也不留在栈里)
5、遇到其他运算符，加减乘除：拿出所有优先级大于或者等于该运算符的栈顶元素(依次添加到后缀表达式右边)，
然后将遇到的该运算符入栈。有一点需要注意，只有在遇到" ) "的情况下我们才拿出" ( "，其他情况我们都不会拿出" ( "，
也就是：遇到的运算符不是右括号的话，拿出符号时，如果遇到栈内遇到了左括号，那就别再拿了，左括号就留在里面的意思。
6、扫描完中缀表达后，最终将栈内的元素依次出栈，添加到后缀表达式右边，即可得到一个完整的后缀表达式。

用栗子：1-2*(3+(4/5))试下看：
第1步：-号前面是数字，就是减号，不是负号，那这个-就是运算符了，不用管，
第2步：开始从左往右扫描，扫到1，加入后缀表达式后面，此时后缀表达式＝1
再扫描，到-，是运算符，加入栈里，此时栈里是-，
再扫描，到2，是操作数，不是运算符，好，后缀表达式＝1 2，有两个数了，
再扫描，到*，是运算符，栈里的-号优先级比这个低，那就入栈，栈＝- *
再扫描，到(，是符号，这个直接入栈就对了，那就是栈＝- * (
再扫描，到3，是操作数，那就后缀表达式＝1 2 3
再扫描，到+，是运算符，栈顶是(，那就直接入栈，那就是栈＝- * ( +
再扫描，到(，这个没二话，直接入栈，栈＝- * ( + (
再扫描，到4，加入后缀表达式＝1 2 3 4
再扫描，到/，栈顶是(，那就直接入栈，那就是栈＝- * ( + ( /
再扫描，到5，加入后缀表达式＝1 2 3 4 5
再扫描，到)，右括号来了，那就一直出栈吧，出到左括号为止，出/，此时后缀表达式＝1 2 3 4 5 /，栈＝- * ( + (
  然后再出(，好了，出到左括号了，不再出了，也不要把这个(加去表达式去，此时栈＝- * ( +
再扫描，到)，同上，出栈，出到(为止，先出+，此时后缀表达式＝1 2 3 4 5 / +，栈＝- * (
  然后再出到(了，那就停，一样的，这个左括号不要了，也不要加去表达式，现在栈＝- *
再扫描，呼，没有了，扫完了，那就把栈里的一个个出到表达式右边去，先出*，后缀表达式＝1 2 3 4 5 / + *
然后出-，后缀表达式＝1 2 3 4 5 / + * -
这样就转换完成啦，是不是括号就没有了啦。

第二步，用“后缀表达式”来计算出结果：
1、设置一个栈，开始时，栈为空(这个栈是用来存取操作数的，不像上面那个，上面那个是存取符号用的)
2、从左到右扫描后缀表达式，若遇操作数，则进栈
3、若遇运算符，则从栈中退出两个元素，先退出的放到运算符的右边，后退出的放到运算符左边，运算后的结果再进栈，直到后缀表达式扫描完毕
4、最后，栈中仅有一个元素，即为运算的结果

用上面转换出的栗子：1 2 3 4 5 / + * -
首先从左开始扫描，遇到1，入栈，此时栈＝1
再扫描，遇到2，入栈，此时栈＝1 2
再扫描，遇到3，入栈，此时栈＝1 2 3
再扫描，遇到4，入栈，此时栈＝1 2 3 4
再扫描，遇到5，入栈，此时栈＝1 2 3 4 5
再扫描，遇到/，遇到符号了，是个除号，那就从栈里取出两个元素，取得第一个是5，再取得第二个是4，
      然后根据原理，先出的5放右边，后出4的放左边，那就是4/5，算出结果4/5＝0.8，这里可以判断一下除数为0就返回错误，不给计算咯，
      把这个计算结果放入栈，此时栈＝1 2 3 0.8 因为5和4刚都取出了，没有了，
再扫描，遇到+，同上，出栈＝0.8，再出栈＝3，同上，3+0.8＝3.8，把结果3.8入栈＝1 2 3.8
再扫描，遇到*，同上，出栈＝3.8，再出栈＝2，同上，2*3.8＝7.6，把结果7.6入栈＝1 7.6
再扫描，遇到-，同上，出栈＝7.6，再出栈＝1，同上，1-7.6＝-6.6，把结果入栈＝-6.6
再扫描，没有了，再看栈内只有一个元素-6.6，也是刚好的，这个就是最终结果啦，
1-2*(3+(4/5))＝-6.6，就是这样啦。

源码奉上，拿去学会原理了，管他什么语言，想写就写哈哈哈哈

原帖：http://bbs.eyuyan.com/read.php?tid=418888

作者: 易造轮 时间: 2020-10-17 22:09
沙发

作者: a6546 时间: 2020-10-17 22:45
好东西，必须支持！！

作者: kmskik 时间: 2020-10-17 22:55
凌哥出品，必属精品

作者: 影知 时间: 2020-10-17 23:10
精典算法吗？？

作者: kentfung 时间: 2020-10-17 23:36
谢谢分享，下载来看看

作者: Dwan 时间: 2020-10-18 01:07
支持一下！！！！！！！！！！！！！！

作者: eyy2017 时间: 2020-10-18 07:12
6666666666666666666666666666

作者: jhai 时间: 2020-10-18 09:46
厉害了............

作者: 外星星人 时间: 2020-10-18 11:31
试试源码效果

作者: wxj213 时间: 2020-10-18 14:17
谢谢分享，下载来看看

作者: lity2310 时间: 2020-10-18 14:27
下载下来学习学习

作者: 爱易语言的傻蛋 时间: 2020-10-18 20:58
学习学习~~~~

作者: hmyroot 时间: 2020-10-18 22:46
好复杂，看了会头痛

作者: huaidan2015 时间: 2020-10-20 13:57
这个图画的，我给满分，我一下子就看懂了

作者: 靓低调人生 时间: 2020-10-20 17:08
必须支持一下！！！！！！！！

作者: vSpear 时间: 2020-10-21 10:08
学习一波了

作者: jing2020yi 时间: 2020-10-21 16:22
学习一波

作者: lunengcheng 时间: 2020-10-22 23:19
多谢老大分享

作者: 124149449 时间: 2020-10-24 01:02
感谢你的支持，精易有你更精彩

作者: 冰棍好烫啊 时间: 2020-10-24 14:04
感谢你的支持，精易有你更精彩

作者: 难解 时间: 2020-10-24 19:27
学习一波

作者: yangcongwen 时间: 2020-10-28 20:13
本帖最后由 yangcongwen 于 2020-10-28 20:17 编辑

能不能支持一下百分号，千分号就不说了百分号不能简单替换为/100，因为有优先计算的问题。比如1/2%=50，如果你替换成1/2%=1/2/100=0.005

作者: jingyi11023995 时间: 2020-11-4 18:54
思路很好，学习了。

作者: wxj213 时间: 2020-11-13 17:15
思路很好，学习了。

作者: wxj213 时间: 2020-11-13 17:16

思路很好，学习了。

作者: wxj213 时间: 2020-11-13 17:18

思路很好，学习了。

作者: zhifu3158 时间: 2021-2-15 15:32
下载研究下

作者: 孤城已故 时间: 2021-2-16 03:13
路过围观一下，顺便帮顶

作者: lovely203 时间: 2021-10-12 08:46

作者: ghost12 时间: 2022-3-20 20:01
先点评加好评再送精币的说

作者: S777 时间: 2022-3-23 01:17

作者: 互斥体 时间: 2024-9-24 22:43
支持开源~！感谢分享

作者: 互斥体 时间: 2024-9-24 22:43
支持开源~！感谢楼主分享

欢迎光临精易论坛 (https://125.confly.eu.org/)