保护私人版权,尊重他人版权。转载请注明出处并附带页面链接
问题来源
全日制steam小游戏『24点』实现过程中遇到的问题,现在,通过某种方法,后端能得到一个字符串表达式,含有四则运算和括号。要求结算该表达式得到结果。对于计算结果,若为整数,直接以整数结果表示;若为分数则以分数结果表示,不能转成浮点数。
解决思路
分解问题
其实是一个经典的算法问题以及一个分数运算问题:
- 解析字符串表达式,表达式中含有+、-、*、/、( 和 )
- 将一般的数值运算转为分数运算,其中,值得注意的是** 分数的约分 **逻辑
解析字符串表达式
首先,忽略分数计算的问题,解析字符串表达式,这个算是一个经典问题,大学时期应该都有了解,这里提供一个leetcode题目作为参考: leetcode - 227. 基本计算器2 Basic Calculator II 。在这个题目的基础上,增加解析括号的要求,即为本小节需要解决的问题。
表达式中含有四则运算和括号,因此存在运算优先级的问题,为了减少递归,对于乘除法没有执行。
先来一个字符串表达式解析的流程图。
分数运算
分数运算没有复杂的算法,实际上就是新增一个** Fraction类 ,Fraction存储分子和分母,所有的从字符串表达式中解析得到的数字都不直接参与字符串解析的算法,而是 先初始化为 Fraction 的对象 ,再进行四则运算,因此,只要理清楚 分数的四则运算 和 约分 **逻辑即可。其中,约分逻辑需要注意效率和正确性,因此下文也给出了笔者的约分流程图。
以下是Fraction分式类的类图,以及约分流程图。
fraction类图
方法或属性 | 说明 |
---|---|
Fraction::num | 存储分子 |
Fraction::den | 存储分母 |
Fraction::rule(Fraction $exp, int $op) | 当前对象与$exp做$op运算,并将结果更新至当前对象 |
Fraction::ruleString(Fraction $exp, int $op) | 当前对象与$exp做$op运算,并将结果更新至当前对象 |
Fraction::sum(Fraction $exp) | 当前对象与$exp做加法运算,并将结果更新至当前对象 |
Fraction::sub(Fraction $exp) | 当前对象与$exp做减法运算,并将结果更新至当前对象 |
Fraction::mul(Fraction $exp) | 当前对象与$exp做乘法运算,并将结果更新至当前对象 |
Fraction::div(Fraction $exp) | 当前对象与$exp做除法运算,并将结果更新至当前对象 |
Fraction::reduction() | 对当前对象执行约分逻辑 |
Fraction::reciprocal() | 对当前对象求倒数 |
Fraction::isProper() | 对当前对象判断是否为真分数 |
Fraction::getFloat() | 返回当前对象的浮点数值 |
Fraction::getAuto() | 当前分式能表达为整数则表达为整数,否则返回分数字符串 |
约分流程图
注意:实际代码较该流程有优化,可参考最后php代码中,Fraction::reduction()
方法的具体逻辑。
代码实现
最后,惯例,看不懂上面的图文的,来看代码吧~~~
php实现
两个类,一个** Fraction 存储分式,Caculator用于计算,里面仅一个静态方法Caculator::caculate()**用于计算字符串表达式。
1 | /** |