栈的简单实现与应用

本文最后更新于：2 年前

关于栈（Stack）

  1. 栈是一个先入后出（FILO - first in last out）的有序列表。

  2. 栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶（Top），另一端为固定的一端，称为栈底（Bottom）。

  3. 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。

  4. 出栈（pop）和入栈（push）概念图：

    入栈、出栈示意图

  5. 栈的应用场景：

    • 子程序的调用

      在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。

    • 处理递归调用

      和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。

    • 表达式的转换

      中缀表达式转后缀表达式 与 求值（实际解决）。

    • 二叉树的遍历。

    • 图形的深度优先（depth一first）搜索法。

数组模拟栈

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

思路分析

  1. 定义一个 top ，用来表示栈顶，初始化为 -1。

    数组模拟栈

  2. 当有数据加入到栈中时：

    1
    2
    top++;
    stack[top] = data;

  3. 当有数据从栈中弹出时：

    1
    2
    3
    int value = stack[top];
    top--;
    return value;

代码实现

  1. 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
    public class ArrayStack {

        /**
         * 栈的大小
         */
        private int maxStack;

        /**
         * 用来模拟栈的数组
         */
        private int[] stack;

        /**
         * 表示栈顶所在的位置，没有数据时默认为-1
         */
        private int top = -1;

        /**
         * 构造器
         *
         * @param maxStack [in] 栈的最大容量
         */
        public ArrayStack(int maxStack) {
            this.maxStack = maxStack;
            stack = new int[maxStack];
        }

        /**
         * 判断栈是否已满
         */
        public boolean isFull() {
            return this.top == this.maxStack - 1;
        }

        /**
         * 判断是否为空栈
         */
        public boolean isEmpty() {
            return this.top == -1;
        }

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

        /**
         * 弹栈
         */
        public int pop() {
            //如果栈为空
            if (isEmpty()) {
                throw new RuntimeException("栈空，没有数据！");
            }
            int value = stack[top];
            top--;
            return value;
        }

        /**
         * 遍历栈，查看栈中所有元素
         * 从栈顶开始打印数据
         */
        public void list() {
            //是否是空栈
            if (isEmpty()) {
                throw new RuntimeException("空栈，未找到数据");
            }
            for (int i = maxStack - 1; i >= 0; i--) {
                System.out.printf("stack[%d]=%d\n", i, stack[i]);
            }

        }
    }

  2. 测试栈的功能

    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
    public class Test {
        public static void main(String[] args) {
            //先创建一个ArrayStack对象，用来表示表示栈
            ArrayStack stack = new ArrayStack(4);
            String key = "";
            //控制是否退出菜单
            boolean loop = true;
            Scanner scanner = new Scanner(System.in);

            while(loop) {
                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":
                        stack.list();
                        break;
                    case "push":
                        System.out.println("请输入一个数");
                        int value = scanner.nextInt();
                        stack.push(value);
                        break;
                    case "pop":
                        try {
                            int res = stack.pop();
                            System.out.printf("出栈的数据是 %d\n", res);
                        } catch (Exception e) {
                            // TODO: handle exception
                            System.out.println(e.getMessage());
                        }
                        break;
                    case "exit":
                        scanner.close();
                        loop = false;
                        break;
                    default:
                        break;
                }
            }
            System.out.println("程序退出~~~");
        }
    }

    运行结果

