計算機裡的 polish notation

[楚香帥]

請問中序式表示法如果是: a+b*c/d-e+f
那前序式要如何表示呢 ?　
我看解答是 +/*+abc-def
但我一直有個疑問，照道理說 * / 這些運算子的優先權應該是高於 + - ，所以如果我先處理 b*c，應該就變成 *bc，但顯然這種做法會與答案不符，按照解答，會變成先處理 a+b--> +ab ，然後再把 +ab *c 處理 --> *+abc
接著處理 d-e --> -de，再把 *+abc /-de 作處理 --> /*+abc-de
最後跟 +f 作處理 -->+/*+abc-def 。
想請教大大，這裡好像沒根據運算子的優先權作處理，那真正流程是要怎麼做呢 ?

[claudwu]

印象中一般是用堆疊
詳細忘了
大概就是
一次push一個字元到stack中 然後依據現在丟入的運算子優先權
決定要從stack pop到那邊
最後全部pop完後 就成了

考完試不過三個月 已經忘光光 sorry

[claudwu]

看這個吧
http://www.java3z.com/cwbwebhome/articl ... ostfix.htm
挺詳細的

下次google一下 因該很容易找到才對

[redjoe]

(((a+((b*c)/d))-e)+f )
=> (((a+(*bc/d))-e)+f )
=> (((a+/*bcd)-e)+f )
=> ((+a/*bcd-e)+f )
=> (-+a/*bcde+f )
=> +-+a/*bcdef

代碼: 選擇全部

       +
      / \
     -   f
    / \
   +   e
  / \
 a   /
    / \
   *   d
  / \
 b   c


[楚香帥]

其實我算出來的答案，跟 redjoe 大大是相同的，但好像跟解答有出入，我還特地將答案反解回去：
+/*+abc-def 轉成中序式﹔
+/*T1 c-def (T1=a+b)
= +/T2 -def (T2=T1*c)
=+/T2 T3 f (T3=d-e)
=+T4 f (T4=T2/T3)
=T5 (T4+f)
所以得到：
T5=T4+f=T2/T3+f=T1*c/d-e+f
= a+b*c/d-e+f
結果是一致的，所以 redjoe 大大跟我原本算出來的答案好像不對。

[redjoe]

+/*+abc-def轉成中序
=>(+(/(*(+ab)c)(-de))f)
=>(+(/(*(a+b)c)(d-e))f)
=>(+(/((a+b)*c)(d-e))f)
=>(+(((a+b)*c)/(d-e))f)
=>((((a+b)*c)/(d-e))+f)
=>(a+b)*c/(d-e)+f
註:有些括號不能拿掉

代碼: 選擇全部

         +
        / \
       /   f
     /   \
    *     -
   / \   / \
  +   c d   e
 / \
a   b


[楚香帥]

原來如此，我了解了，謝謝幫忙。