(轉)字首、中綴、字尾表達式

關鍵字：概念, 字首表達式, 字首記法, 中綴表達式, 中綴記法, 波蘭式, 字尾表達式, 字尾記法, 逆波蘭式

它們都是對表達式的記法，是以也被稱為字首記法、中綴記法和字尾記法。它們之間的差別在于運算符相對與操作數的位置不同：字首表達式的運算符位于與其相關的操作數之前；中綴和字尾同理。

舉例：

(3 + 4) × 5 - 6 就是中綴表達式

- × + 3 4 5 6 字首表達式

3 4 + 5 × 6 - 字尾表達式

中綴表達式（中綴記法）

中綴表達式是一種通用的算術或邏輯公式表示方法，操作符以中綴形式處于操作數的中間。中綴表達式是人們常用的算術表示方法。

雖然人的大腦很容易了解與分析中綴表達式，但對計算機來說中綴表達式卻是很複雜的，是以計算表達式的值時，通常需要先将中綴表達式轉換為字首或字尾表達式，然後再進行求值。對計算機來說，計算字首或字尾表達式的值非常簡單。

字首表達式（字首記法、波蘭式）

字首表達式的運算符位于操作數之前。

由字首表達式的計算機求值：

從右至左掃描表達式，遇到數字時，将數字壓入堆棧，遇到運算符時，彈出棧頂的兩個數，用運算符對它們做相應的計算（棧頂元素 op 次頂元素），并将結果入棧；重複上述過程直到表達式最左端，最後運算得出的值即為表達式的結果。

例如字首表達式“- × + 3 4 5 6”：

(1) 從右至左掃描，将6、5、4、3壓入堆棧；

(2) 遇到+運算符，是以彈出3和4（3為棧頂元素，4為次頂元素，注意與字尾表達式做比較），計算出3+4的值，得7，再将7入棧；

(3) 接下來是×運算符，是以彈出7和5，計算出7×5=35，将35入棧；

(4) 最後是-運算符，計算出35-6的值，即29，由此得出最終結果。

可以看出，用計算機計算字首表達式的值是很容易的。

将中綴表達式轉換為字首表達式：

遵循以下步驟：

(1) 初始化兩個棧：運算符棧S1和儲存中間結果的棧S2；

(2) 從右至左掃描中綴表達式；

(3) 遇到操作數時，将其壓入S2；

(4) 遇到運算符時，比較其與S1棧頂運算符的優先級：

(4-1) 如果S1為空，或棧頂運算符為右括号“)”，則直接将此運算符入棧；

(4-2) 否則，若優先級比棧頂運算符的較高或相等，也将運算符壓入S1；

(4-3) 否則，将S1棧頂的運算符彈出并壓入到S2中，再次轉到(4-1)與S1中新的棧頂運算符相比較；

(5) 遇到括号時：

(5-1) 如果是右括号“)”，則直接壓入S1；

(5-2) 如果是左括号“(”，則依次彈出S1棧頂的運算符，并壓入S2，直到遇到右括号為止，此時将這一對括号丢棄；

(6) 重複步驟(2)至(5)，直到表達式的最左邊；

(7) 将S1中剩餘的運算符依次彈出并壓入S2；

(8) 依次彈出S2中的元素并輸出，結果即為中綴表達式對應的字首表達式。（相當于S1中序列的逆序）

例如，将中綴表達式“1+((2+3)×4)-5”轉換為字首表達式的過程如下：

掃描到的元素	S2(棧底->棧頂)	S1 (棧底->棧頂)	說明
5		空	數字，直接入棧
-			S1為空，運算符直接入棧
)		- )	右括号直接入棧
4	5 4		數字直接入棧
×		- ) ×	S1棧頂是右括号，直接入棧
		- ) × )
