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

[nevikw39 (☆牜攵☆犬羊)]

大家安安，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
→ s89162504: 還有分配綠跟負號呢
→ oToToT: 好奇隨機代值的話怎麼估計
推 bibo9901: 這應該是undecidable
推 alan23273850: 我在stackoverflow查到你的發問哈哈
→ alan23273850: 我猜啦，你按照課堂上教的stack實作法，讓兩邊stac
→ alan23273850: k的理論值同步，到最後能一樣的話就是相等，不過這
→ alan23273850: 只是我的猜測，你要去證明我的方法正確或有反例
→ alan23273850: 阿不對，當我沒說，光這個例子我的方法就不行了
推 vnon: 先轉換成Canonical Form再比較?
→ vnon: 這篇也許有幫助 https://reurl.cc/O1Dzz7
→ stimim: 全部展開+比較係數大概可以，不過複雜度就...
推 DJWS: https://leetcode.com/discuss/interview-question/339111/
推 ddavid: 樓上那個裡面只有+，難度差距很大
→ ddavid: 我在想有沒有可能算出其中一邊的變數次方數跟乘除關係後，
→ ddavid: 能用多點例證法甚至大數值的單點例證法直接證明相等？
推 DJWS: https://www.mathworks.com/help/symbolic/simplify.html
→ DJWS: https://stackoverflow.com/questions/7540227/