作者noodleT (麵T)
看板Programming
標題Re: [問題] A+B+C 用堆疊法要如何轉出 ++ABC 的結果
時間Sat Nov 5 16:34:36 2016
※ 引述《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://webptt.com/m.aspx?n=bbs/Programming/M.1478334879.A.66A.html
※ 編輯: noodleT (36.237.93.195), 11/05/2016 16:40:33
1F：推 art1: &在這邊是什麼意思阿？61.64.0.230 11/05 20:49
2F：→ noodleT: 就只是運算子。你也可以去除&36.237.93.195 11/05 21:05
3F：→ noodleT: 二進位 0&0=0；0&1=036.237.93.195 11/05 21:06
※ 編輯: noodleT (36.237.93.195), 11/05/2016 21:07:40
4F：推 art1: 如果不用遞迴而用堆疊來做呢？ 61.64.0.230 11/05 22:02
5F：推 art1: 我瞭解了，轉前序時不能使用跟轉後序一樣的 61.64.0.230 11/06 00:39
6F：→ art1: 規則，也就是進堆疊的優先權只有在大於堆疊 61.64.0.230 11/06 00:40
7F：→ art1: 說錯，應該是小於，才需要把堆疊內的運算子 61.64.0.230 11/06 00:41
8F：→ art1: 小於堆疊內運算子的優先權時才把堆疊內的運 61.64.0.230 11/06 00:41
9F：→ art1: 算子輸出，而等於時可以繼續疊上去 61.64.0.230 11/06 00:41
10F：→ art1: 找到的資料都沒特別提出這一點差異，讓我以 61.64.0.230 11/06 00:43
11F：→ art1: 為跟後序一樣只要小於等於時就要輸出運算子 61.64.0.230 11/06 00:43
12F：→ LPH66: 這其實是左結合和右結合的差別 180.177.29.238 11/06 10:06
13F：→ LPH66: 後序做右結合運算子也是要去掉等於 180.177.29.238 11/06 10:06
14F：→ LPH66: 這裡只是反過來而已 180.177.29.238 11/06 10:06
15F：→ LPH66: 右結合運算子的例子如次方 180.177.29.238 11/06 10:06
16F：推 art1: 中序轉後序時的次方優先權不是更高嗎？ 61.64.0.230 11/06 14:13
17F：→ art1: 還是你是說計算後序運算式時規則要去掉等於? 61.64.0.230 11/06 14:14
18F：→ LPH66: 這裡講的是結合性, 同優先權時誰先做的問題 180.177.29.238 11/06 16:09
19F：→ LPH66: 加減和乘除是左邊先, 但次方卻是右邊先 180.177.29.238 11/06 16:10
20F：→ LPH66: 例如像 3^4^5 在轉後序時就要如此處理 180.177.29.238 11/06 16:10
21F：→ LPH66: 才能得到正確的 345^^ 而非 34^5^ 180.177.29.238 11/06 16:11
22F：推 art1: 感謝解答 61.64.0.230 11/06 23:55