例如:Exp=a*b+(c-d/e)*f
若 Exp=a*b+(c-d/e)*f 則它的
前綴式為: +*ab*-c/def
中綴式為: a*b+c-d/e*f
后綴式為: ab*cde/-fx+
綜合比較它們之間的關系可得下列結論:
1.三式中的 “操作數之間的相對次序相同”;
(二叉樹的三種訪問次序中,葉子的相對訪問次序是相同的)
2.三式中的 “運算符之間的的相對次序不同”;
3.中綴式丟失了括弧信息,致使運算的次序不確定;
(而前綴和后綴運算只需要一個存儲操作數的棧,而中綴求值需要兩個棧,符號棧和操作數棧)
4.前綴式的運算規則為:連續出現的兩個操作數和在它們之前且緊靠它們的運算符構成一個最小表達式;
5.后綴式的運算規則為:
·運算符在式中出現的順序恰為表達式的運算順序;
·每個運算符和在它之前出現且緊靠它的兩個操作數構成一個最小表達式。
6.中綴求值的運算規則:
如果是操作數直接入棧。
如果是運算符。這與當前棧頂比較。個如果比當前棧頂高,則入棧,如果低則說明當前棧頂是最高的必須把他先運算完了。用編譯原理的話就是說當前棧頂已經是最左素短語了)
其實中綴表達式直接求值和把中綴表達式轉化成后綴表達式在求值的過程驚人的相似,只不過是直接求值是求出來,而轉化成后綴是輸出來。
數據結構在計算機學科專業基礎綜合試卷中占有較高的分值比重,因此是計算機專業課復習的重點科目,建議同學們在復習過程中能夠廣泛參考復習資料,同時結合自身的復習情況,找準方法,取得復習的超高效率和良好效果。