如果計算一個表達(dá)式，比如 4+5+6*2，隨著計算器的不同，簡單的四功能計算器是30，許多科學(xué)計算器知道乘法的優(yōu)先級高于加法，所以科學(xué)答案是21。典型計算順序可以是計算4+5，存為臨時變量a，再計算6*2，存為b，最后計算a+b可得出最后結(jié)果。這種操作順序如下：45+62*+

　　這種記法就是后綴表達(dá)式，其求值的過程就是上面描述的整個過程。那如何生成后綴表達(dá)式呢，也就是從中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，可以借助于棧來實現(xiàn)，整個步驟如下：

依次讀取輸入的表達(dá)式，如果是操作數(shù)，則把它放入到輸出中。

如果是操作符，棧為空的話直接將該操作符入棧；如果棧非空，則比較棧頂操作符和該操作符優(yōu)先級，如果棧頂操作符優(yōu)先級小于該操作符，則該操作符入棧；否則彈出棧頂操作符并將其放入到輸出中，直到棧為空或者發(fā)現(xiàn)優(yōu)先級更低的操作符為止。

如果是括號，比如'('和')'，則特殊處理。如果是'('的話，直接入棧；如果是')'，那么就將棧頂操作符彈出寫入到輸出中，直到遇到一個對應(yīng)的'('，但是這個'('只彈出不寫入到輸出中。注意："("可以理解為優(yōu)先級最高。

當(dāng)表達(dá)式讀取完畢后，如果棧中還有操作符，則依次彈出操作符并寫入到輸出中。

?

比如(1+2)*(3+2)-4/2表達(dá)式，其后綴表達(dá)式和計算結(jié)果為：

Java示例代碼如下：

import java.util.ArrayList; import java.util.List; import java.util.Stack;/*** MyComputer*/ public class MyComputer {public static int computer(String input) {List<String> cutList = cutInput(input);List<String> afterList = getAfterList(cutList);return getResultFromAfterList(afterList);}/*** 根據(jù)后綴表達(dá)式計算結(jié)果*/private static int getResultFromAfterList(List<String> afterList) {Stack<Integer> stack = new Stack<>();for (String ele : afterList) {if (isFlag(ele.charAt(0))) {int b = stack.pop();int a = stack.pop();stack.push(cal(a, b, ele.charAt(0)));} else {stack.push(Integer.valueOf(ele));}}if (stack.size() != 1) {throw new StackOverflowError();}return stack.pop();}/*** 獲取兩個數(shù)的計算結(jié)果*/private static int cal(int a, int b, char flag) {int result = 0;switch (flag) {case '+': {result = a + b;break;}case '-': {result = a - b;break;}case '*': {result = a * b;break;}case '/': {result = a / b;break;}default: {break;}}return result;}/*** 生成后綴表達(dá)式*/private static List<String> getAfterList(List<String> cutList) {List<String> output = new ArrayList<>();Stack<Character> stack = new Stack<>();for (String ele : cutList) {char flag = ele.charAt(0);if (isFlag(ele.charAt(0)) || (flag == '(') || (flag == ')')) {// 計算符入棧if (stack.isEmpty()) {stack.push(flag);} else {// 如果待入棧計算符大于棧頂計算符，則直接入棧；否則出棧直到棧為空或者待入棧計算符小于棧頂計算符if (flag == '(') {stack.push(flag);} else if (flag == ')') {while (stack.peek() != '(') {output.add(String.valueOf(stack.pop()));}stack.pop();}else if (isFlagSmaller(stack.peek(), flag)) {stack.push(flag);} else if (stack.peek() == '(') {stack.push(flag);} else{do {if (stack.peek() == '(') {break;}output.add(String.valueOf(stack.pop()));} while (!stack.isEmpty() && !isFlagSmaller(stack.peek(), flag));stack.push(flag);}}} else {// 數(shù)字直接添加到輸出中 output.add(ele);}}while (!stack.isEmpty()) {if ((stack.peek() != '(') || (stack.peek() != ')')) {output.add(String.valueOf(stack.pop()));}}return output;}/*** 將字符串以操作符為分隔符切片*/private static List<String> cutInput(String input) {List<String> cutList = new ArrayList<>();boolean running = true;while ((input.length() > 0) && running) {char c = input.charAt(0);if (isFlag(c) || (c == '(') || (c == ')')) {cutList.add(String.valueOf(c));input = input.substring(1);} else {for (int i = 0; i < input.length(); i++) {char tmpC = input.charAt(i);if (isFlag(tmpC) || (tmpC == '(') || (tmpC == ')')) {cutList.add(input.substring(0, i));cutList.add(String.valueOf(tmpC));input = input.substring(i + 1);break;}if (i == input.length() - 1) {cutList.add(input);running = false;}}}}return cutList;}/*** 判斷一個字符是否是操作符*/private static boolean isFlag(char c) {return (c == '+' || c == '-' || c == '*' || c == '/');}/*** 第一個操作符優(yōu)先級是否小于第二個*/private static boolean isFlagSmaller(char a, char b) {boolean flag = true;switch (a) {case '+':case '-': {if ((b == '+') || (b == '-')) {flag = false;}break;}case '*':case '/': {flag = false;}case '(': {flag = false;}default: {break;}}return flag;} }

?

后綴表達(dá)式和表達(dá)式樹

　　表達(dá)式樹是由后綴表達(dá)式構(gòu)造而來的，那么如何構(gòu)造呢，也是借助于棧來實現(xiàn)。上述代碼已經(jīng)實現(xiàn)了從中綴表達(dá)式轉(zhuǎn)換為為后綴表達(dá)式，整個步驟大致如下：

依次遍歷后綴表達(dá)式，如果是如果是操作數(shù)，則以其為數(shù)據(jù)創(chuàng)建一個單節(jié)點書，然后將該樹入棧。

如果是操作符，則從棧中彈出2棵樹T₁和T₂(T₁先彈出)并形成一個新的書，該樹的根就是該操作符，左右孩子分別是T₂和T₁，然后將這棵新樹入棧。

最后棧中會剩下一棵樹，則這棵樹就是表達(dá)式樹。具體代碼可以參考表達(dá)式樹。

?

總結(jié)

以上是生活随笔為你收集整理的如何生成后缀表达式的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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