栈的应用场景和介绍

栈的实际需求

计算式:[7*2*2-5+1-5*3-3]

image-20220930104602731

请问：计算机底层是如何运算的到结果的？我们看到的算式7*2*2-5，但是计算机怎么理解这个算式的(对于计算机而言，接收到的就是一个字符串)–>栈；

栈的介绍

  1. 栈的英文为(stack);
  2. 栈是一个先入后出(FILO-First In Last Out)的有序列表；
  3. 栈(stack)是限制线性表中元素的插入和删除只能再线性表的同一段进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(top)，另一端为固定的一端，称为栈底(bottom);
  4. 根据站的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除；

入栈和出栈示意图

入栈(push)，出栈(pop)

image-20220930110533733

栈的应用场景

  1. 子程序的调用：在跳往子程序前，会先将下个指令的地址存在堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中；
  2. 处理递归调用：和子程序的调用类似，只是除了存储下一个指令的地址外，也将参数，区域变量等数据存入堆栈中；
  3. 表达式的转换[中缀表达式和后缀表达式]与求值；
  4. 二叉树的遍历；
  5. 图形的深度优先(depth-first)搜索法;

栈的思路分析和代码实现

栈的快速入门

用数组模拟栈的使用，由于栈是一种有序列表，当然可以使用数组的结构来存储栈的数据内容，我们使用数组来模拟栈的出栈和入栈等操作；

数组模拟栈的思路分析

image-20220930121326624

  1. 使用数组来模拟栈；
  2. 定义一个top，来表示栈顶，初始为-1；
  3. 入栈的操作，当有数据加入到栈时，top++;stack[top]=data;
  4. 出栈的操作，int value = stack[top];top--;return value;

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
package com.jokerdig.stack;

/**
 * @author Joker大雄
 * @data 2022/9/30 - 12:17
 **/
public class ArrayStackDemo {
    public static void main(String[] args) {

    }
}
// 定义一个类ArrayStack，表示栈结构
class ArrayStack{
    private int maxSize; // 栈的大小
    private int[]stack; // 使用数组模拟栈，数据存放在该数组
    private int top = -1; // 栈顶，没有数据为-1

    // 构造器
    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[this.maxSize]; // 初始化
    }

    // 栈满
    public boolean isFull(){
        return top == maxSize-1;
    }

    // 栈空
    public boolean isEmpty(){
        return top == -1;
    }

    // 入栈
    public void push(int value){
        // 先判断栈是否满
        if(isFull()){
            System.out.println("栈满");
            return;
        }
        top++;
        stack[top] = value;
    }

    // 出栈
    public int pop(){
        // 先判断栈是否空
        if(isEmpty()){
            // 抛出异常
            throw new RuntimeException("栈空");
        }
        int value = stack[top];
        top--;
        return value;
    }

    // 遍历栈，遍历时要从栈顶开始
    public void listStack(){
        // 先判断栈是否为空
        if(isEmpty()){
            System.out.println("栈空");
            return;
        }
        for (int i = top; i >=0 ; i--) {
            System.out.printf("stack[%d]=%d\n",i,stack[i]);
        }
    }
}

栈的功能测试

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
package com.jokerdig.stack;

import java.util.Scanner;

/**
 * @author Joker大雄
 * @data 2022/9/30 - 12:17
 **/
