當(dāng)前位置：首頁(yè) > 编程资源 > 编程问答 >内容正文

编程问答

前缀、中缀和后缀表达式详解，中缀表达式到后缀表达式的转换规则，以及后缀表达式的计算规则，附计算代码

發(fā)布時(shí)間：2025/3/19 编程问答 23 豆豆

生活随笔收集整理的這篇文章主要介紹了前缀、中缀和后缀表达式详解，中缀表达式到后缀表达式的转换规则，以及后缀表达式的计算规则，附计算代码小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

1. 中綴、前綴和后綴表達(dá)式

1.1 中綴表達(dá)式

首先，中綴表達(dá)式的這個(gè)“綴”指運(yùn)算符在兩個(gè)操作數(shù)的位置。中綴表達(dá)式其實(shí)就是我們常用的算術(shù)表達(dá)式，比如 2 + 9 - (32?* (19 - 4) +14)，我們很容易就可以得到計(jì)算結(jié)果，但是對(duì)于計(jì)算機(jī)來(lái)說(shuō)，它們就得對(duì)各個(gè)運(yùn)算符進(jìn)行優(yōu)先級(jí)比較以及彈棧和入棧等操作，其實(shí)計(jì)算機(jī)對(duì)于前綴表達(dá)式和后綴表達(dá)式更容易理解。

1.2 前綴表達(dá)式

前綴表達(dá)式，也稱(chēng)波蘭式，指運(yùn)算符處于兩個(gè)操作數(shù)的前面，比如 2 + 3，那么前綴表達(dá)式就是 + 2 3；對(duì)于復(fù)雜點(diǎn)的表達(dá)式，如 13 * ((3 + 8) * 4)，前綴表達(dá)式為 * 13 * + 3 8 4，后續(xù)分析怎么轉(zhuǎn)換。

1.3?后綴表達(dá)式

也稱(chēng)逆波蘭式，指運(yùn)算符處于兩操作數(shù)后面，比如 2 + 3，后綴表達(dá)式為 2 3 +；對(duì)于復(fù)雜點(diǎn)的表達(dá)式，如?13 * ((3 + 8) * 4)，后綴表達(dá)式為?13 3 8 + 4 * *，后續(xù)會(huì)講怎么轉(zhuǎn)換。

2. 中綴表達(dá)式到后綴表達(dá)式的轉(zhuǎn)換規(guī)則

前面我們提到計(jì)算機(jī)易于理解前綴表達(dá)式和后綴表達(dá)式，但我們生活中或使用計(jì)算器時(shí)是中綴表達(dá)式，這也就意味著我們需要將中綴表達(dá)式轉(zhuǎn)換為前綴或后綴表達(dá)式，從而實(shí)現(xiàn)計(jì)算器的高效計(jì)算。

中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的規(guī)則如下：

1.創(chuàng)建運(yùn)算符棧s1和操作數(shù)數(shù)組a2，然后掃描中綴表達(dá)式；2.如果是操作數(shù)，直接放入數(shù)組a2；3.如果是運(yùn)算符，棧s1為空或棧頂符號(hào)為左括號(hào)，或者優(yōu)先級(jí)比棧頂運(yùn)算符高，則入棧結(jié)束該步驟；否則將s1棧頂運(yùn)算符彈出放入操作數(shù)數(shù)組a2，然后重復(fù)該步驟3。4.如果是左括號(hào)，直接壓入運(yùn)算符棧s1；如果是右括號(hào)，依次彈出s1的運(yùn)算符放入s2，直至遇到左括號(hào)結(jié)束，并將左、右括號(hào)舍棄。5.循環(huán)步驟2-4直至表達(dá)式掃描結(jié)束，將s1的剩余運(yùn)算符依次彈出放入數(shù)組a2，數(shù)組a2就是后綴表達(dá)式。

以下演示一個(gè)較復(fù)雜中綴表達(dá)式 3 * (11 - 8) - 45 / ((98 - 60) / 10 + 6) ?轉(zhuǎn)換后綴表達(dá)式的流程，流程如下。

