前綴【運算符+操作數(shù)+操作數(shù)】 中綴【操作數(shù)+運算符+操作數(shù)】后綴【操作數(shù)+操作數(shù)+運算符】
首先明確:
- 前綴中綴后綴三者之間的轉換只會影響運算符的順序,而不會影響操作數(shù)的順序。
- 前綴和后綴是沒有界定符(即括號)的表達式,運算符的排列順序就是整個表達式的運算順序。而中綴表達式作為日常的表達式,需要我們計算時判斷運算的優(yōu)先順序。中綴轉后綴即是判斷運算符優(yōu)先級的過程。
按順序遍歷中綴表達式,
-
由于中綴轉后綴只會改變運算符的執(zhí)行順序而操作數(shù)的順序不變,每次遍歷到操作數(shù)時,直接放入后綴表達式即可。
-
當碰到括號時,相當于碰到一個嚴格的墻壁,在日常計算中,如果沒有算出“()”內的值,是無法和其他操作數(shù)結合起來運算的,所以括號內的運算符一定是優(yōu)先運算的
-
遍歷到運算符的時候,單獨一個運算符無法判斷它的優(yōu)先級(因為他的右操作數(shù)可能還有其他運算要先進行),先將他存入棧中(這里的棧存放無法確定優(yōu)先級的運算符),當遍歷到下一個運算符的時候和棧頂無法確定優(yōu)先級的運算符進行比較,首先和棧頂進行比較,明顯知道棧頂運算符和當前運算符中間夾著一個操作數(shù),根據(jù)計算時的規(guī)則,操作數(shù)一定會選擇優(yōu)先級高的操作符進行結合運算。
- 如果棧頂運算符的優(yōu)先級高于當前遍歷的操作符,那么之前因為不確定而壓入的棧頂運算符已知我后一個運算符是優(yōu)先級比我低的,右操作數(shù)一定會和我先結合。運算順序已確定,彈出棧。
- 如果棧頂運算符優(yōu)先級等于當前的,那么根據(jù)“左優(yōu)先”原則,優(yōu)先執(zhí)行棧頂運算符,棧頂運算符彈出棧
- 如果棧頂運算符優(yōu)先級低于當前遍歷的操作符,說明現(xiàn)在還算不了,一定不會先執(zhí)行棧頂運算符,那么你的運算順序就得靠后了,但其實目前也無法確定能否優(yōu)先執(zhí)行當前的符號,因為與當前相連的右操作數(shù)可能被括號這種優(yōu)先級更高的符號限制住了 ,也是無法判斷當前符號的優(yōu)先級,把當前操作符壓入棧
(萬一棧頂運算符優(yōu)先級高,但是他的左邊的操作數(shù)要和其他人進行結合(即棧頂?shù)那耙粋€運算符優(yōu)先級比棧頂元素高) 怎么能讓我先結合呢? 實際上這種情況不可能出現(xiàn),因為如果出現(xiàn)這種情況,在遍歷到棧頂元素的時候一定會讓優(yōu)先級高的先出去運算,不可能留下來,內含一個遞歸的思想,從第一個元素當棧頂開始,我優(yōu)先級高或等于便利的運算符,我就會出去,(此時這就是第一個操作符 前面誰都不能限制我)低于的只能存在棧里面,只能等待優(yōu)先級高的都算好了我再出去算)
其實本質上就是能算你就算 不能算先壓入棧里面,因為還沒到你算的時候,等輪到你了 最后算的只剩兩個操作數(shù)了你總能算了吧
真是寫煩了 寫的我自己都不懂了
![棧和隊列/中綴表達式轉后綴表達式的機算原理思考/YYYYMMDDHHmmssSSS 1.png]()

浙公網安備 33010602011771號