在写24点纸牌算法时，有一个情况：
算法得到的表达式都是基本表达式，没有考虑运算符号之间的关系，导致冗余了括号。
例如：(3 * (1 * 2) * 4) 与 (3 * (1 * 2 * 4))其实是一样的表达式，应该进行优化。
优化的步骤分为：
- 分析表达式
- 统一乘法两边的大小顺序
- 移除乘除运算外面的括号
分析一般表达式的构成，大致可以简化为 表达式E = (左括号left_bracket) + (表达式或数字E0) + (运算符operation) ＋ (表达式或数字E1) (右括号right_bracket)。
参考超越正则的正则表达式, 表达式的正则可以表示为：
表达式的正则1
2
3
4
5
| /(?<expression>\(
(?<left>(\g<expression>|\d*))
(?<operate>[\+\-\*\/])
(?<right>(\g<expression>|\d*))
\))/
|
这个正则可以匹配类似(1+2)、((1+2)*(3+4))这种表达式，如果想匹配没有括号包围的表达式如：1+2,应该再加上去除()的正则。
更完善的正则1
2
3
4
5
6
7
| /(?<expression>
[\((?<left>(\g<expression>|\d*))
(?<operate>[\+\-\*\/])
(?<right>(\g<expression>|\d*))\)
(?<left>(\g<expression>|\d*))
(?<operate>[\+\-\*\/])
(?<right>(\g<expression>|\d*))])/
|
接下来，就是给乘法两边排序。不需要顾虑那么多，直接正则匹配到包含(E0*E1)的子表达式，进行排序替换。
排序替换1
2
3
4
5
6
7
8
9
10
| exp = "(2*3)+5"
if /(?<all_exp>
\((?<left_number>((?<expression_left>\(?(\d*)[\+\-\*\/](\d*|\g<expression_left>)\)?)|\d*))
\*
(?<right_number>((?<expression_right>\(?(\d*)[\+\-\*\/](\d*|\g<expression_right>)\)?)|\d*))\))/ =~ exp
left_number, right_number = right_number, left_number if left_number =~ /^\d*$/ && right_number =~ /^\d*$/ && left_number.to_i < right_number.to_i
s_exp = "#{left_number}*#{right_number}"
exp.gsub!(all_exp, s_exp)
end
puts exp #=> "3*2+5"
|
最后的结果就成功的把乘法外面的括号移掉了，并按照左大右小的顺序排序。
除法的方式比乘法要简单一些,就不列举了。
还有一个类似(1+(2+3))以及((2+3)-2)这种也应该去括号，这样的话得到的表达式就能够去除大部分相同的表达式，从而实现最优。