表达式求值

实现思路

• 准备一个索引index来帮助我们遍历表达式
• 如果index位置上的元素是一个数字，就直接入栈
• 如果index位置上的元素是一个符号
  • 如果符号栈为空，直接入栈
  • 如果符号栈不为空
    • index位置上的符号的优先级小于或等于栈顶符号的优先级，则弹出两个数栈中的元素和符号栈中的一个符号，并且进行计算。将运算结果放入数栈中，并将index位置上的符号压入符号栈
    • index位置上的符号的优先级大于符号栈栈顶符号的优先级，则将该符号压入符号栈
• 当表达式遍历完毕后，就弹出数栈中的2个数字和符号栈中的1个符号进行运算，并将运行结果入栈
• 最终数栈中只有一个值，这个值便是运算结果
• 注意：
  • 读取的是字符，所以存入数字前需要减去0的ASCII码
  • 如果数字是多位数，需要一直读，读到下一位不是数字为止，然后将读到的字符进行拼接，然后一起压入数栈

---

思路流程图

1、假设表达式是express

数字入栈发现入栈的是12字符串，因为12是一个数字，我们不能把他分开所以就必须将连续的数字拼接一起。

2、拼接数字字符串，比对符号栈优先级

当减号之前和会进行一个比对，当入栈的符号栈小于栈顶的优先级时，符号栈栈顶的运算符会和数字栈顶的两个元素进行运算，将运算结果放入数字栈顶。

3、计算栈顶元素的优先级

大家学过数学的都知道*（乘法的优先级大于加法）所以应该先算3*3

计算得到：

4、最终得到

5、计算最终结果

---

实现代码

package com.cloud;

import java.util.EmptyStackException;

public class Demo2 {
    public static void main(String[] args) {
        String exps = "12+8*9-9/3";
        //索引，用来读取字符串中的元素
        int index = 0;
        //保存读取到的数字和符号
        int number1 = 0;
        int number2 = 0;
        int thiChar = ' ';
        // 拼接字符串
        StringBuilder sb = new StringBuilder();
        // 数字栈
        ArrayStack numberStack = new ArrayStack(10);
        // 符号栈
        ArrayStack operationStack = new ArrayStack(10);
        // 保存计算结果
        int result;

        for (index = 0; index < exps.length(); index++) {
            thiChar = exps.charAt(index);
            // 判断字符是不是运算符
            if (operationStack.isOperation(thiChar)){
                // Todo 比较运算符之间的优先级
                if (operationStack.comparePriority(thiChar)){
                    // 入栈的运算符大于栈顶的，直接入栈
                    operationStack.push(thiChar);
                }else{
                    // 入栈的运算符小于栈顶的，将数字栈顶的两个元素进行入栈运算符计算
                    // 栈顶运算符
                    int popChar = operationStack.pop();
                    // 取出数字栈顶的两个元素
                    number2 = numberStack.pop();
                    number1 = numberStack.pop();
                    // 计算结果
                    result = operationStack.calculation(number1, number2, popChar);
                    // 将入栈的运算符入符号栈
                    operationStack.push(thiChar);
                    // 将计算的结果放入数字栈顶
                    numberStack.push(result);
                }
                // 数字直接添加到数字栈中
            }else{
                while (thiChar >= '0' && thiChar <= '9'){
                    // 数字有可能会是多为，12
                    sb.append(thiChar - '0');
                    System.out.println("拼接字符串"+sb);
                    index++;
                    // 到了最后一位结束
                    if (index >= exps.length()){
                        break;
                    }
                    thiChar = exps.charAt(index);
                }
                int num = Integer.parseInt(sb.toString());
                numberStack.push(num);
                // 初始化sb
                sb = new StringBuilder();
                index--;
            }
        }
        // 运算
        while (!operationStack.isEmpty()){
            int popChar = operationStack.pop();
            number2 = numberStack.pop();
            number1 = numberStack.pop();
            result = operationStack.calculation(number1,number2,popChar);
            numberStack.push(result);
        }
        System.out.println(numberStack.pop());

    }
}


class ArrayStack {
    // 栈大小
    private final int maxSize;
    // 栈数组
    int[] stack;
    // 栈顶指针，默认为-1，添加元素top++
    private int top;

    /**
     * 初始化栈
     */
    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
        top = -1;
    }

    /**
     * 判断是否为空,top=-1,说明栈中没有元素
     *
     * @return top == -1
     */
    public boolean isEmpty() {
        return top == -1;
    }

    /**
     * 判断栈是否满了，
     *
     * @return
     */
    public boolean isFull() {
        return top == maxSize - 1;
    }

    /**
     * 添加元素
     *
     * @param i
     */
    public void push(int i) {
        if (isFull()) {
            System.out.println("栈满了，请不要再进来了");
            return;
        }
        top++;
        stack[top] = i;
    }

    /**
     * 从栈顶取出一个元素
     *
     * @return
     */
    public int pop() {
        if (isEmpty()) {
            System.out.println("栈是空的，请不要在进来取了");
            throw new EmptyStackException();
        }
        int retNum = stack[top];
        top--;
        return retNum;
    }

    /**
     * 遍历栈
     */
    public void traverse() {
        for (int thiChar : stack) {
            System.out.println(thiChar);
        }
    }

    /**
     * 判断符号优先级
     *
     * @param operation
     * @return
     */
    public int getPriority(int operation) {
        if (operation == '*' || operation == '/') {
            return 2;
        } else if (operation == '+' || operation == '-') {
            return 1;
        } else if (operation >= '0' && operation <= '9') {
            return 0;
        } else {
            return -1;
        }
    }

    /**
     * 比较符号栈和入栈符号元素的优先级
     *
     * @param operation
     * @return
     */
    public boolean comparePriority(int operation) {
        if (isEmpty()) {
            return true;
        } else {
            int priority1 = getPriority(operation);
            int priority2 = getPriority(stack[top]);
            return priority1 > priority2;
        }
    }

    /**
     * 判断输入的是否是一个运算符号
     *
     * @param operation
     * @return
     */
    public boolean isOperation(int operation) {
        return operation == '*' || operation == '/' || operation == '-' || operation == '+';
    }

    /**
     * 计算
     *
     * @param number1
     * @param number2
     * @param operation
     * @return
     */
    public int calculation(int number1, int number2, int operation) {
        switch (operation) {
            case '+':
                return number1 + number2;
            case '-':
                return number1 - number2;
            case '*':
                return number1 * number2;
            case '/':
                return number1 / number2;
            default:
                System.out.println(operation);
                throw new RuntimeException("符号读取错误！");
        }
    }

}
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
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220

---