public class ArrayStackDemo {
    public static void main(String[] args) {
        // 测试栈
        // 先创建ArrayStack对象
        ArrayStack arrayStack = new ArrayStack(4);
        String key = "";
        boolean flag = true; //控制是否退出菜单
        Scanner scanner = new Scanner(System.in);
        while(flag){
            System.out.println("=========栈功能测试==========");
            System.out.println("======show:表示显示栈=======");
            System.out.println("======exit:退出程序=======");
            System.out.println("======push:表示添加数据到栈=======");
            System.out.println("======pop:表示从栈取出数据=======");
            System.out.println("请输入要测试的功能");
            key = scanner.next();
            switch (key){
                case "show":
                    arrayStack.listStack();
                    break;
                case "exit":
                    scanner.close();
                    flag = false;
                    break;
                case "push":
                    System.out.println("请输入要添加栈的值");
                    int value = scanner.nextInt();
                    arrayStack.push(value);
                    break;
                case "pop":
                    try {
                        int val = arrayStack.pop();
                        System.out.printf("出栈的数据%d\n",val);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                default:
                    System.out.println("请输入正确的内容");
                    break;
            }
        }
        System.out.println("程序退出");
    }
}
// 定义一个类ArrayStack，表示栈结构
class ArrayStack{...}

运行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
=========栈功能测试==========
======show:表示显示栈=======
======exit:退出程序=======
======push:表示添加数据到栈=======
======pop:表示从栈取出数据=======
请输入要测试的功能
push
请输入要添加栈的值
1
=========栈功能测试==========
======show:表示显示栈=======
======exit:退出程序=======
======push:表示添加数据到栈=======
======pop:表示从栈取出数据=======
请输入要测试的功能
push
请输入要添加栈的值
2
=========栈功能测试==========
======show:表示显示栈=======
======exit:退出程序=======
======push:表示添加数据到栈=======
======pop:表示从栈取出数据=======
请输入要测试的功能
push
请输入要添加栈的值
3
=========栈功能测试==========
======show:表示显示栈=======
======exit:退出程序=======
======push:表示添加数据到栈=======
======pop:表示从栈取出数据=======
请输入要测试的功能
push
请输入要添加栈的值
4
=========栈功能测试==========
======show:表示显示栈=======
======exit:退出程序=======
======push:表示添加数据到栈=======
======pop:表示从栈取出数据=======
请输入要测试的功能
push
请输入要添加栈的值
5
栈满
=========栈功能测试==========
======show:表示显示栈=======
======exit:退出程序=======
======push:表示添加数据到栈=======
======pop:表示从栈取出数据=======
请输入要测试的功能
show
stack[3]=4
stack[2]=3
stack[1]=2
stack[0]=1
=========栈功能测试==========
======show:表示显示栈=======
======exit:退出程序=======
======push:表示添加数据到栈=======
======pop:表示从栈取出数据=======
请输入要测试的功能
pop
出栈的数据4
=========栈功能测试==========
======show:表示显示栈=======
======exit:退出程序=======
======push:表示添加数据到栈=======
======pop:表示从栈取出数据=======
请输入要测试的功能
pop
出栈的数据3
=========栈功能测试==========
======show:表示显示栈=======
======exit:退出程序=======
======push:表示添加数据到栈=======
======pop:表示从栈取出数据=======
请输入要测试的功能
pop
出栈的数据2
=========栈功能测试==========
======show:表示显示栈=======
======exit:退出程序=======
======push:表示添加数据到栈=======
======pop:表示从栈取出数据=======
请输入要测试的功能
pop
出栈的数据1
=========栈功能测试==========
======show:表示显示栈=======
======exit:退出程序=======
======push:表示添加数据到栈=======
======pop:表示从栈取出数据=======
请输入要测试的功能
pop
栈空
=========栈功能测试==========
======show:表示显示栈=======
======exit:退出程序=======
======push:表示添加数据到栈=======
======pop:表示从栈取出数据=======
请输入要测试的功能
exit
程序退出

Process finished with exit code

栈实现简单计算器思路分析

栈实现简单计算器

通过栈自定义运算优先级

输入表达式[7*2*2-5+1-5*3-3]，计算出结果；

image-20221003141232852

简单计算器思路分析：