1. 先創(chuàng)建運(yùn)算符棧s1,和操作數(shù)數(shù)組a2，然后索引指向中綴表達(dá)式的第一位；

2. 3是操作數(shù)，放入數(shù)組a2的第一個(gè)位置，得到a2 = {3}；

3. *是運(yùn)算符，因?yàn)闂1為空，*直接入棧s1，s1 = ；

4. 遇到左括號(hào)，直接壓入運(yùn)算符棧s1，s1 =?；

5. 11是操作數(shù)，直接放入數(shù)組a2，得到a2 = {3, 11}；

6. - 是運(yùn)算符，因?yàn)闂ｍ敺?hào)是左括號(hào)，- 直接入棧得到s1 =?

7.?8是操作數(shù)，直接放入數(shù)組a2，得到a2 = {3, 11, 8}；

8. 遇到右括號(hào)，彈出s1中的運(yùn)算符 - ，直到遇到左括號(hào)結(jié)束；此時(shí)a2={3, 11, 8, -}，s1?=?

9.?- 是運(yùn)算符，因?yàn)閮?yōu)先級(jí)低于棧頂符號(hào) * ，將s1棧頂符號(hào)彈出放入數(shù)組a2，a2變?yōu)閧3, 11, 8, -, *}，s1?=?

10. 重復(fù)步驟3，由于此時(shí)棧為空，則 - 直接入棧，s1?=?

11. 45是操作數(shù)，直接放入數(shù)組a2，得到a2 = {3, 11, 8, -, *, 45}；

12. / 是運(yùn)算符，而且運(yùn)算優(yōu)先級(jí)高于s1的棧頂符號(hào) -，所以直接入棧，s1 =?

13.?遇到左括號(hào)，直接壓入運(yùn)算符棧s1，s1 =?；

14.?遇到左括號(hào)，直接壓入運(yùn)算符棧s1，s1 =?；

15. 98是操作數(shù)，直接放入數(shù)組a2，得到a2 = {3, 11, 8, -, *, 45, 98}；

16.?- 是運(yùn)算符，因?yàn)闂ｍ敺?hào)是左括號(hào)，- 直接入棧,得到s1 =?

17. 60是操作數(shù)，直接放入數(shù)組a2，得到a2 = {3, 11, 8, -, *, 45, 98, 60}；

18.?遇到右括號(hào)，彈出s1中的運(yùn)算符 - ，直到遇到左括號(hào)結(jié)束；此時(shí)a2={3, 11, 8, -, *, 45, 98, 60, -}，s1?=?

19.?/ 是運(yùn)算符，而且棧頂符號(hào)是左括號(hào)，/?直接入棧，得到s1 =?

20. 10是操作數(shù)，直接放入數(shù)組a2，得到a2 = {3, 11, 8, -, *, 45, 98, 60, -, 10}；

21. +?是運(yùn)算符，因?yàn)閮?yōu)先級(jí)低于棧頂符號(hào) /?，將s1棧頂符號(hào) / 彈出放入數(shù)組a2，a2變?yōu)閧3, 11, 8, -, *, 45, 98, 60, -, 10, /}，

? ? ? s1 =?

22. + 運(yùn)算符接著和棧頂符號(hào)比較，此時(shí)由于棧頂符號(hào)是左括號(hào)，直接入棧，s1 =?

23. 6是操作數(shù)，直接放入數(shù)組a2，得到a2 = {3, 11, 8, -, *, 45, 98, 60, -, 10, /, 6}；

24.?遇到右括號(hào)，彈出s1中的運(yùn)算符 +?，直到遇到左括號(hào)結(jié)束；此時(shí)a2={3, 11, 8, -, *, 45, 98, 60, -, 10, /, 6, +}，

? ? ?s1 =?

