"10以下關於運算式 A×(B-C)+D 不同表示法的描述,何者正確?
(A)其前序表示法為+×- A BCD
(B)其前序表示法為 ABC-×D+
(C)其後序表示法為 ABCD-×+
(D)其後序表示法為 ABC-×D+"
統計: A(45), B(83), C(74), D(400), E(0) #386431
詳解 (共 4 筆)
要解這個要先了解運算子和運算元
運算子:運算符號如+-x/
運算元:就是你看到的ABCD或是1234
然後再知道tree的長法
o
/ \
o o
/ \ / \
o o o o
前序:以根節點為基礎開始劃分中(中為根節點或父節點)節點、左節點、右節點
後序:以根節點為基礎開始劃分左節點、右節點、中節點
中序:以根節點為基礎開始劃分左節點、中節點、右節點
以上的劃分方法簡單的說就是以中節點為主然後由左往右
所以前序的中節點就會是最先開始的節點然後左節點右節點
而後序的中節點就會是放在最後
中序的中節點就會在中間
現在進入正題
解題一開始都是先抓運算子為根節點或父節點
前序:中左右=> +(根節點) x(父節點) A(子左節點) -(父節點) B(子左節點) C(子右節點) D(子右節點)
=> + x A - B C D
tree: +
/ \
x D
/ \
A -
/ \
B C
後序:左右中=>A(子左節點) B(子左節點) C(子右節點) -(父節點) x(父節點) D(子右節點) +(根節點)
中序:左中右=>就是題目
說明
平常所使用的運算式,主要是將運算元放在運算子的兩旁,例如a+b/d這樣的式子,這稱之為中序(Infix)表示式,對於人類來說,這樣的式子很容易理
解,但由於電腦執行指令時是有順序的,遇到中序表示式時,無法直接進行運算,而必須進一步判斷運算的先後順序,所以必須將中序表示式轉換為另一種表示方
法。
可以將中序表示式轉換為後序(Postfix)表示式,後序表示式又稱之為逆向波蘭表示式(Reverse polish notation),它是由波蘭的數學家盧卡謝維奇提出,例如(a+b)*(c+d)這個式子,表示為後序表示式時是ab+cd+*。
解法
用手算的方式來計算後序式的話,可以使用括號法,將運算子兩旁的運算元依先後順序全括號起來,然後將所有的右括號取代為左邊最接近的運算子(從最內層括號開始),最後去掉所有的左括號就可以完成後序表示式,例如:
另一個方式是使用堆疊法進行中序轉後序,演算法直接敘述的話就是使用迴圈,取出中序式的字元,遇運算元直接輸出;堆疊運算子與左括號;
堆疊中運算子優先順序若大於等於讀入的運算子優先順序的話,直接輸出堆疊中的運算子,再將讀入的運算子置入堆疊;遇右括號輸出堆疊中的運算子至左括號。
個人簡解
A×(B-C)+D 後序全用括號法處理
=>{[A×(B-C)]+D}=[A×(BC)-]+D=(ABC-x)+D=ABC-xD+;後序表示法