  1. 通过一个index值(索引)，来遍历我们的表达式；
  2. 通过索引扫描，如果扫描到数字，有如下情况：
    • 在处理数，需要向表达式的index后再看一位，如果是数就继续扫描，如果index后是符号，就将该数入栈；
  3. 如果扫描到符号，有如下三种情况：
    • 如果符号栈为空，就直接入栈；
    • 如果符号栈有操作符，就进行比较，如果当前操作符的优先级小于或者等于栈中的操作符，就需要从数栈中pop出两个数，然后从符号栈中pop出一个符号，进行运算，将运算得到的结果入数栈，然后再将当前的操作符入符号栈；
    • 如果符号栈有操作符，且当前操作符的优先级大于栈中的操作符，就直接入符号栈；
  4. 当表达式扫描完毕，因为运算到最后一定是从前向后依次进行，所以先将数栈中的值依次放入数中转栈，然后将符号栈中的值依次放入数栈，最后按顺序的从数中转栈和数栈中pop出相应的数和符号，并运算，将最后的结果放入数中转栈中；
  5. 数中转栈最后只有一个数字，就是表达式的运算结果；

栈实现简单计算器代码

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
package com.jokerdig.stack;


/**
 * @author Joker大雄
 * @data 2022/10/3 - 11:17
 **/
public class Calculator {
    public static void main(String[] args) {
        // 完成中缀表达式7*2*2-5+1-5*3-3的运算
        String expression = "7*2*2-5+1-5*3-3";
        // 创建数栈、符号栈和数中转栈，注意：如果你的表达式很长，可以适当修改这里的栈大小
        CalculatorStack numStack = new CalculatorStack(20);
        CalculatorStack operStack = new CalculatorStack(20);
        CalculatorStack transferStack = new CalculatorStack(20);
        // 定义需要的变量
        int index = 0; // 用于扫描
        // 定义两个运算的数字，运算符和结果
        int num1 = 0,num2 = 0,oper=0,res = 0;
        // 将每次扫描得到的char
        char ch = ' ';
        // 用于拼接多位数
        String keepNum = "";
        // 开始扫描
        while(true){
            // 依次得到expression的每一个字符
            ch = expression.substring(index,index+1).charAt(0);
            // 判断ch是什么，然后做响应的处理
            if(operStack.isOper(ch)){
                // 如果时运算符，首先判断当前符号栈是否为空
                if(!operStack.isEmpty()){
                    // 如果不为空有操作符，就进行比较，如果当前操作符的优先级小于或者等于栈中的操作符，
                    // 就需要从数栈中pop出两个数，然后从符号栈中pop出一个符号，进行运算，将运算得到的结果入数栈，然后再将当前的操作符入符号栈；
                    if(operStack.priority(ch)<= operStack.priority(operStack.peek())){
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        oper = operStack.pop();
                        res = numStack.cal(num1,num2,oper);
                        // 把运算那结果入数栈
                        numStack.push(res);
                        // 把当前运算符放入符号栈
                        operStack.push(ch);
                    }else{
                        // 当前的运算符优先级大于栈中的运算符，就直接放入栈
                        operStack.push(ch);
                    }
                }else{
                    // 如果为空，直接入栈
                    operStack.push(ch);
                }
            }else{
                // 如果是数，需要判断是是单位数还是多位数
                // 注意，字符和数字之间相差48，例如字符1实际是49
                // umStack.push(ch - 48);
                // 处理多位数
                keepNum += ch;
                // 判断下一个字符是不是数字，如果是就继续扫描,若是运算符就出栈
                // 如果ch已经是expression的最后一位，就直接入栈
                if(index == expression.length()-1){
                    numStack.push(Integer.parseInt(keepNum));
                }else{
                    if(operStack.isOper(expression.substring(index+1,index+2).charAt(0))){
                        // 如果后一位是运算符，则入栈
                        numStack.push(Integer.parseInt(keepNum));
                        // 重要！清空keepNum
                        keepNum = "";
                    }
                }
            }
            // 让index+1，并判断是否扫描到最后
            index++;
            if(index>=expression.length()){
                break;
            }
        }
        /*
            当表达式扫描完毕，因为运算到最后一定是从前向后依次运算，所以先将数栈中的值依次放入数中转栈，
            然后将符号栈中的值依次放入数栈，最后按顺序的从数中转栈和数栈中pop出相应的数和符号，并运算，将最后的结果放入数中转栈中；
            数中转栈中只有一个数字，就是表达式的运算结果；
         */
        // 把数栈所有值都放入数中转栈
        while(!numStack.isEmpty()){
            transferStack.push(numStack.pop());
        }
        // 把符号栈所有值都放入数栈
        while(!operStack.isEmpty()){
            numStack.push(operStack.pop());
        }
        while(true){
            // 如果数栈为空，则计算到最后的结果
            if(numStack.isEmpty()){
                break;
            }
            // 注意，数中转栈和原本栈刚好相反，所以注意赋值的顺序
            num1 = transferStack.pop(); // 先弹出，在这里反而是大的值
            num2 = transferStack.pop(); // 后弹出，在这里是小的值
            oper = numStack.pop();
            res = transferStack.cal(num2,num1,oper);
            // 把运算那结果放入数中转栈
            transferStack.push(res);
        }
        System.out.printf("表达式%s运算结果: = %d",expression,transferStack.pop());
    }
}

// 先创建一个栈
class CalculatorStack {
    private int maxSize; // 栈的大小
    private int[] stack; // 使用数组模拟栈，数据存放在该数组
    private int top = -1; // 栈顶，没有数据为-1

