:7.477KB : :1 :2021-08-24 12:16:04
一共需要两步,第一步就是把“中缀表达式”转换成“后缀表达式”,第二步就是用“后缀表达式”来计算出结果。
这两步里,每一步用到一个栈,两步就是两个栈咯,栈是啥,新手不知道没关系,这就说一下啥是栈。
第一步:把“中缀表达式”转换成“后缀表达式”的方法(用到一个栈,用来存放运算符+-*/和左括号那些):
首先处理负数:"-"前面一个字符是数字或者),则认为是减号;否则是负号;
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,就是这样啦。
02-04分数的四则运算,关于分数计算
10-07四则运算.cpp(加减乘除)
10-01四则运算出题系统
08-31实验报告,数据结构长整数四则运算
01-09随机生成小学数学四则运算练习题
11-14易语言四则运算解析器
12-24四则运算的代码
12-24双整数数组去重复支持负数