3	5 4 3		數字
+		- ) × ) +
2	5 4 3 2
(	5 4 3 2 +		左括号，彈出運算符直至遇到右括号
	5 4 3 2 + ×		同上
		- +	優先級與-相同，入棧
1	5 4 3 2 + × 1
到達最左端	5 4 3 2 + × 1 + -		S1中剩餘的運算符

是以結果為“- + 1 × + 2 3 4 5”。

字尾表達式（字尾記法、逆波蘭式）

字尾表達式與字首表達式類似，隻是運算符位于操作數之後。

字尾表達式的計算機求值：

與字首表達式類似，隻是順序是從左至右：

從左至右掃描表達式，遇到數字時，将數字壓入堆棧，遇到運算符時，彈出棧頂的兩個數，用運算符對它們做相應的計算（次頂元素 op 棧頂元素），并将結果入棧；重複上述過程直到表達式最右端，最後運算得出的值即為表達式的結果。

例如字尾表達式“3 4 + 5 × 6 -”：

(1) 從左至右掃描，将3和4壓入堆棧；

(2) 遇到+運算符，是以彈出4和3（4為棧頂元素，3為次頂元素，注意與字首表達式做比較），計算出3+4的值，得7，再将7入棧；

(3) 将5入棧；

(4) 接下來是×運算符，是以彈出5和7，計算出7×5=35，将35入棧；

(5) 将6入棧；

(6) 最後是-運算符，計算出35-6的值，即29，由此得出最終結果。

将中綴表達式轉換為字尾表達式：

與轉換為字首表達式相似，遵循以下步驟：

(2) 從左至右掃描中綴表達式；

(4-1) 如果S1為空，或棧頂運算符為左括号“(”，則直接将此運算符入棧；

(4-2) 否則，若優先級比棧頂運算符的高，也将運算符壓入S1（注意轉換為字首表達式時是優先級較高或相同，而這裡則不包括相同的情況）；

(5-1) 如果是左括号“(”，則直接壓入S1；

(5-2) 如果是右括号“)”，則依次彈出S1棧頂的運算符，并壓入S2，直到遇到左括号為止，此時将這一對括号丢棄；

(6) 重複步驟(2)至(5)，直到表達式的最右邊；

(8) 依次彈出S2中的元素并輸出，結果的逆序即為中綴表達式對應的字尾表達式（轉換為字首表達式時不用逆序）。（相當于s2中的序列）

例如，将中綴表達式“1+((2+3)×4)-5”轉換為字尾表達式的過程如下：

		+ (	左括号，直接入棧
		+ ( (
	1 2
		+ ( ( +	S1棧頂為左括号，運算符直接入棧
	1 2 3
	1 2 3 +		右括号，彈出運算符直至遇到左括号
		+ ( ×
	1 2 3 + 4
	1 2 3 + 4 ×
	1 2 3 + 4 × +		-與+優先級相同，是以彈出+，再壓入-
	1 2 3 + 4 × + 5
到達最右端	1 2 3 + 4 × + 5 -

是以結果為“1 2 3 + 4 × + 5 -”（注意需要逆序輸出）。

編寫Java程式将一個中綴表達式轉換為字首表達式和字尾表達式，并計算表達式的值。其中的toPolishNotation()方法将中綴表達式轉換為字首表達式（波蘭式）、toReversePolishNotation()方法則用于将中綴表達式轉換為字尾表達式（逆波蘭式）：

注：

(1) 程式很長且注釋比較少，但如果将上面的理論内容弄懂之後再将程式編譯并運作起來，還是比較容易了解的。有耐心的話可以研究一下。(2) 此程式是筆者為了說明上述概念而編寫，僅做了簡單的測試，不保證其中沒有Bug，是以不要将其用于除研究之外的其他場合。

​

1. package qmk.simple_test;  
2. import java.util.Scanner;  
3. import java.util.Stack;  
4. /** 
5.  * Example of converting an infix-expression to 
6.  * Polish Notation (PN) or Reverse Polish Notation (RPN). 
7.  * Written in 2011-8-25 
8.  * @author QiaoMingkui 
9.  */  
10. public class Calculator {  
11.       public static final String USAGE = "== usage ==\n"  
12.             + "input the expressions, and then the program "  
13.             + "will calculate them and show the result.\n"  
14.             + "input 'bye' to exit.\n";  
15.       /** 
16.        * @param args 
17.        */  
18.       public static void main(String[] args) {  
19.             System.out.println(USAGE);  
20.             Scanner scanner = new Scanner(System.in);  
21.             String input = "";  
22.             final String CLOSE_MARK = "bye";  
23.             System.out.println("input an expression:");  
24.             input = scanner.nextLine();  
25.             while (input.length() != 0  
26.                   && !CLOSE_MARK.equals((input))) {  
27.                   System.out.print("Polish Notation (PN):");  
28.                   try {  
29.                         toPolishNotation(input);  
30.                   } catch (NumberFormatException e) {  
31.                         System.out.println("\ninput error, not a number.");  
32.                   } catch (IllegalArgumentException e) {  
33.                         System.out.println("\ninput error:" + e.getMessage());  
34.                   } catch (Exception e) {  
35.                         System.out.println("\ninput error, invalid expression.");  
36.                   }  
37.                   System.out.print("Reverse Polish Notation (RPN):");  
39.                         toReversePolishNotation(input);  
47.                   System.out.println("input a new expression:");  
48.                   input = scanner.nextLine();  
49.             }  
50.             System.out.println("program exits");  
51.       }  
53.        * parse the expression , and calculate it. 
54.        * @param input 
55.        * @throws IllegalArgumentException 
56.        * @throws NumberFormatException 
58.       private static void toPolishNotation(String input)  
59.                   throws IllegalArgumentException, NumberFormatException {  
60.             int len = input.length();  
61.             char c, tempChar;  
62.             Stack<Character> s1 = new Stack<Character>();  
63.             Stack<Double> s2 = new Stack<Double>();  
64.             Stack<Object> expression = new Stack<Object>();  
65.             double number;  
66.             int lastIndex = -1;  
67.             for (int i=len-1; i>=0; --i) {  
68.                   c = input.charAt(i);  
69.                   if (Character.isDigit(c)) {  
70.                         lastIndex = readDoubleReverse(input, i);  
71.                         number = Double.parseDouble(input.substring(lastIndex, i+1));  
72.                         s2.push(number);  
73.                         i = lastIndex;  
74.                         if ((int) number == number)  
75.                               expression.push((int) number);  
76.                         else  
77.                               expression.push(number);  
78.                   } else if (isOperator(c)) {  
79.                         while (!s1.isEmpty()  
80.                                     && s1.peek() != ')'  
81.                                     && priorityCompare(c, s1.peek()) < 0) {  
82.                               expression.push(s1.peek());  
83.                               s2.push(calc(s2.pop(), s2.pop(), s1.pop()));  
84.                         }  
85.                         s1.push(c);  
86.                   } else if (c == ')') {  
88.                   } else if (c == '(') {  
89.                         while ((tempChar=s1.pop()) != ')') {  
90.                               expression.push(tempChar);  
91.                               s2.push(calc(s2.pop(), s2.pop(), tempChar));  
92.                               if (s1.isEmpty()) {  
93.                                     throw new IllegalArgumentException(  
94.                                           "bracket dosen't match, missing right bracket ')'.");  
95.                               }  
97.                   } else if (c == ' ') {  
98.                         // ignore  
99.                   } else {  
100.                         throw new IllegalArgumentException(  
101.                                     "wrong character '" + c + "'");  
104.             while (!s1.isEmpty()) {  
105.                   tempChar = s1.pop();  
106.                   expression.push(tempChar);  
107.                   s2.push(calc(s2.pop(), s2.pop(), tempChar));  
109.             while (!expression.isEmpty()) {  
110.                   System.out.print(expression.pop() + " ");  
112.             double result = s2.pop();  
113.             if (!s2.isEmpty())  
114.                   throw new IllegalArgumentException("input is a wrong expression.");  
115.             System.out.println();  
116.             if ((int) result == result)  
117.                   System.out.println("the result is " + (int) result);  
118.             else  
119.                   System.out.println("the result is " + result);  
122.        * parse the expression, and calculate it. 
127.       private static void toReversePolishNotation(String input)  
135.             for (int i=0; i<len; ++i) {  
137.                   if (Character.isDigit(c) || c == '.') {  
138.                         lastIndex = readDouble(input, i);  
139.                         number = Double.parseDouble(input.substring(i, lastIndex));  
141.                         i = lastIndex - 1;  
143.                               System.out.print((int) number + " ");  
145.                               System.out.print(number + " ");  
148.                                     && s1.peek() != '('  
149.                                     && priorityCompare(c, s1.peek()) <= 0) {  
150.                               System.out.print(s1.peek() + " ");  
151.                               double num1 = s2.pop();  
152.                               double num2 = s2.pop();  
153.                               s2.push(calc(num2, num1, s1.pop()));  
159.                         while ((tempChar=s1.pop()) != '(') {  
160.                               System.out.print(tempChar + " ");  
163.                               s2.push(calc(num2, num1, tempChar));  
166.                                           "bracket dosen't match, missing left bracket '('.");  
178.                   System.out.print(tempChar + " ");  
179.                   double num1 = s2.pop();  
180.                   double num2 = s2.pop();  
181.                   s2.push(calc(num2, num1, tempChar));  
193.        * calculate the two number with the operation. 
194.        * @param num1 
195.        * @param num2 
196.        * @param op 
197.        * @return 
200.       private static double calc(double num1, double num2, char op)  
201.                   throws IllegalArgumentException {  
202.             switch (op) {  
203.             case '+':  
204.                   return num1 + num2;  
205.             case '-':  
206.                   return num1 - num2;  
207.             case '*':  
208.                   return num1 * num2;  
209.             case '/':  
210.                   if (num2 == 0) throw new IllegalArgumentException("divisor can't be 0.");  
211.                   return num1 / num2;  
212.             default:  
213.                   return 0; // will never catch up here  
217.        * compare the two operations' priority. 
218.        * @param c 
219.        * @param peek 
222.       private static int priorityCompare(char op1, char op2) {  
223.             switch (op1) {  
224.             case '+': case '-':  
225.                   return (op2 == '*' || op2 == '/' ? -1 : 0);  
226.             case '*': case '/':  
227.                   return (op2 == '+' || op2 == '-' ? 1 : 0);  
229.             return 1;  
232.        * read the next number (reverse) 
234.        * @param start 
238.       private static int readDoubleReverse(String input, int start)  
240.             int dotIndex = -1;  
241.             char c;  
242.             for (int i=start; i>=0; --i) {  
244.                   if (c == '.') {  
245.                         if (dotIndex != -1)  
246.                               throw new IllegalArgumentException(  
247.                                     "there have more than 1 dots in the number.");  
249.                               dotIndex = i;  
250.                   } else if (!Character.isDigit(c)) {  
251.                         return i + 1;  
252.                   } else if (i == 0) {  
253.                         return 0;  
256.             throw new IllegalArgumentException("not a number.");  
259.        * read the next number 
265.       private static int readDouble(String input, int start)  
266.       throws IllegalArgumentException {  
270.             for (int i=start; i<len; ++i) {  
275.                               "there have more than 1 dots in the number.");  
276.                         else if (i == len - 1)  
278.                               "not a number, dot can't be the last part of a number.");  
282.                         if (dotIndex == -1 || i - dotIndex > 1)  
283.                               return i;  
287.                   } else if (i == len - 1) {  
288.                         return len;  
294.        * return true if the character is an operator. 
298.       private static boolean isOperator(char c) {  
299.             return (c=='+' || c=='-' || c=='*' || c=='/');  
301. }  

下面是程式運作結果（綠色為使用者輸入）：

== usage ==

input the expressions, and then the program will calculate them and show the result.

input 'bye' to exit.

input an expression:

3.8+5.3

Polish Notation (PN):+ 3.8 5.3

the result is 9.1

Reverse Polish Notation (RPN):3.8 5.3 +

input a new expression:

5*(9.1+3.2)/(1-5+4.88)

Polish Notation (PN):/ * 5 + 9.1 3.2 + - 1 5 4.88

the result is 69.88636363636364

Reverse Polish Notation (RPN):5 9.1 3.2 + * 1 5 - 4.88 + /

1+((2+3)*4)-5

Polish Notation (PN):- + 1 * + 2 3 4 5

the result is 16

Reverse Polish Notation (RPN):1 2 3 + 4 * + 5 -

bye

program exits