25. 掃描結(jié)束，彈出s1中剩余運(yùn)算符至數(shù)組a2，得到a2 = {3, 11, 8, -, *, 45, 98, 60, -, 10, /, 6, +, /, -}

因此，最終得到的后綴表達(dá)式為?3?11?8?-?*?45?98?60?-?10?/?6?+?/?-

代碼如下

3. 后綴表達(dá)式的計(jì)算原則

我們得到后綴表達(dá)式?3?11?8?-?*?45?98?60?-?10?/?6?+?/?-，那么怎么計(jì)算呢？其實(shí)，后綴表達(dá)式計(jì)算原則很簡(jiǎn)單，主要分為三步，如下

1. 創(chuàng)建一個(gè)棧，并且從左至右掃描表達(dá)式；

2. 遇到數(shù)字，將數(shù)字壓入棧中；遇到運(yùn)算符則彈出棧頂?shù)膬蓚€(gè)元素，使用運(yùn)算符進(jìn)行計(jì)算，然后將計(jì)算結(jié)果再壓入棧中；

3.?重復(fù)步驟2直到表達(dá)式掃描結(jié)束，最后彈出棧頂元素就是計(jì)算結(jié)果。

以上示例后綴表達(dá)式的計(jì)算步驟如下：

1. 創(chuàng)建棧stack，掃描表達(dá)式，將數(shù)字3, 11, 8依次壓入棧stack，得到stack =?

2. 遇到運(yùn)算符 - ，棧stack彈出 8 和 11，計(jì)算 11 - 8 得到3，入棧得到stack =?

3.?遇到運(yùn)算符 *?，棧stack彈出 3?和 3，計(jì)算得到 9，入棧得到stack =?

4. 將數(shù)字45, 98, 60壓入棧，得到stack =?

5.?遇到運(yùn)算符 - ，棧stack彈出 60?和 98，計(jì)算 98- 60得到38，入棧得到stack =?

6.?將數(shù)字10壓入棧，得到stack =?

7.?遇到運(yùn)算符 /?，棧stack彈出 10?和 38，計(jì)算 38 /?10得到3 (java整數(shù)相除得到整數(shù)3，其它變成語(yǔ)言可得到3.8)，入棧得到

? ? stack =?

8.?將數(shù)字6壓入棧，得到stack =?

9. 遇到運(yùn)算符 +?，棧stack彈出 6?和 3，計(jì)算 3 + 6 得到9，入棧得到stack =?

10.?遇到運(yùn)算符 /?，棧stack彈出 9?和 45，計(jì)算 45?/?9?得到5，入棧得到stack =?

11.?遇到運(yùn)算符 -?，棧stack彈出 5?和 9，計(jì)算 9?-?5?得到4，入棧得到stack =?

12. 計(jì)算結(jié)束，彈出棧頂元素 4，所以計(jì)算結(jié)果為4.

代碼如下

