Notifications
Article
不定量变量运算转后缀表达式的一个方法
Published 6 months ago
125
0
Max(1,2,3) -> 1 2 max 3 max,我觉得有很大优化空间
前几天想要实现一个字符串计算的功能(类似Eval()),一般的加减乘除等双目运算符好解决,直接转成后缀表达式就行了,但到了 Max() Min() 这些变量数不能确定的运算时就出问题了。我们一般使用的算式是中缀表达式,这个表达式的计算顺序是不固定的,把中缀表达式转成后缀表达式来让计算机从左到右计算是解决这个问题的常用方法之一,但问题是后缀表达式没有括号,不定量运算无法通过括号来表示自己需要多少个变量来进行运算。
对于这个问题我有一个思路:不定量变量运算应该是有一个最基本的算法,然后才在这个基础上增加变量数量。那么如果我们把这个基本算法提取出来作为一个运算符,之后把不定量变量运算改成多个这个运算符是不是就能解决问题?

我用Max做一个实验,Max不管传进去多少个参数最后都会返回出最大的那个,而Max至少需要两个参数,那么Max应该可以理解为所有参数一次次进行双参数的Max计算。
把双参数Max计算作为一个运算符提取出来,比较左右两个数返回大的那个,那么Max(a,b,c)就可以转化为(a max b max c),保留括号可以保证执行顺序不会错乱。

有这个转化方案之后是如何进行转化,只有一个Max好解决,把括号前的Max删掉,把括号里的逗号替换成max就行了。但是如果涉及到嵌套的情况就不好办了,比如 Max(Min(1,2,3),Min(3,4,5)) ,怎么区分哪个逗号是Max的哪个逗号是Min的?
这时中缀转后缀的缓存栈又可以拿出来用了,其实根本没必要管什么顺序,只要从左到右一路走下去,记住每个括号是哪个运算符的就解决了。
还用 Max(Min(1,3),Min(3,4)) 来说,从左到右开始:
遇到Max的左括号,把Max压入栈,向右走 -> 遇到Min的左括号,把Min压入栈,向右走 -> 遇到逗号,此时栈顶是Min,说明正在Min的括号里,这个逗号是Min的,替换成min,向右走 -> 遇到逗号,此时栈顶是Min,说明正在Min的括号里,这个逗号是Min的,替换成min,向右走 -> 遇到右括号,说明这个运算符的范围结束了,从栈里弹出栈顶运算符,向右走 -> 遇到一个逗号,此时栈顶是Max,说明在Max的括号里,这个逗号是Max的,替换成max,向右走 -> 遇到Min的左括号,把Min压入栈,向右走 -> 遇到逗号,此时栈顶是Min,说明正在Min的括号里,这个逗号是Min的,替换成min,向右走 -> 遇到逗号,此时栈顶是Min,说明正在Min的括号里,这个逗号是Min的,替换成min,向右走 -> 遇到右括号,说明这个运算符的范围结束了,从栈里弹出栈顶运算符,向右走 -> 遇到右括号,说明这个运算符的范围结束了,从栈里弹出栈顶运算符,到末尾了,结束
最后的结果是 ((1 min 2 min 3) max (3 min 4 min 5))
再按照中缀转后缀的方法转为 1 2 min 3 min 3 4 min 5 min max,之后就可以用后缀计算来算出结果了。

具体实现代码可以看:https://github.com/MrTrueChina/Unity-Eveluate

我写完后觉得这个思路有很多可以优化的地方,比如能不能给运算符加前缀数量,在运算时直接弹出需要数量的元素,不过这样如何在向右走的同时记录下运算符和它有几个逗号似乎就变得麻烦起来了。
Tags:C#
MtC
咸鱼王 - Programmer
2
Comments