稀有猿诉

十年磨一剑,历炼出锋芒,说话千百句,不如码二行。

表达式求值问题总结

在模拟范畴内表达式运算求值是比较典型的一类问题。

问题分类

表达式类问题一般输入都是以字串形式,所以第一个要点就是把一个字符串按语义拆解为符号,操作符和操作数。

第二个要点就是表达式的运算。

形式上又可分为后缀式和中缀式(也即正常顺序)。

操作符有些是只有加减法,有些则四则运算都有,这个会让难度上一个层次。

最难搞的就是括号,如果有括号的话,会让难度直接上一个数量级。

绝大多数场景都要用到栈,对于复杂的运算(四则)和有括号,因为涉及优先级和嵌套,所以要用到双栈,一个栈存操作符,一个栈存操作数。

要点分析

第一步就是拆解字串,把其分解成为操作符,符号操作数。在拆解的时候最重要的就是当遇到某一个类型分类时,要把它当成一个整体全都解析出来,直到遇到不同类别的字符。比如说『-234+5』这样一个字串,第一个是符号,它不能单独存在,必须与其后的数字组合起来,这一坨直到加号『+』为止,是一个整体操作数-234

符号一般只出现在字符串的开头,具体的就是整个字串的第1个字符,以及等号右边的第1个字符(如果有等号的话)。

典型问题

题目 题解 说明
640. 求解方程 题解
592. 分数加减运算 题解

参考资料

Comments