作者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/m.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