【转载】支持负数和无限精度的四则运算

凌哥

举个栗子：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，就是这样啦。

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


四则运算.e (27.06 KB, 下载次数: 97)

2020-10-17 21:55 上传

点击文件名下载附件

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

互斥体

支持开源~！感谢楼主分享

互斥体

支持开源~！感谢分享

S777

ghost12

先点评加好评再送精币的说

lovely203

孤城已故

路过围观一下，顺便帮顶

zhifu3158

下载 研究下

wxj213

思路很好，学习了。

wxj213

思路很好，学习了。

wxj213

思路很好，学习了。