Re: [問題] A+B+C 用堆疊法要如何轉出 ++ABC 的結果

[noodleT (麵T)]

※ 引述《art1 (人，原來不是人)》之銘言：
:   中序 A+B+C 要利用堆疊法轉成前序，正確答案是++ABC，因為這樣A+B才會先做
:         ^ ^
:        第 第
:        二 一
:        個 個
:        加 加
:        號 號
:   可是我想不出在讀到第二個加號時要怎樣才能不把堆疊內的第一個加號趕出來
:   下一個元素    堆疊      輸出
:       無        空的      無
:       Ｃ　　　　空的　 　 Ｃ
: 　　　＋　　　　＋　　    Ｃ
: 　　　Ｂ　　　　＋　　　　ＣＢ
: 　　　＋　　　　＋　　　　ＣＢ＋
: 　　　Ａ　　　　＋　　　　ＣＢ＋Ａ
: 　　　完成　　　空的　　　ＣＢ＋Ａ＋
: 　很明顯這樣一定無法輸出＋＋ＡＢＣ的答案
: 　請問到底堆疊法要怎樣處理才能得出正確答案呢？

放著原來的例子 A+B+C ，先來看 X+Y 就好：

X+Y 轉前序是 +XY ，這沒什麼問題，由左至右先讀三個字元 c1,c2,c3，

然後按照順序輸出 c2,c1,c3 即可。

現在令 X = A+B

那麼 +XY就變成 +(A+B)Y 這時候 A+B 還沒轉成前序，

所以如果有其他人(也就是遞迴)可以幫忙把 A+B 轉前序，就解決了！


其他例如 A+B&C*D*E 轉前序：

((A+B)&((C*D)*E)) => (&(+AB)(*(*CD)E)) => &+AB**CDE

在每個括號裡都是類似 (X)(+)(Y) 轉前序的概念


C++:

可處理 運算子為單一字元、運算元為 +-*/& 的算式

運算子優先權 (*/) > (+-) > (&)

http://ideone.com/SQj8uf

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.237.93.195
※ 文章網址: https://www.ptt.cc/bbs/Programming/M.1478334879.A.66A.html
※ 編輯: noodleT (36.237.93.195), 11/05/2016 16:40:33
推 art1: &在這邊是什麼意思阿？
→ noodleT: 就只是運算子。你也可以去除&
→ noodleT: 二進位 0&0=0；0&1=0
※ 編輯: noodleT (36.237.93.195), 11/05/2016 21:07:40
推 art1: 如果不用遞迴而用堆疊來做呢？
推 art1: 我瞭解了，轉前序時不能使用跟轉後序一樣的
→ art1: 規則，也就是進堆疊的優先權只有在大於堆疊
→ art1: 說錯，應該是小於，才需要把堆疊內的運算子
→ art1: 小於堆疊內運算子的優先權時才把堆疊內的運
→ art1: 算子輸出，而等於時可以繼續疊上去
→ art1: 找到的資料都沒特別提出這一點差異，讓我以
→ art1: 為跟後序一樣只要小於等於時就要輸出運算子
→ LPH66: 這其實是左結合和右結合的差別
→ LPH66: 後序做右結合運算子也是要去掉等於
→ LPH66: 這裡只是反過來而已
→ LPH66: 右結合運算子的例子如次方
推 art1: 中序轉後序時的次方優先權不是更高嗎？
→ art1: 還是你是說計算後序運算式時規則要去掉等於?
→ LPH66: 這裡講的是結合性, 同優先權時誰先做的問題
→ LPH66: 加減和乘除是左邊先, 但次方卻是右邊先
→ LPH66: 例如像 3^4^5 在轉後序時就要如此處理
→ LPH66: 才能得到正確的 345^^ 而非 34^5^
推 art1: 感謝解答