栈——通过逆波兰计算式构建计算器

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

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

思路分析

已知后缀进行计算

​ (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
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
public class PolandNotation {
    public static void main ( String[] args ) {
        //先定义一个逆波兰表达式
        //(3+4)*5-6 => 3 4 + 5 * 6 -
        //4*5-8+60+8/2=4 5 * 8 - 60 + 8 2 / +
        String suffixExpression = "4 5 * 8 - 60 + 8 2 / +";
        //思路
        //1.先将“3 4 + 5 * 6 -”=> 放入ArrayList
        //2. 将ArrayList 传递给一个方法，遍历ArrayList 配合栈完成计算

        List<String> reList = getListStrings ( suffixExpression );
        System.out.println ("reList="+reList );
        int res=calculate ( reList );
        System.out.println ("运算结果为: "+res );
    }

    //将一个逆波兰表达式，依次将数据和运算符放入到ArrayList中
    public static List<String> getListStrings ( String suffixEpression ) {
        //将suffixEpression分割
        String[] spilt=suffixEpression.split ( " " );  //以空格来分割
        List<String> list = new ArrayList<String> ( );
        for ( String element : spilt ) {  //将分割后的数依次循环
            list.add( element );

        }
        return list;
    }

    //完成对逆波兰表达式的运算

    /**
     * 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，由此得出最终结果（下一个-顶部）
     */
    public static int calculate ( List<String> ls) {
        //创建一个栈
        Stack<String> stack = new Stack<> ( );
        //遍历ls
        for ( String s : ls ) {
            //这里使用正则表达式来取多位数
            if ( s.matches ("\\d+"  ) ){//匹配多位数  s.matches来匹配数字“\\d+"(+)表示一到多
                //入栈
                stack.push ( s );
            }else {
                //栈中弹出两个数，并运算，计算结果在入栈
                int num2 = Integer.parseInt (stack.pop ( ));
                int num1 = Integer.parseInt (stack.pop ( ));
                int res=0;
                if ( s.equals ( "+" ) ) {
                    res = num1 + num2;
                }
                else if ( s.equals ( "-" ) ) {
                    res = num1 - num2;
                }
                else if ( s.equals ( "*" ) ) {
                    res = num1 * num2;
                }
                else if ( s.equals ( "/" ) ) {
                    res = num1 / num2;
                }else {
                    throw new RuntimeException ( "运算符完毕" );
                }
                stack.push (  ""+res );
            }
        }
        //最后留在stack中的数据为运算结果
        return Integer.parseInt (stack.pop ( ));
    }
}

结果：

这里有张图片：
image-20230119232552897