    // 构造器
    public CalculatorStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[this.maxSize]; // 初始化
    }

    // 栈满
    public boolean isFull() {
        return top == maxSize - 1;
    }

    // 栈空
    public boolean isEmpty() {
        return top == -1;
    }

    // 入栈
    public void push(int value) {
        // 先判断栈是否满
        if (isFull()) {
            System.out.println("栈满");
            return;
        }
        top++;
        stack[top] = value;
    }

    // 出栈
    public int pop() {
        // 先判断栈是否空
        if (isEmpty()) {
            // 抛出异常
            throw new RuntimeException("栈空");
        }
        int value = stack[top];
        top--;
        return value;
    }

    // 返回运算符的优先级，我们假定数字越大，优先级越高
    public int priority(int oper) {
        if (oper == '*' || oper == '/') {
            return 1;
        } else if (oper == '+' || oper == '-') {
            return 0;
        } else {
            return -1; // 假定目前的表达式只有加减乘除
        }
    }

    // 返回当前栈顶的值，且不出栈
    public int peek(){
        return stack[top];
    }

    // 判断是否为运算符
    public boolean isOper(char val){
        return val == '+' || val == '-' || val == '*' || val =='/';
    }

    // 计算方法
    public int cal(int num1,int num2,int oper){
        int res = 0; //存放计算结果
        switch(oper){
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1; //注意相减顺序
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1; //注意相除顺序
                break;
            default:
                break;
        }
        return res;
    }
}

运行结果

1
2
表达式7*2*2-5+1-5*3-3运算结果: = 6
Process finished with exit code 0

前缀，中缀，后缀表达式规则

前缀表达式

  1. 前缀表达式又称波兰表达式，前缀表达式的运算符位于操作数之前；
  2. 举例说明：(3+4)×5-6对应的前缀表达式为：- × + 3 4 5 6;

前缀表达式计算机求值

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

例如：(3+4)×5-6对应的前缀表达式- × + 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. 中缀表达式就是我们常见的运算表达式，如(3+4)×5-6；
  2. 中缀表达式的求值是我们最熟悉的，但对计算机来说却不好操作，因此我们使用计算机时通常会将中缀表达式转为其他表达式操作;(一般转为后缀表达式)

后缀表达式

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

  2. 例如：(3+4)×5-6对应的后缀表达式为 3 4 + 5 × 6 -；

  3. 如下表：

    正常表达式 逆波兰表达式
    a+b a b +
    a+(b-c) a b c - +
    a+(b-c)*d a b c - d * +
    a+d*(b-c) a d b c - * +
    a=1+3 a 1 3 + =

后缀表达式计算机求值

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

例如：(3+4)×5-6对应的后缀表达式3 4 + 5 × 6 -，运算步骤如下：

  1. 从左至右扫描，将3和4压入栈堆；
  2. 遇到+运算符，因此弹出4和3(4为栈顶元素，3为次顶元素)，计算出3+4=7，再将7入栈；
  3. 将5入栈，接下来时×运算符，因此弹出5和7，计算出7×56=35，再将35入栈；
  4. 将6入栈，最后时-运算符，计算出35-6=29，得出最终结果；

逆波兰计算器思路分析

逆波兰计算器要求

  1. 输入一个逆波兰(后缀)表达式，使用栈(Stack)计算其结果；
  2. 支持小括号和多位整整数，因为这里我们主要讲解数据结构，所以堆计算器进行简化，只支持整数的计算；

思路分析

  1. 定义一个逆波兰表达式，变量名位suffixExpression
  2. 先将suffixExpression放到一个ArrayList集合中；
  3. 将ArrayList传递给一个方法，遍历ArrayList配合栈完成计算；

逆波兰计算器代码实现

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
package com.jokerdig.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author Joker大雄
 * @data 2022/10/4 - 14:05
 **/
