[問題] 關於運算式的相等

看板 Prob_Solve
作者
時間
留言 17則留言,8人參與討論
推噓 6  ( 6推 0噓 11→ )
大家安安,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://www.ptt.cc/bbs/Prob_Solve/M.1590986839.A.FC5.html
1Fs89162504: 還有分配綠跟負號呢 06/01 13:22
2FoToToT: 好奇隨機代值的話怎麼估計 06/01 15:35
3Fbibo9901: 這應該是undecidable 06/01 17:14
4Falan23273850: 我在stackoverflow查到你的發問哈哈 06/01 19:38
5Falan23273850: 我猜啦,你按照課堂上教的stack實作法,讓兩邊stac 06/01 19:41
6Falan23273850: k的理論值同步,到最後能一樣的話就是相等,不過這 06/01 19:41
7Falan23273850: 只是我的猜測,你要去證明我的方法正確或有反例 06/01 19:41
8Falan23273850: 阿不對,當我沒說,光這個例子我的方法就不行了 06/01 19:42
9Fvnon: 先轉換成Canonical Form再比較? 06/02 18:48
10Fvnon: 這篇也許有幫助 https://reurl.cc/O1Dzz7 06/02 18:48
11Fstimim: 全部展開+比較係數大概可以,不過複雜度就... 06/02 19:37
13Fddavid: 樓上那個裡面只有+,難度差距很大 06/10 15:28
14Fddavid: 我在想有沒有可能算出其中一邊的變數次方數跟乘除關係後, 06/10 15:33
15Fddavid: 能用多點例證法甚至大數值的單點例證法直接證明相等? 06/10 15:34