[請益] 一個數學多項式問題

[stevekevin10 (hippo泡)]

各位大大好
最近看到一個問題

Q: 如何將所有變數的多項式組合列出來 (包含括號情況 重複意義的不需要)

ex: a b c
-->
a + b + c
(a + b) + c 重複 不用
a + b - c
a - b + c
a - b - c
a * b * c
a * b / c
a / b * c
a / (b * c)
a / (b / c)
(a / b) / c
a + b * c
(a + b) * c
.
.
.etc

而輸入的變數也可能是a b c d e....etc

加入括號後 就不知道該如何做了
請問該從哪方面下手思考呢?
有沒有類似問題的關鍵字呢

謝謝m_ _m

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.93.155
※ 文章網址: https://www.ptt.cc/bbs/Soft_Job/M.1470732404.A.86C.html
推 YahooTaiwan: 作業？
不是作業..><
→ prosperous: stack?
忘了它...謝謝我上面也去問問看><
※ 編輯: stevekevin10 (1.160.93.155), 08/09/2016 17:17:03
→ win30221: 遞迴感覺比較可以輕鬆弄，只是要額外判斷相同意義的可
→ win30221: 能要再處理
噓 Sidney0503: 作業自己做
不是作業啦。。:"(
是跟朋友閒聊沒加括號情況下要得到所有解很簡單
但是加括號後好像難度翻了幾倍
推 Ayukawayen: 用Postfix(或Prefix)找 這樣就不用管括號 如果輸出要
→ Ayukawayen: Infix 就Postfix再轉Infix就好
→ Ayukawayen: 好像還是會有結合律的問題....
→ prosperous: 我說可以用stack做 不是stackoverflow...
XDD...抱歉我搞錯 stack有考慮過但是在括號部分還是覺得有點卡住
※ 編輯: stevekevin10 (1.160.93.155), 08/09/2016 17:39:06
→ skyhigh8988: 個人想法如Ayu所說 最後轉Infix過程判斷一下結果
→ skyhigh8988: 是否符合結合律去做刪減？
推 CoNsTaR: template MetaProgramming 秒解…
推 CoNsTaR: 喔～是只要列出來 不用算答案喔…
要算答案><
※ 編輯: stevekevin10 (223.137.166.214), 08/09/2016 19:34:30
推 CoNsTaR: 那你就 1.產生依序一串運算子 2.插入 a, b, c，規則是 b
→ CoNsTaR:  不能在 a 前面，c 不能在 b 前面
推 CoNsTaR: 把產生出來的式子當作前序看待，可以產生出所有組合(包含
→ CoNsTaR: 有括號的，只是如果你要轉回中序要自己把括號加上)並且沒
→ CoNsTaR: 有重複
→ donvito: 這個該叫多變數四則運算 不是多項式
→ donvito: 多項式是有精確定義的
噓 Sidney0503: expression binary tree + permutation combination
→ Sidney0503: 作業自己做
推 kukuzo: 就排列組合啊...
→ kukuzo: 看錯..
噓 Sidney0503: 就算不使用expression binary tree
→ Sidney0503: 窮舉所有情況再檢查相同阿
→ Sidney0503: 作業自己做
推 kyuudonut: 你一定沒修過資料結構.....
推 ggg12345: 先用BNF production rule寫出含括弧的expression 限最終
→ ggg12345: terminate 出現的次數就能造出所有可能結果.
→ lazarus1121: 如果想知道原理，去math板問會比較好
推 willy1106: 我記得leetcode有這題目  可以去看看別人解法
推 moon2519: 排列組合問題
推 suhorng: 所以看起來 a - b + c 跟 a - (b - c) 也算重複?
→ suhorng: 為什麼有 a / b * c 又有 a / (b / c)
→ suhorng: 喔要括號, 所以"重複意義"僅限 infixr 或 infixl 不要囉?
推 developers: 1.窮舉所有運算子得到所有expression
→ developers: 2.針對1.的每個expression，窮舉所有括弧
→ developers: 1.的解法可參考leetcode:Expression And Operators
→ developers: 2.的解法leetcode:Different Ways To Add Parentheses
→ developers: 其中1.的解法比leetcode那題還要簡單