public class PolandNotation {
    public static void main(String[] args) {
        // 先定义逆波兰表达式，为了方便我们使用空格隔开
        String suffixExpression = "3 4 + 5 x 6 -";
        // 获取集合
        List<String> rpnList = getListString(suffixExpression);
        int res = calculate(rpnList);
        System.out.printf("后缀表达式%s的计算结果为：%d",suffixExpression,res);
    }

    // 将逆波兰表达式依次放入ArrayList
    public static List<String> getListString(String suffixExpression){
        // 将suffixExpression分割
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<String>();
        for (String str : split) {
            list.add(str);
        }
        return list;
    }
    // 完成对逆波兰表达式的运算
    public static int calculate(List<String> ls){
        // 创建一个栈
        Stack<String> stack = new Stack<>();
        // 遍历ls
        for (String item : ls) {
            // 使用正则表达式取出数,\\d+ 匹配多为数
            if(item.matches("\\d+")){
                // 入栈
                stack.push(item);
            }else{
                // 从栈中pop出两个数进行运算，结果入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0; //存放结果
                // 进行运算
                if(item.equals("+")) {
                    res = num1 + num2;
                }else if(item.equals("-")){
                    res = num1 - num2;
                }else if(item.equals("×")){
                    res = num1 * num2;
                }else if(item.equals("/")){
                    res = num1 / num2;
                }
                // 把结果入栈
                stack.push(""+res);
            }
        }
        // 最后再栈中就是运算结果
        return Integer.parseInt(stack.pop());
    }
}

运算结果

1
2
后缀表达式3 4 + 5 x 6 -的计算结果为：29
Process finished with exit code 0

中缀转后缀表达式思路分析

后缀表达式适合计算式进行运算，但是人却不太容易写出来，尤其是表达式很长的情况下；因此在开发中，我们需要使用代码将中缀表达式转为后缀表达式；

