PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

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

看板Prob_Solve (計算數學 Problem Solving)作者 (☆牜攵☆犬羊)時間3年前 (2020/06/01 12:47), 編輯推噓6(6推 0噓 11→)
留言17則, 8人參與, 3年前最新討論串1/1
大家安安，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
→
06/01 13:22, 3年前 , 1F
還有分配綠跟負號呢
06/01 13:22, 1F
→
06/01 15:35, 3年前 , 2F
好奇隨機代值的話怎麼估計
06/01 15:35, 2F
推
06/01 17:14, 3年前 , 3F
這應該是undecidable
06/01 17:14, 3F
推
06/01 19:38, 3年前 , 4F
我在stackoverflow查到你的發問哈哈
06/01 19:38, 4F
→
06/01 19:41, 3年前 , 5F
我猜啦，你按照課堂上教的stack實作法，讓兩邊stac
06/01 19:41, 5F
→
06/01 19:41, 3年前 , 6F
k的理論值同步，到最後能一樣的話就是相等，不過這
06/01 19:41, 6F
→
06/01 19:41, 3年前 , 7F
只是我的猜測，你要去證明我的方法正確或有反例
06/01 19:41, 7F
→
06/01 19:42, 3年前 , 8F
阿不對，當我沒說，光這個例子我的方法就不行了
06/01 19:42, 8F
推
06/02 18:48, 3年前 , 9F
先轉換成Canonical Form再比較?
06/02 18:48, 9F
→
06/02 18:48, 3年前 , 10F
這篇也許有幫助 https://reurl.cc/O1Dzz7
06/02 18:48, 10F
→
06/02 19:37, 3年前 , 11F
全部展開+比較係數大概可以，不過複雜度就...
06/02 19:37, 11F
推
06/05 19:06, 3年前 , 12F
06/05 19:06, 12F
推
06/10 15:28, 3年前 , 13F
樓上那個裡面只有+，難度差距很大
06/10 15:28, 13F
→
06/10 15:33, 3年前 , 14F
我在想有沒有可能算出其中一邊的變數次方數跟乘除關係後，
06/10 15:33, 14F
→
06/10 15:34, 3年前 , 15F
能用多點例證法甚至大數值的單點例證法直接證明相等？
06/10 15:34, 15F
推
06/25 16:14, 3年前 , 16F
06/25 16:14, 16F
→
06/25 16:15, 3年前 , 17F
06/25 16:15, 17F
‣ 更多 nevikw39 的文章
文章代碼(AID): #1Ur8XN_5 (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 nevikw39 的文章
文章代碼(AID): #1Ur8XN_5 (Prob_Solve)