static String calculate(List<String> ls){Stack<String> st_result = new Stack();for (String s:ls) {// 因?yàn)檫@個(gè)計(jì)算后綴表達(dá)式的方法是和中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式聯(lián)合使用的，而且中綴表達(dá)式// 轉(zhuǎn)換后綴表達(dá)式的方法中考慮了運(yùn)算符異常等異常，所以以下代碼不考慮異常情況if(("-".equals(s)) || ("+".equals(s)) || ("*".equals(s)) || ("/".equals(s))){int num_back = Integer.valueOf(st_result.pop());int num_front = Integer.valueOf(st_result.pop());switch(s){case "-":st_result.push((num_front - num_back) + "");break;case "/":st_result.push((num_front / num_back) + "");break;case "+":st_result.push((num_front + num_back) + "");break;case "*":st_result.push((num_front * num_back) + "");break;}}else {st_result.push(s);}}return st_result.pop();}

?

完整測(cè)試代碼以運(yùn)行結(jié)果如下

static int priority(char c1){if((c1 == '*') || (c1 == '/')){return 2;}else{return 1;}}static List infixToPostfix(String infixExpress){char c;Stack s1 = new Stack();List<String> a2 = new ArrayList();for (int i = 0; i < infixExpress.length(); i++) {c = infixExpress.charAt(i);if((c == '*') || (c == '/') || (c == '+') || (c == '-')){//如果棧空、棧頂元素是左括號(hào)，或者運(yùn)算符優(yōu)先級(jí)高于棧頂元素優(yōu)先級(jí)，則入棧if((s1.isEmpty()) || ((char)s1.lastElement() == '(') || (priority(c) > priority((char)s1.lastElement()))){s1.push(c);}else{a2.add(String.valueOf(s1.pop()));//循環(huán)比較，直至運(yùn)算符可以入棧，結(jié)束；否則一直將棧頂元素彈出放入數(shù)組a2while(!(s1.isEmpty() || ((char)s1.lastElement() == '(') || (priority(c) > priority((char)s1.lastElement())))){a2.add(String.valueOf(s1.pop()));}s1.push(c);}}else if(c == '('){s1.push(c);}else if(c == ')'){char c2 = (char)s1.pop();//循環(huán)比較，直至匹配到左括號(hào)結(jié)束；否則一直將棧頂元素彈出放入數(shù)組a2while(c2 != '('){a2.add(String.valueOf(c2));c2 = (char)s1.pop();}}else if((c >= 48) && (c <= 57)){//如果是最后一位，那么直接將數(shù)字放入數(shù)組a2，結(jié)束if(i == infixExpress.length()-1){a2.add(String.valueOf(c));}else{String s2 = "" + c;int cnt = 1;char c3 = infixExpress.charAt(i+cnt);while((c3 >= 48) && (c3 <= 57)){s2 += c3;cnt++;//一直掃描數(shù)字，直至中綴表達(dá)式末尾，結(jié)束if(i+cnt < infixExpress.length()){c3 = infixExpress.charAt(i+cnt);}else{break;}}i += (cnt-1);a2.add(s2);}}else{//如果字符是空格或者表達(dá)式最后一個(gè)字符是 = ，不操作，否則表達(dá)式異常if(((i == infixExpress.length()-1) && (c == '=')) || (c == ' ')){}else{System.out.println("Express is fault");}}}//最后需要將s1剩余的運(yùn)算符彈出，放入數(shù)組a2中。while(! s1.isEmpty()){a2.add(String.valueOf(s1.pop()));}return a2;}static String calculate(List<String> ls){Stack<String> st_result = new Stack();for (String s:ls) {// 因?yàn)檫@個(gè)計(jì)算后綴表達(dá)式的方法是和中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式聯(lián)合使用的，而且中綴表達(dá)式// 轉(zhuǎn)換后綴表達(dá)式的方法中考慮了運(yùn)算符異常等異常，所以以下代碼不考慮異常情況if(("-".equals(s)) || ("+".equals(s)) || ("*".equals(s)) || ("/".equals(s))){int num_back = Integer.valueOf(st_result.pop());int num_front = Integer.valueOf(st_result.pop());switch(s){case "-":st_result.push((num_front - num_back) + "");break;case "/":st_result.push((num_front / num_back) + "");break;case "+":st_result.push((num_front + num_back) + "");break;case "*":st_result.push((num_front * num_back) + "");break;}}else {st_result.push(s);}}return st_result.pop();}public static void main(String[] args) {String s = "3 * (11 - 8) - 45 / ((98 - 60) / 10 + 6)";List posefixList = infixToPostfix(s);System.out.print("后綴表達(dá)式為：");for (Object o:posefixList) {System.out.print(o + " ");}System.out.println("\n后綴表達(dá)式計(jì)算結(jié)果是 " + calculate(posefixList));}

總結(jié)

以上是生活随笔為你收集整理的前缀、中缀和后缀表达式详解，中缀表达式到后缀表达式的转换规则，以及后缀表达式的计算规则，附计算代码的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

上一篇：修饰符private和protected
下一篇：八皇后问题的Java递归算法