[问题] 关于运算式的相等

楼主: nevikw39 (牧)   2020-06-01 12:47:15
大家安安,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
这样似乎就没办法继续惹
想请问各位大大能否给我一些方向,谢谢!!
作者: s89162504 (阿本)   2020-06-01 13:22:00
还有分配绿跟负号呢
作者: oToToT (屁孩)   2020-06-01 15:35:00
好奇随机代值的话怎么估计
作者: bibo9901 (function(){})()   2020-06-01 17:14:00
这应该是undecidable
作者: alan23273850   2020-06-01 19:38:00
我在stackoverflow查到你的发问哈哈我猜啦,你按照课堂上教的stack实作法,让两边stack的理论值同步,到最后能一样的话就是相等,不过这只是我的猜测,你要去证明我的方法正确或有反例阿不对,当我没说,光这个例子我的方法就不行了
作者: vnon (路人)   2020-06-02 18:48:00
先转换成Canonical Form再比较?这篇也许有帮助 https://reurl.cc/O1Dzz7
作者: stimim (qqaa)   2020-06-02 19:37:00
全部展开+比较系数大概可以,不过复杂度就...
作者: ddavid (谎言接线生)   2020-06-10 15:28:00
楼上那个里面只有+,难度差距很大我在想有没有可能算出其中一边的变量次方数跟乘除关系后,能用多点例证法甚至大数值的单点例证法直接证明相等?

Links booklink

Contact Us: admin [ a t ] ucptt.com