作者nevikw39 (☆牜攵☆犬羊)
看板Prob_Solve
标题[问题] 关於运算式的相等
时间Mon Jun 1 12:47:15 2020
大家安安，o'_'o
最近我想要判断两（後序）运算式是否相等，例如中序式 A + (B+C)*D - E 的後序式可以是
BC+D* A + E - 或 A BC+D* E - +。
一开始的想法是构造 expression tree 然後看看经过旋转後是否相等，但是我发现加法、乘法有交换律与
结合律，事情就变得好复杂。
比如把上面的例子简化为中序式 X + Y - Z，後序式的写法包括但或许不限於 X Y + Z - 及 X Y Z - + 等
等。写成 expression tree 的话分别是：
-
/ \
+ Z
/ \
X Y
+
/ \
X -
/ \
Y Z
这样似乎就没办法继续惹
想请问各位大大能否给我一些方向，谢谢！！
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 210.60.35.241 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1590986839.A.FC5.html
1F：→ s89162504: 还有分配绿跟负号呢 06/01 13:22
2F：→ oToToT: 好奇随机代值的话怎麽估计 06/01 15:35
3F：推 bibo9901: 这应该是undecidable 06/01 17:14
4F：推 alan23273850: 我在stackoverflow查到你的发问哈哈 06/01 19:38
5F：→ alan23273850: 我猜啦，你按照课堂上教的stack实作法，让两边stac 06/01 19:41
6F：→ alan23273850: k的理论值同步，到最後能一样的话就是相等，不过这 06/01 19:41
7F：→ alan23273850: 只是我的猜测，你要去证明我的方法正确或有反例 06/01 19:41
8F：→ alan23273850: 阿不对，当我没说，光这个例子我的方法就不行了 06/01 19:42
9F：推 vnon: 先转换成Canonical Form再比较? 06/02 18:48
11F：→ stimim: 全部展开+比较系数大概可以，不过复杂度就... 06/02 19:37
13F：推 ddavid: 楼上那个里面只有+，难度差距很大 06/10 15:28
14F：→ ddavid: 我在想有没有可能算出其中一边的变数次方数跟乘除关系後， 06/10 15:33
15F：→ ddavid: 能用多点例证法甚至大数值的单点例证法直接证明相等？ 06/10 15:34