前缀、中缀、后缀表达式

  • 前缀表达式 (波兰表达式)

    前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前。

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

    例如：(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，由此得出最终结果。

  • 中缀表达式

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

    中缀表达式的求值是我们人最熟悉的，但是对计算机来说却不好操作。因此，在计算结果时，往往会将中缀表达式转成其它表达式来操作（一般转成后缀表达式）。

  • 后缀表达式

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

    例如： (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –

    正常的表达式 逆波兰表达式
    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 入栈；
    4. 接下来是 × 运算符，因此弹出 5 和 7，计算出 7×5=35 ，将 35 入栈；
    5. 将 6 入栈；
    6. 最后是 - 运算符，计算出 35-6 的值，即 29，由此得出最终结果。

栈的运用

1. 判断回文数据

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
public class TestApp {
    public static void main(String[] args) {

        /**
         * 回文数据
         * 回文：   aba   racecar
         * 需求：通过上面以数组模拟栈来判断一个字符串是否是一个回文数据
         */
        System.out.println( detection("hello"));

    }


    public static boolean detection(String val){
        /**
         * 初始化栈对象
         */
        ArrayStack arrayStack = new ArrayStack(10);

        /**
         * 获取字符串长度
         */
        int length = val.length();

        //把字符串数据逐次获取字符压栈至数组中
        for(int i=0;i<length;i++){
            arrayStack.push(val.charAt(i));

        }

        /**
         * 获取
         */
        String newVal = "";
        //每次pop后，length自动减少，必须提取出来
        int length1 = arrayStack.length();
        for (int i=0;i<length1;i++){
            //是否是一个空栈
            if (!arrayStack.isEmpty()){
                char pop = (char)arrayStack.pop();
                newVal=newVal+pop;
            }
        }

        if (val.equals(newVal)){
            return true;
        }

        return false;
    }

}

2. 栈实现综合计算器

image-20211120231817065

思路分析

思路分析

  1. 遍历字符串，获取每一个字符；

  2. 判断当前字符是一个运算符还是一个数字

    • 如果当前字符是一个数字，就直接放入数栈中；
    • 如果运算符栈是空栈，那么运算符直接进入符号栈；
    • 如果运算符栈中已经了其他运算符，就需要先对比运算符的优先级：
      • 如果该运算符小于等于栈中运算符，那么需要从数字栈中弹出两个数字，并符号栈中栈顶的符号出栈，进行运算，运算后的结果重新放入数字栈中，新运算符入栈；
      • 如果新运算符优先级大于原符号栈中运算符，那么新的符号直接入栈。

  3. 当表达式扫描完毕，就顺序的从数栈和符号栈中 pop 出相应的数和符号,进行运算。最后在数栈只有一个数字，就是表达式的结果

代码实现

  1. 用一个数组来模拟栈，并增加了以下方法：

    新增方法

    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
    public class ArrayStack {

        /**
         * 栈的大小
         */
        private int maxStack;

        /**
         * 数组用来模拟栈
         */
        private int[] stack;

        /**
         * 表示栈顶所在的位置，默认情况下如果没有数据时，使用-1
         */
        private int top = -1;

        /**
         * 构造器
         * @param maxStack [in] 栈的最大容量
         */
        public ArrayStack(int maxStack) {
            this.maxStack = maxStack;
            stack = new int[maxStack];
        }


        /**
         * 判断是否已经满栈
         */
        public boolean isFull() {
            return this.top == this.maxStack - 1;
        }

        /**
         * 判断栈是否是空栈
         */
        public boolean isEmpty() {
            return this.top == -1;
        }


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

        /**
         * 弹栈
         */
        public int pop() {
            //如果栈为空
            if (isEmpty()) {
                throw new RuntimeException("栈空，没有数据！");
            }
            int value = stack[top];
            top--;
            return value;
        }


        /**
         * 遍历栈，查看栈中所有元素
         * 从栈顶开始打印数据
         */
        public void list() {
            //是否是空栈
            if (isEmpty()) {
                throw new RuntimeException("空栈，未找到数据");
            }
            for (int i = maxStack - 1; i >= 0; i--) {
                System.out.printf("stack[%d]=%d\n", i, stack[i]);
            }

        }


        /**
         * 返回运算符的优先级
         * 优先级使用数字来表示：数字越大，优先级越高
         * @param oper [in] 用户输入的运算符
         * @return
         */
        public int priority(int oper){
            if (oper == '*' || oper == '/'){
                return 1;
            } else if (oper == '+' || oper == '1'){
                return 0;
            } else {
                return -1;
            }
        }

        /**
         * 判断是否为运算符
         * @param val [in] 用户输入的字符
         * @return
         */
        public boolean isOper(char val){
            return val == '+' || val == '-' || val == '*' || val == '/';
        }

        /**
         * 返回栈顶的元素，不是弹栈
         * @return
         */
        public int peek(){
            return stack[top];
        }

        /**
         * 计算表达式的结果
         * @param num1 [in] 接收的第一个数字
         * @param num2 [in] 接收的第二个数字
         * @param oper [in] 接收的符号
         * @param oper [out] 返回的计算结果
         * @return
         */
        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;
        }

    }

  2. 处理表达式并完成运算。

    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
    public class Calculator {
        public static void main(String[] args) {
            //用户输入的运算式
            String expression = "7*2*2-5+1-5+3-4";
            //数栈
            ArrayStack numStack = new ArrayStack(10);
            //符号栈
            ArrayStack operStack = new ArrayStack(10);
            //用于扫描时，定位当前所在表达式的位置
            int index = 0;
            int num1 = 0;
            int num2 = 0;
            int oper = 0;
            //用于存放运算结果
            int res = 0;
            //保存每次扫描表达式得到的符号
            char ch = ' ';
            //用于拼接 多位数
            String keepNum = "";

            //扫描表达式,逐个的处理表达式中的字符
            while(true) {
                //获取一个字符并存放在ch中
                ch = expression.substring(index, index+1).charAt(0);
                //如果是运算符
                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 {
                    //numStack.push(ch - 48);
                    //1. 当处理多位数时，不能发现是一个数就立即入栈，因为他可能是多位数
                    //2. 在处理数，需要向表达式当前的index后再看一位,如果是数就继续扫描，如果是符号才入栈
                    //3. 因此我们定义了变量 keepNum，用于拼接

                    //处理多位数
                    keepNum += ch;

                    //如果ch已经是表达式的最后一位了，就直接入栈
                    if (index == expression.length() - 1) {
                        numStack.push(Integer.parseInt(keepNum));
                    }else{

                        //判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈
                        //注意只是看index后面一位，不是index++
                        if (operStack.isOper(expression.substring(index+1,index+2).charAt(0))) {
                            //如果后一位是运算符，则入栈 ，如keepNum = "1" 或者 "123"
                            numStack.push(Integer.parseInt(keepNum));
                            //重要的!!!!!!, keepNum清空
                            keepNum = "";

                        }
                    }
                }
                //让index + 1，定位到下一个数
                index++;
                //判断是否扫描到表达式的最后，扫描结束
                if (index == expression.length()) {
                    break;
                }
            } //整个表达式扫描完毕，数字和符号已经全部作处理后入栈

            //顺序的从数栈和符号栈中弹出相应的数和符号并进行计算.
            while(true) {
                //如果符号栈为空，停止弹栈运算
                if(operStack.isEmpty()) {
                    break;
                }
                num1 = numStack.pop();
                num2 = numStack.pop();
                oper = operStack.pop();
                res = numStack.cal(num1, num2, oper);
                numStack.push(res);
            } //此时符号栈为空，数栈只有一个数字就是表达式的运算结果
            int res2 = numStack.pop();
            System.out.printf("表达式 %s = %d", expression, res2);
        }
    }

    运行结果

3. 逆波兰计算器

思路分析

1. 将中缀表达式转为后缀表达式

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

具体步骤如下**:**

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

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

  3. 遇到操作数时，将其压入 s2；

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

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

    • 如果 s1 不为空

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

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

  5. 遇到括号时：

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

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

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

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

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

扫描到的元素 s2(栈底->栈顶) s1 (栈底->栈顶) 说明
1 1 空 数字，直接入栈
+ 1 + s1 为空，运算符直接入栈
( 1 + ( 左括号，直接入栈
( 1 + ( ( 同上
2 1 2 + ( ( 数字
+ 1 2 + ( ( + s1 栈顶为左括号，运算符直接入栈
3 1 2 3 + ( ( + 数字
) 1 2 3 + + ( 右括号，弹出运算符直至遇到左括号
× 1 2 3 + + ( × s1 栈顶为左括号，运算符直接入栈
4 1 2 3 + 4 + ( × 数字
) 1 2 3 + 4 × + 右括号，弹出运算符直至遇到左括号
- 1 2 3 + 4 × + - - 与 + 优先级相同，因此弹出 +，再压入 -
5 1 2 3 + 4 × + 5 - 数字
到达最右端 1 2 3 + 4 × + 5 - 空 s1 中剩余的运算符
2. 对后缀表达式计算求值

  1. 依次将逆波兰表达式中的数据和运算符放入到 ArrayList 中；

  2. 将 ArrayList 传递给一个方法，遍历 ArrayList 配合栈，完成计算。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    public static List<String> getListString(String suffixExpression) {
            //将 suffixExpression 分割
            String[] split = suffixExpression.split(" ");
            List<String> list = new ArrayList<String>();
            for (String ele : split) {
                list.add(ele);
            }
            return list;
        }

代码实现

  1. 获取运算符优先级的类

    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
    public class Operation {
        private static int ADD = 1;
        private static int SUB = 1;
        private static int MUL = 2;
        private static int DIV = 2;

        /**
         * 返回插入的运算符的优先级数字
         * @param operation [in] 传入的运算符
         * @return
         */
        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:
                    //System.out.println("不存在该运算符" + operation);
                    break;
            }
            return result;
        }

    }

  2. 对表达式转化、求值的主体类

    类方法

    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
    public class RevPolishCalculator {


        /**
         * 主方法：测试代码是否能实现功能
         * @param args
         */
        public static void main(String[] args) {

            String expression = "1+((2+3)*4)-5";

            //将中缀表达式字符串入list
            List<String> infixExpressionList = toInfixExpressionList(expression);
            System.out.println("中缀表达式对应的List=" + infixExpressionList);

            //将【中缀表达式对应的List】转为【后缀表达式对应的List】
            List<String> parseSuffixExpressionList = parseSuffixExpressionList(infixExpressionList);
            System.out.println("后缀表达式对应的List=" + parseSuffixExpressionList);

            //对后缀表达式进行计算
            System.out.println(expression + calculate(parseSuffixExpressionList));


        }


        /**
         * 将中缀表达式转成对应的【List】
         *
         * @param s [in] 待转化的中缀表达式
         * @return
         */
        public static List<String> toInfixExpressionList(String s) {
            //定义一个List,存放中缀表达式 对应的内容
            List<String> ls = new ArrayList<String>();
            //用于遍历【中缀表达式】字符串的指针
            int i = 0;
            // 用于多位数的拼接
            String str;
            // 每遍历到一个字符就放入到c
            char c;
            do {
                //如果c是一个非数字，我需要加入到 ls
                if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
                    ls.add("" + c);
                    //指针后移
                    i++;
                } else {
                    //如果是一个数，判断是否是多位数
                    //先将 str 置成 ""
                    str = "";
                    // '0'是[48]-->'9'是[57]
                    while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
                        //拼接
                        str += c;
                        i++;
                    }
                    ls.add(str);
                }
            } while (i < s.length());
            //返回集合 ls
            return ls;
        }

        /**
         * 将【中缀表达式对应的List】转为【后缀表达式对应的List】
         *
         * @param ls [in] 中缀表达式对应的List
         * @return s2 [out] 后缀表达式对应的List
         */
        public static List<String> parseSuffixExpressionList(List<String> ls) {
            //定义符号栈
            Stack<String> s1 = new Stack<String>();
            //说明：因为s2 这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出

            //因为s2这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出
            //比较麻烦，这里我们就不用 Stack<String> 直接使用 List<String> s2
            //用于存储中间结果的List s2
            List<String> s2 = new ArrayList<String>();

            //遍历集合ls中的中缀表达式
            for (String item : ls) {
                //如果是一个数，加入s2
                if (item.matches("\\d+")) {
                    s2.add(item);
                } else if (item.equals("(")) {
                    s1.push(item);
                } else if (item.equals(")")) {
                    //遇到到右括号“)”，则依次弹出s1栈顶的运算符压入s2，直到遇到左括号为止
                    while (!s1.peek().equals("(")) {
                        s2.add(s1.pop());
                    }
                    //当s1栈顶是"("时, 将它弹出s1栈，将这一对小括号丢弃掉
                    s1.pop();
                } else {
                    //遍历到运算符，如果优先级小于等于s1栈顶运算符
                    while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
                        //将s1栈顶的运算符弹出并加入到s2中，并再次与新的栈顶运算符相比较
                        s2.add(s1.pop());
                    }
                    //优先级大于s1栈顶运算符时压入s1栈
                    s1.push(item);
                }
            }

            //将s1中剩余的运算符依次弹出并加入s2
            while (s1.size() != 0) {
                s2.add(s1.pop());
            }

            //因为是存放在List中,按顺序输出就是后缀表达式对应的List
            return s2;

        }

        /**
         * 对逆波兰表达式进行计算求值
         * 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，由此得出最终结果
         *
         * @param ls [in]
         * @return
         */
        public static int calculate(List<String> ls) {
            // 创建给栈, 只需要一个栈即可
            Stack<String> stack = new Stack<String>();
            // 遍历 ls
            for (String item : ls) {
                // 使用正则表达式取数,匹配到多位数
                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;
                    } else {
                        throw new RuntimeException("运算符有误");
                    }
                    //把res 入栈
                    stack.push("" + res);
                }

            }
            //最后留在stack中的数据就是运算结果
            return Integer.parseInt(stack.pop());
        }
    }

    运行结果