问题标题: 酷町堂:1773 表达式求值

1
0

0
已采纳
蒋智航
蒋智航
高级天翼
高级天翼

在做这一题你需要把基础大佬,这一题是栈

使用两个栈,一个栈用来保存当前操作符,一个栈用来保存操作数。
从前往后遍历字符串:
当遇到数字时直接压入操作数栈;
当遇到正括号 (、[、{ 时直接压入操作符栈;
当遇到乘号或者除号时,判断前一个操作符(即操作符栈栈顶元素)是否为除号,如果前一个操作符为除号则先从操作数栈弹出栈顶两个元素计算除号,除法结果压入操作数栈,然后从操作符栈弹出除法操作符;
当遇到加号或者减号时,如果这个加号或减号是输入字符串的第一个字符时,或者字符串前一个字符为正括号 (、[、{ 时,在操作数栈栈顶压入一个 0, 如果不是这种情况再继续考虑,如果前一个操作符(即操作符栈顶元素)是否为乘号或者除号或者减号,如果是乘号或者除号,就一直从操作数栈弹出两个元素进行乘法或者除法运算,结果压入操作数栈,一直进行到前一个操作符不再是乘号或者除号为止,如果前一个操作符为减号,则也先从操作数栈弹出两个元素进行减法运算,结果压入操作数栈;
当遇到反括号 )、]、} 时, 从操作数栈弹出两个元素,从操作符栈弹出一个操作符,进行算术运算,指导操作符栈栈顶元素为对应的正括号 (、[、{ 时停止进行算术运算,并将正括号从操作符栈弹出。
当输入字符串遍历结束以后,如果操作符栈不为空,则操作数栈弹出两个元素,从操作符弹出一个操作符,进行算术运算,直到操作符栈为空,这个过程相当于最后的表达式从后往前计算,因为有前面的判断逻辑保证,逆序计算不会影响结果。
上述整个过程结束后,操作符栈为空,操作数栈中只剩下整个表达式计算的结果值,返回该结果,弹出栈即可。

我是个魔芋,非常弱

我太弱了,以至于跟大佬您讲这些我都惭愧

自己多理解,哈!

蒋智航在2018-09-17 17:30:19追加了内容

第一句话错了

是“把基础打牢”

1
0
周建勋
周建勋
中级光能
中级光能

建议先打好基础!!!

如果打好了基础就用栈做!!!

0
0
我要回答