四则运算（挑战出题）解答之轮子哥版-1

先看看题目：

下一篇：

以下思路来自轮子哥:

故事

6月11日凌晨1点半左右（北京时间），轮子哥就上面的四则运算（挑战出题）题目开始热血贡献思路，本来有点睡不着，这下倒好，我脑子也开始转起来了。经过半小时的文字迭代，轮子哥确定思路，说第二天（对我来说是当天）还记得就实现一个demo（我一定会记得提醒！:D）。于是...，我们先说说思路是啥。

思路

1. 直接产生后缀表达式
2. 归一化表达式（相同题目的后缀表达式一定一样）
3. 通过直接比较归一化的后缀表达式字符串来去重
4. 后缀转中缀输出

整个过程中我们依然有表达式树的概念，只是各个节点都是存放字符串中的各个字符。

1) 产生后缀表达式

我们题目里面规定数值只能是整数 1~9 (轮子哥实现的是 0~9，但是不影响思路)，运算符只能是 +,-,*,/，于是我们实现时可以简化，一个字符就是一个操作数or操作符。

• 我们要产生合法的表达式
• 什么时候判断结束呢？
  • 如果需要产生n个运算符的表达式，那么表达式总长度为2*n+1，终止条件很明确。
• 期间如何判断这一次1)能不能产生操作符？2)能不能产生操作数？
  • 产生操作符的前提是至少有两棵子树。
  • 操作数总个数为n+1个，期间产生的操作数个数不能超过限制。

下面以产生3个操作符的表达式为例：

• 首先我们的子树个数为0，需要产生操作数作为子树，例如：2，此时后缀表达式是2
  • 此时子树个数不足2，继续产生操作数作为子树，例如：1，此时后缀表达式是21

tree1	tree2
2	1

• 有大于等于2棵子树，接着我们可随机产生操作数或者操作符，比如产生出 +，此时后缀表达式是21+，+ 产生时，是一个操作符，需要选取靠近它的两棵子树作为左右子树，并将它们合并成一棵树

left	right
2	1

tree1

21+

• 这时只有一棵子树了，我们必须继续产生操作数来增加新的子树（如果再继续产生新的操作符，表达式就不合法了）,比如产生出 3，此时后缀表达式是 21+3

tree1	tree2
21+	3

• 有大于等于2棵子树，接下来可以产生操作数或者操作符，比如产生4，此时表达式为21+34,多一棵子树

tree1	tree2	tree3
21+	3	4

• 有大于等于2棵子树，接下来可以产生操作数或者操作符，比如产生-，此时表达式为21+34-，- 产生时，是一个操作符，需要选取靠近它的两棵子树作为左右子树，并将它们合并成一棵树

tree1	left	right
21+	3	4

tree1	tree2
21+	34-

• 有大于等于2棵子树，接下来可以产生操作数或者操作符，比如产生*，此时表达式为21+34-*，* 产生时，是一个操作符，需要选取靠近它的两棵子树作为左右子树，并将它们合并成一棵树

left	right
21+	34-

tree1

21+34-*

最后结果为 21+34-*，中缀表达式为 (2+1)*(3-4)

2) 归一化表达式

归一化的目的是为了去重，手段是让相同表达式的后缀表现为相同的字符串。

如何做呢？很简单

• 让表达式子树按大小排序，即小的在左边，大的在右边。
• 比较大小即比较左右子树的字符串大小即可

注意：仅+和*有交换律，需要做排序

举例：

• 在产生操作符+时，假如后缀表达式为 43+，此时左右子树是：

left	right
4	3

我们对左右子树做字符串排序，则交换为

left	right
3	4

再连接两棵子树：

tree1

34+

• 在产生操作符*时，假如后缀表达式为 34+21-*，此时左右子树是：

left	right
34+	21-

我们对左右子树做字符串排序，则交换为：

left	right
21-	34+

再连接两棵子树：

tree1

21-34+*

3) 去重

这里就很简单了，我们在集合也存放后缀表达式的字符串，放入集合中保证集合内没有相同的字符串，则一定不是相同的表达式。

C++中直接往std::set<std::string>中存放即可

4) 后缀转中缀输出

大把参考资料，略。

故事（续）

第二天轮子哥没经提醒就已经开始实现了，实现过程中自曝有bug，调试，写注释，最后给出代码。经测试发现有重复题目，查证后发现并不是产生后缀的问题，是在输出中缀时括号处理不当造成。

期间轮子哥一句话我不能同意更多:

写注释业是一种code review的办法，在没有人帮你的情况下

Skills

• 如何解决除0问题？
  • 参考思路：产生后缀表达式过程中记下每棵子树的值，如果右子树的值为0，下一次避免产生/
• 如何从任意一个运算符开始，搜索归属于该运算符的完整表达式？
  • 参考思路：
    • 从右往左开始搜索
    • 标记开始
    • 对操作数和操作符分别计数
    • 当操作数个数比操作符个数多1的地方停止
    • 标记结束

参考

附轮子哥的代码（部分信息未在博客中解读，后续更新）：

下一篇：