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

作者: noodleT (麵T)   2016-11-05 16:34:36
※ 引述《art1 (人,原來不是人)》之銘言:
: 中序 A+B+C 要利用堆疊法轉成前序,正確答案是++ABC,因為這樣A+B才會先做
: ^ ^
: 第 第
: 二 一
: 個 個
: 加 加
: 號 號
: 可是我想不出在讀到第二個加號時要怎樣才能不把堆疊內的第一個加號趕出來
: 下一個元素 堆疊 輸出
: 無 空的 無
: C    空的    C
:    +    +   C
:    B    +    CB
:    +    +    CB+
:    A    +    CB+A
:    完成   空的   CB+A+
:  很明顯這樣一定無法輸出++ABC的答案
:  請問到底堆疊法要怎樣處理才能得出正確答案呢?
放著原來的例子 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

Links booklink

Contact Us: admin [ a t ] ucptt.com