具体步骤：

  1. 初始化两个栈，运算符栈s1和存储中间结果的栈s2；
  2. 从左至右扫描中缀表达式；
  3. 遇到数时，将其压入s2栈；
  4. 遇到运算符时，比较其与s1栈顶运算符的优先级：
    • 如果s1为空，或栈顶运算符为左括号(，则直接将此运算符入栈；
    • 若优先级比栈顶运算符高，也将运算符入s1栈；
    • 否则，将s1栈顶的运算符弹出并压入到s2中，再将当前运算符与s1中新的栈顶运算符进行比较(重复步骤4)；
  5. 遇到括号时：
    • 如果是左括号(，则直接入s1栈；
    • 如果是右括号)，则依次弹出s1栈顶的运算符，并入s2栈，直到遇到左括号为止，此时丢弃这一对括号；
  6. 重复步骤2至5，直到表达式的最右边；
  7. 将s1中剩余的运算符依次弹出并入s2栈；
  8. 依次弹出s2栈中的元素并输出，结果的逆序即为该中缀表达式对应的后缀表达式；

举例说明：

将中缀表达式1+((2+3)×4)-5转为后缀表达式；

屏幕截图 2022-10-05 104900

中缀转后缀表达式代码实现

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
package com.jokerdig.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author Joker大雄
 * @data 2022/10/4 - 14:05
 **/

public class PolandNotation {
    public static void main(String[] args) {
        /*
            实现中缀表达是转后缀表达式，并计算结果
            1. 举例表达式：1+((2+3)×4)-5 -> 1 2 3 + 4 × + 5 -
            2. 因为直接对字符串操作不方便，我们将其放入ArrayList
            // 即：1+((2+3)×4)-5 -> [1,+,(,(,2,+,3,),×,4,),-,5]
            3. 将得到的中缀表达式List转为->后缀表达式对应的List

        */
        String suffixExpression = "1+((2+3)×4)-5";
        // 将中缀表达式放入ArrayList
        List<String> infixExpressionList = toInfixExpressionList(suffixExpression);
        System.out.println("中缀表达式对应的List："+infixExpressionList);
        // 将中缀表达式转为后缀表达式，并返回
        List<String> suffixExpressionList = parseSuffixExpressionList(infixExpressionList);
        System.out.println("中缀表达式转后缀表达式对应的List："+suffixExpressionList);
        // 计算后缀表达式，并返回结果
        int result = calculate(suffixExpressionList);
        System.out.printf("%s=%d",suffixExpression,result);
    }
    // 将得到的中缀表达式List转为->后缀表达式对应的List
    public static List<String> parseSuffixExpressionList(List<String>  ls){
        // 定义s1栈和s2栈
        Stack<String> s1 = new Stack<>(); // 符号栈
        // 因为s2栈一直放入值，但是没有pop()值，可以使用ArrayList代替该栈
        List<String> s2 = new ArrayList<>();
        // 遍历ls
        for (String item : ls) {
            // 如果是一个数，就加入到s2
            if(item.matches("\\d+")){
                // 如果是数，放入s2
                s2.add(item);
            }else if(item.equals("(")){
                // 如果是左括号`(`，则直接入s1栈；
                s1.push(item);
            }else if(item.equals(")")){
                // 如果是右括号`)`，则依次弹出s1栈顶的运算符，并入s2栈，直到遇到左括号为止，此时丢弃这一对括号
                while(!s1.peek().equals("(")){
                    s2.add(s1.pop());
                }
                s1.pop(); // 将括号弹出s1,来消除括号
            }else{
                /*
                 当item的优先级小于等于栈顶运算符的优先级，
                 将s1栈顶的运算符弹出并压入到s2中，再将当前运算符与s1中新的栈顶运算符进行比较
                 */
                while(s1.size()!=0 && Operation.getValue(s1.peek())>=Operation.getValue(item)){
                    s2.add(s1.pop());
                }
                // 将item压入栈
                s1.push(item);
            }
        }
        // 将s1中所有运算符依次加入s2
        while(s1.size() != 0){
            s2.add(s1.pop());
        }
        // 返回s2，就是对应的后缀表达式
        return s2;
    }

    // 将中缀表达式转为对应的List
    public static List<String> toInfixExpressionList(String str){
        // 定义一个List，存放中缀表达式对应内容
        List<String> ls = new ArrayList<String>();
        int i = 0; // 指针，用于遍历中缀表达式字符串
        String s; // 做多位数拼接
        char c; // 没遍历一个字符，就放入到c
        do{
            // 如果c是非数字，就需要加入到ls
            if((c=str.charAt(i)) < 48 || (c=str.charAt(i)) > 57 ){
                ls.add(""+c);
                i++; // i后移
            } else {
                // 如果是数字，需要考虑多位数问题
                s = ""; //将string为空 0[48]->9[57]
                while(i < str.length() && (c=str.charAt(i))>=48 && (c=str.charAt(i))<=57){
                    s +=c; //拼接
                    i++;
                }
                ls.add(s);
            }
        }while(i<str.length());
        // 返回list
        return ls;
    }
    
    // 完成对逆波兰表达式的运算
    public static int calculate(List<String> ls){
        // 创建一个栈
        Stack<String> stack = new Stack<>();
        // 遍历ls
        for (String item : ls) {
            // 使用正则表达式取出数,\\d+ 匹配多为数
            if(item.matches("\\d+")){
                // 入栈
                stack.push(item);
            }else{
                // 从栈中pop出两个数进行运算，结果入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0; //存放结果
                // 进行运算
                if(item.equals("+")) {
                    res = num1 + num2;
                }else if(item.equals("-")){
                    res = num1 - num2;
                }else if(item.equals("×")){
                    res = num1 * num2;
                }else if(item.equals("/")){
                    res = num1 / num2;
                }
                // 把结果入栈
                stack.push(""+res);
            }
        }
        // 最后再栈中就是运算结果
        return Integer.parseInt(stack.pop());
    }
}

// 编写一个类Operation，返回运算符的优先级
class Operation {
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;

    // 写一个方法，返回优先级对应的数字
    public static int getValue(String operation){
        int result = 0;
        switch (operation){
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "×":
                result = MUL;
                break;
            case "/":
                result = DIV;
                break;
            default:
                break;

        }
        return result;
    }
}

运行结果

1
2
3
4
中缀表达式对应的List：[1, +, (, (, 2, +, 3, ), ×, 4, ), -, 5]
中缀表达式转后缀表达式对应的List：[1, 2, 3, +, 4, ×, +, 5, -]
1+((2+3)×4)-5=16
Process finished with exit code 0