Re: [理工] [資結]-中序轉後序

[crazykk (JK)]

※ 引述《fj90406 (阿亮)》之銘言：
: Write the postfix form of the following expressions:
: (a) -a+b-c+d
: (b) a*-b+c
: (c) (a+b)*d+e/(f+a*d)+c
: -----------------------
: 以下為小弟答案
: (a)
:         (-a)b+c-d+
: (b)
:         a(-b)*c+
: (c)
:         ab+d*efad*+/+c+
: 答案很不確定
: 請高手幫忙解
: 並加以糾正
: 謝謝

(a) -a+b-c+d

    = ((((-a)+b)-c)+d)   setp1.先用括號(依照優先權順序括，注意:加、減的右結合)

    => postfix: a - b + c - d +  setp2.運算式取代最近的右括號

    Note:1.prefix 差別在於setp2是將運算式取代最近的左括號

                                                  x     y
         2.所謂最近的右括號，如下所示:  ( ( a - b ) + c ) => a b - c +
           (減取代x括號,加取代y括號)

(b) a*-b+c

    =( (a* (-b)) + c )

    => postfix: a b - * c +

(c) (a+b)*d+e/(f+a*d)+c

    =((((a+b)*d)+(e/(f+(a*d))))+c)

    => postfix: a b + d * e f a d * + / + c +

還有另一種方法是用Stack，晚點再補

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 60.244.36.139
推 fj90406:謝謝大大的解答，不過像(b)小題，如果在把其轉回中序，不
→ fj90406:不會造成說"ab-" → "a-b"嗎?
posfix轉回infix如下所示
http://img257.imageshack.us/img257/706/40549062.jpg

推 fj90406:小弟我個人見解是"是否應該把負號與減號分別判定"(雖然外
→ fj90406:觀一樣)
※ 編輯: crazykk         來自: 60.244.36.139        (03/22 18:26)
推 fj90406:感謝高手的解答，對於這些題目，已無惑 謝謝您!!!
補上用Stack轉換(即是電腦實際轉換方法)

可參考程式 http://tinyurl.com/ybxuka3

我以(b)來講解  a*-b+c

step1.先補上括號 ((a*(-b))+c) 接著從運算式最左邊開始往右SCAN

step2."(" push到stack中   | ( |
                          |___|
                          stack

step3."(" push到stack中   | ( |
                          | ( |
                          |___|
                          stack

step4."a" 運算元，直接印出a，所以目前輸出是 a

step5."*" push到stack中   | * |
                          | ( |
                          | ( |
                          |___|
                          stack

step6."(" push到stack中   | ( |
                          | * |
                          | ( |
                          | ( |
                          |___|
                          stack

step7."-" push到stack中   | - |
                          | ( |
                          | * |
                          | ( |
                          | ( |
                          |___|
                          stack

step8."b" 運算元，直接印出b，所以目前輸出是 a b

step9.")" 執行pop()且印出pop的結果，直到遇到左括號(括號不印)
      目前stack: | * | ，輸出結果 a b -
                 | ( |
                 | ( |
                 |___|
                 stack

step10.")"同上，目前stack: | ( |，輸出結果 a b - *
                           |___|
                           stack

step11."+" push到stack | + |
                       | ( |
                       |___|
                       stack

step12."c" 運算元，直接印出c，所以目前的輸出是 a b - * c

step13.")"執行pop()且印出pop的結果，輸出結果 a b - * c +

所以postfix是 a b - * c +
※ 編輯: crazykk         來自: 60.244.36.139        (03/22 19:50)