栈——通过中缀转后缀在进行逆波兰计算式构建计算器
只能在运算式中出现数字（）+ - * / .

代码

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

        //完成中缀表达式转后缀表达式
        //1. 1+（(2+3）*4）-5=>转成1 2 3 + 4 × + 5 -
        //2.因为直接对字符串操作不方便，所以我们先将1+（(2+3）*4）-5转成中缀的list
        //  即1+（(2+3）*4）-5转为【1，+，（，（，2，+，3，），*，4，），-，5】
        //3.将得到的中缀表达式对应的List=>后缀对应的List
        //即ArrayList【1，+，（，（，2，+，3，），*，4，），-，5】=>[]
        String expression = "1+((22.222+3)*4.05)-5";
        List<String> list = toInfixList ( expression );
        System.out.println ("中缀表达式List="+ list );
        List<String> suffixlist    = turnSuffixExpression ( list );
        System.out.println ( "后缀表达式List="+ suffixlist );
        float res=calculate ( suffixlist );
        System.out.printf ( "%s=%f" ,expression, res );

    }

    //讲中缀表达式转化为List
    public static List<String> toInfixList ( String s ) {
        //先定义一个list,存放中缀表达式对应的内容
        List<String> ls=new ArrayList<String> (  ) ;
        int i = 0;//这是一个指针用于遍历中缀表达式字符串
        String str;//多位数拼接
        char c;//每遍历到一个字符就放入到c中
        do {
            //如果c是一个非数字，需要加到ls
            if ( (c=s.charAt ( i ))<48 ||(c=s.charAt ( i ))>57&&(c=s.charAt ( i ))!='.' ){  //ASCII表48-57是数字
                ls.add ( "" + c );
                i++;
            }else{
                str = "";//先将str置空
                while ((i<s.length ()&&((c=s.charAt ( i ))>=48&&(c=s.charAt ( i ))<=57||(c=s.charAt ( i ))=='.')) ){
                    str += c;//拼接
                    i++;
                }
                ls.add ( str );

            }

        } while (i < s.length ( ));

        return ls;
    }

    //将得到的中缀表达式对应的List=>后缀对应的List
    public static List<String> turnSuffixExpression ( List<String> ls ) {
        //定义两个栈
        Stack<String> s1 = new Stack<String> ( );
        //s2栈在整个过程没有弹出操作，又因为最后要逆序输出，所以使用ArrayList
        List<String> s2 = new ArrayList<String> ( );//用于存储中间结果

        //遍历ls
        for ( String i:ls ){
            //如果是一个数，加入s2
            if ( i.matches ( "\\d+" )|| i.matches ( "\\d+.\\d+" )) {
                s2.add ( i );
            }
            else if ( i.equals ( "(")) {
                s1.push ( i );
            }
            else if (i.equals ( ")" )){
                //如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
                while (!s1.peek ( ).equals ( "(" )) {  //s1.peek()查看栈顶内容，但不弹出;如果栈顶没有到达（就不停止，继续弹
                    s2.add ( s1.pop ( ) );
                }
                s1.pop ();//将（弹出s1,消除小括号
            }else {
                //若i优先级<=栈顶运算符将s1栈顶的运算符弹出并加入到s2中，再次转到（4.1）与s1中新的栈顶运算符相比较；
                //缺少比较一个运算符优先级高低的方法
                while (s1.size ()!=0&& Operation.getValue ( s1.peek () )>=Operation.getValue (  i)){
                    s2.add ( s1.pop ( ) );
                }
                //// 比栈顶运算符的高，也将运算符压入s1；
                s1.push ( i );

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

        //因为是存放到list中，正常输出即为后缀表达式
        return s2;
    }


    //将一个逆波兰表达式，依次将数据和运算符放入到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 float calculate ( List<String> ls) {
        //创建一个栈
        Stack<String> stack = new Stack<> ( );
        //遍历ls
        for ( String s : ls ) {
            //这里使用正则表达式来取多位数
            if ( s.matches ("\\d+"  )||s.matches ( "\\d+.\\d+" ) ){//匹配多位数  s.matches来匹配数字“\\d+"(+)表示一到多
                //入栈
                stack.push ( s );
            }else {
                //栈中弹出两个数，并运算，计算结果在入栈
                float num2=Double.valueOf ( stack.pop ( )).floatValue (); //把整数或者小数的字符串转为float类型
                float num1=Double.valueOf ( stack.pop ( )).floatValue ();
                double 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 Double.valueOf ( stack.pop ( ) ).floatValue ();
    }


}

//编写一个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:
                System.out.println ("运算符有误" );
        }
        return result;
    }
}

结果

image-20230126150326481