【Java数据结构和算法】009-栈：前缀、中缀、后缀表达式（逆波兰表达式）

「爱情、让人受尽委屈。」 2023-10-05 13:39 33阅读 0赞

# **目录** #

0、警醒自己

一、前缀表达式

1、概述

2、前缀表达式的计算求值逻辑

二、中缀表达式

1、概述

三、后缀表达式

1、概述

2、后缀表达式计算求值逻辑

3、逆波兰计算器

表达式：

要求：

代码实现：

运行结果：

四、中缀表达式转后缀表达式【重点】

1、步骤

2、举个例子

3、说明

举例子：

算法 = 武功秘籍：

掌握算法两重天：

4、代码实现

5、运行结果（完美）

--------------------

# 0、警醒自己 #

**1、学习不用心，骗人又骗己；**

**2、学习不刻苦，纸上画老虎；**

**3、学习不惜时，终得人耻笑；**

**4、学习不复习，不如不学习；**

**5、学习不休息，毁眼伤身体；**

**7、狗才等着别人喂，狼都是自己寻找食物；**

# 一、前缀表达式 #

## 1、概述 ##

①前缀表达式(波兰表达式)：前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前；

②举例说明： (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6；

（PS：符号逆序走前面，数字顺序走后面；）

（PS：这么看来前缀表达式就是符号放前面，类似“1+1”就是中缀表达式，那后缀表达式就是将符号放后面（实际上不完全相似，具体见后缀表达式））

## 2、前缀表达式的计算求值逻辑 ##

**从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 和 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果；**

例如：(3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 , 针对前缀表达式求值步骤如下：

①从右至左扫描，将6、5、4、3压入堆栈；

②遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素），计算出3+4的值，得7，再将7入栈；

③接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈 最后是-运算符，计算出35-6的值，即29，由此得出最终结果；

# 二、中缀表达式 #

## 1、概述 ##

①中缀表达式就是常见的运算表达式，如(3+4)×5-6；

②中缀表达式的求值是我们人最熟悉的，但是对计算机来说却不好操作(前面我们讲的案例就能看的这个问题)，因此，在计算结果时，往往会将中缀表达式转成其它表达式来操作（一般转成后缀表达式）；

# 三、后缀表达式 #

## 1、概述 ##

后缀表达式又称**逆波兰表达式**，与前缀表达式相似，只是运算符位于操作数之后；

中举例说明： (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –；

再比如：

<table style="width:453px;"> 
 <tbody> 
 <tr> 
 <td> 正常的表达式 </td> 
 <td> 逆波兰表达式 </td> 
 </tr> 
 <tr> 
 <td> a+b </td> 
 <td> a&nbsp;b&nbsp;+ </td> 
 </tr> 
 <tr> 
 <td> a+(b-c) </td> 
 <td> a&nbsp;b&nbsp;c&nbsp;-&nbsp;+ </td> 
 </tr> 
 <tr> 
 <td> a+(b-c)*d </td> 
 <td> a&nbsp;b&nbsp;c&nbsp;–&nbsp;d&nbsp;*&nbsp;+ </td> 
 </tr> 
 <tr> 
 <td> a+d*(b-c) </td> 
 <td> a&nbsp;d&nbsp;b&nbsp;c&nbsp;-&nbsp;*&nbsp;+ </td> 
 </tr> 
 <tr> 
 <td> a=1+3 </td> 
 <td> a&nbsp;1&nbsp;3&nbsp;+&nbsp;= </td> 
 </tr> 
 </tbody> 
</table>

## 2、后缀表达式计算求值逻辑 ##

**从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果；**

例如：(3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下：

①从左至右扫描，将3和4压入堆栈；

②遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；

③将5入栈；

④接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；

⑤将6入栈；

⑥最后是-运算符，计算出35-6的值，即29，由此得出最终结果；

PS：根据逻辑说明可以很简单地实现计算逻辑，现在的关键问题就是如何将中缀表达式转成后缀表达式了；

## 3、逆波兰计算器 ##

### 表达式： ###

正常表达式：a+(b-c)\*d —— 逆波兰表达式：a b c – d \* +

例如：3+(8-5)\*4；

### 要求： ###

①输入一个逆波兰表达式(后缀表达式)，使用栈(Stack), 计算其结果；

②支持小括号和一位整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算；

### 代码实现： ###

（使用后缀表达式计算）

package com.zb.ds;
 
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.List;
 import java.util.Stack;
 
 public class MStack {
 public static void main(String[] args) {
 //表达式3+(8-5)*4 ——> 3 8 5 – 4 * +
 String expression = "3 8 5 - 4 * +";//为了方便，我们将表达式每个单位之间使用空格隔开
 //创建一个数栈
 Stack<Integer> numStack = new Stack<>();
 //遍历表达式
 String[] split = expression.split(" ");
 List<String> list = new ArrayList<>(Arrays.asList(split));
 for (String s : list) {
 //如果不是符号，就入栈
 if(!isOperator(s)){
 //入栈之前转成数字
 int num = Integer.parseInt(s);
 numStack.push(num);
 System.out.println(num + "入栈成功！");
 }else {
 //是符号，弹出两个数，进行计算，并将计算的结果入栈
 Integer num1 = numStack.pop();
 Integer num2 = numStack.pop();
 //注意运算的顺序
 int res = cal(num1, num2, s);
 numStack.push(res);
 System.out.println(res + "入栈成功！");
 }
 }
 //最后栈里面只有一个值，就是结果
 System.out.println("最终计算结果：" + numStack.pop());
 }
 //判断是否是符号
 //判断是否是一个操作符
 public static boolean isOperator(String s){
 return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/");
 }
 
 //计算方法
 public static int cal(int num1, int num2, String oper){
 int res;//res用来存储计算结果
 switch (oper){
 case "+":
 res = num1 + num2;
 break;
 case "-":
 res = num2 - num1;
 break;
 case "*":
 res = num1 * num2;
 break;
 case "/":
 res = num2 / num1;
 break;
 default:
 throw new RuntimeException("意料之外的情况，操作符为：" + oper);
 }
 return res;
 }
 }

### 运行结果： ###

3入栈成功！
    8入栈成功！
    5入栈成功！
    3入栈成功！
    4入栈成功！
    12入栈成功！
    15入栈成功！
    最终计算结果：15

# 四、中缀表达式转后缀表达式【重点】 #

## 1、步骤 ##

①初始化两个栈：运算符栈s1和储存中间结果的栈s2；

②从左至右扫描中缀表达式；

③遇到操作数时，将其压s2；

④遇到运算符时，比较其与s1栈顶运算符的优先级：

如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；

否则，若优先级比栈顶运算符的高，也将运算符压入s1；

否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；

⑤遇到括号时：

(1) 如果是左括号“(”，则直接压入s1；

(2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃；

⑥重复步骤2至5，直到表达式的最右边；

⑦将s1中剩余的运算符依次弹出并压入s2；

⑧依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式；

## 2、举个例子 ##

举例说明: 将中缀表达 式“1+((2+3)×4)-5”转 换为后缀表达式的过程如下：

（结果为 "1 2 3 + 4 × + 5 –"）

<table style="width:476pt;"> 
 <tbody> 
 <tr> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> 扫描到的元素 </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:96pt;"> s2(栈底-&gt;栈顶) </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> s1&nbsp;(栈底-&gt;栈顶) </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:198pt;"> 说明 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> 1 </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:96pt;"> 1 </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> 空 </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:198pt;"> 数字，直接入栈 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> + </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:96pt;"> 1 </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> + </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:198pt;"> s1为空，运算符直接入栈 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> ( </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:96pt;"> 1 </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> +&nbsp;( </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:198pt;"> 左括号，直接入栈 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> ( </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:96pt;"> 1 </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> +&nbsp;(&nbsp;( </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:198pt;"> 同上 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> 2 </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:96pt;"> 1&nbsp;2 </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> +&nbsp;(&nbsp;( </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:198pt;"> 数字 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> + </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:96pt;"> 1&nbsp;2 </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> +&nbsp;(&nbsp;(&nbsp;+ </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:198pt;"> s1栈顶为左括号，运算符直接入栈 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> 3 </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:96pt;"> 1&nbsp;2&nbsp;3 </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> +&nbsp;(&nbsp;(&nbsp;+ </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:198pt;"> 数字 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> ) </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:96pt;"> 1&nbsp;2&nbsp;3&nbsp;+ </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> +&nbsp;( </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:198pt;"> 右括号，弹出运算符直至遇到左括号 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> × </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:96pt;"> 1&nbsp;2&nbsp;3&nbsp;+ </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> +&nbsp;(&nbsp;× </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:198pt;"> s1栈顶为左括号，运算符直接入栈 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> 4 </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:96pt;"> 1&nbsp;2&nbsp;3&nbsp;+&nbsp;4 </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> +&nbsp;(&nbsp;× </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:198pt;"> 数字 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> ) </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:96pt;"> 1&nbsp;2&nbsp;3&nbsp;+&nbsp;4&nbsp;× </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> + </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:198pt;"> 右括号，弹出运算符直至遇到左括号 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> - </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:96pt;"> 1&nbsp;2&nbsp;3&nbsp;+&nbsp;4&nbsp;×&nbsp;+ </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> - </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:198pt;"> -与+优先级相同，因此弹出+，再压入- </td> 
 </tr> 
 <tr> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> 5 </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:96pt;"> 1&nbsp;2&nbsp;3&nbsp;+&nbsp;4&nbsp;×&nbsp;+&nbsp;5 </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> - </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:198pt;"> 数字 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> 到达最右端 </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:96pt;"> 1&nbsp;2&nbsp;3&nbsp;+&nbsp;4&nbsp;×&nbsp;+&nbsp;5&nbsp;- </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:90pt;"> 空 </td> 
 <td style="border-color:#c0c0c0;vertical-align:middle;width:198pt;"> s1中剩余的运算符 </td> 
 </tr> 
 </tbody> 
</table>

## 3、说明 ##

我们看到，**中缀表达式转后缀表达式实现算法是相当复杂的**，我们学习之后运用，很难自创一个这样的新算法；

### 举例子： ###

**降龙十八掌：**

**学习——运用【低层次】；**

**自创【高层次】；**

### **算法 = 武功秘籍：** ###

**你是跟着别人的武功秘籍走，还是自创武功，这就是层次的区别！**

### 掌握算法两重天： ###

第一重：学会，然后灵活运用；

第二重：自创，然后发扬光大；

## 4、代码实现 ##

（根据思路自己写出了代码）

package com.zb.ds;
 
 import java.util.ArrayList;
 import java.util.List;
 import java.util.Stack;
 
 //中缀表达式转后缀表达式
 public class MeToEe {
 public static void main(String[] args) {
 //中缀表达式例子：1+((2+3)×4)-5
 String expression = "1+((2+3)×4)-5";
 //①初始化两个栈：运算符栈operatorStack和储存中间结果栈numberStack；
 //运算符栈
 Stack<Character> operatorStack = new Stack<>();
 //储存中间结果栈
 Stack<Character> resultStack = new Stack<>();
 //②从左至右扫描中缀表达式；
 char[] chars = expression.toCharArray();
 for (char c : chars) {
 //③遇到操作数时，将其压numberStack；
 judgeAndPush(c,operatorStack,resultStack);
 }
 //遍历完了，将s1中剩余的运算符依次弹出并压入s2；
 while (!operatorStack.empty()){
 resultStack.push(operatorStack.pop());
 }
 //逆序
 List<Character> list = new ArrayList<>();
 while (!resultStack.empty()){
 list.add(resultStack.pop());
 }
 for (int i = list.size()-1; i >-1; i--) {
 System.out.print(list.get(i) + " ");
 }
 }
 
 //judge
 public static void judgeAndPush(char c,Stack<Character> operatorStack,Stack<Character> resultStack){
 //这个时候需要写一个判断是否是运算符的方法
 if(isOperator(c)){//运算符
 //如果符号栈为空，直接入栈
 if(operatorStack.empty() || isBracket(operatorStack.peek())==1){
 operatorStack.push(c);
 }else {
 //若优先级比栈顶运算符的高，也将运算符压入符号栈
 //写一个比较符号优先级的方法
 //peek方法是偷窥的意思，知道栈顶是谁，又不使其出栈
 Character top = operatorStack.peek();
 if(getPriority(c) > getPriority(top)){
 operatorStack.push(c);
 }else {
 //否则，将符号栈顶的运算符弹出并压入到结果栈中，再次转到(4-1)与符号中新的栈顶运算符相比较
 resultStack.push(operatorStack.pop());
 //再次转到(4-1)，调用自己
 judgeAndPush(c,operatorStack,resultStack);
 }
 }
 }else if(isBracket(c)!=0){//括号
 if(isBracket(c)==1){//左括号
 operatorStack.push(c);
 }else {
 while (isBracket(operatorStack.peek())!=1){
 resultStack.push(operatorStack.pop());
 }
 //这个时候偷窥到(了，要弹出来
 operatorStack.pop();
 }
 }else {
 //是数字
 resultStack.push(c);
 }
 }
 
 //判断是否是运算符
 public static boolean isOperator(char c){
 return c == '+' || c == '-' || c == '×' || c == '/';
 }
 
 //判断是否是括号，左括号为1，右括号为2
 public static int isBracket(char c){
 if(c == '('){
 return 1;
 }else if(c == ')'){
 return 2;
 }else {
 return 0;
 }
 }
 
 //比较符号优先级，+-1 */2
 public static int getPriority(char c){
 switch (c){
 case '+':
 case '-':
 return 1;
 case '*':
 case '/':
 return 2;
 default:
 throw new RuntimeException("不是符号！" + c);
 }
 }
 }

## 5、运行结果（完美） ##

（再加上上面的逆波兰计算器，一个完美的计算器就写好了，中缀表达式——后缀表达式——逆波兰计算器）

1 2 3 + 4 × + 5 -