java学习之—使用栈实现字符串数字四则运算

1/**
2 * 使用栈存储后缀表达式
3 * Create by Administrator
4 * 2018/6/13 0013
5 * 下午 2:25
6 **/
7public class StackX {
8
9    private int maxSize;
10    private char[] stackArray;
11    private int top;
12
13    public StackX(int size)      // 构造函数
14    {
15        maxSize = size;
16        stackArray = new char[maxSize];
17        top = -1;
18    }
19
20    public void push(char j)     // 将项目放在堆栈的顶部
21    {
22        stackArray[++top] = j;
23    }
24
25    public char pop()            // 从堆栈顶部取项
26    {
27        return stackArray[top--];
28    }
29
30    public char peek()           // 从堆栈顶部查看
31    {
32        return stackArray[top];
33    }
34
35    public boolean isEmpty()    // 如果栈为空，则为true
36    {
37        return (top == -1);
38    }
39
40    public boolean isFull()     // 如果堆栈已满 true
41    {
42        return (top == maxSize - 1);
43    }
44
45    public int size()           // return size
46    {
47        return top + 1;
48    }
49
50    public char peekN(int n)     // peek at index n
51    {
52        return stackArray[n];
53    }
54
55    public void displayStack(String s) {
56        System.out.print(s);
57        System.out.print("Stack (bottom-->top): ");
58        for (int j = 0; j < size(); j++) {
59            System.out.print(peekN(j));
60            System.out.print(' ');
61        }
62        System.out.println("");
63    }
64
65}
66
67/**
68 * 使用栈存储计算过程结果
69 * Create by Administrator
70 * 2018/6/14 0014
71 * 上午 10:37
72 **/
73public class StackR {
74    private int maxSize;
75    private int[] stackArray;
76    private int top;
77
78    public StackR(int size)      // 构造函数
79    {
80        maxSize = size;
81        stackArray = new int[maxSize];
82        top = -1;
83    }
84
85    public void push(int j)     // 将项目放在堆栈的顶部
86    {
87        stackArray[++top] = j;
88    }
89
90    public int pop()            // 从堆栈顶部取项
91    {
92        return stackArray[top--];
93    }
94
95    public int peek()           // 从堆栈顶部查看
96    {
97        return stackArray[top];
98    }
99
100    public boolean isEmpty()    // 如果栈为空，则为true
101    {
102        return (top == -1);
103    }
104
105    public boolean isFull()     // 如果堆栈已满 true
106    {
107        return (top == maxSize - 1);
108    }
109
110    public int size()           // return size
111    {
112        return top + 1;
113    }
114
115    public int peekN(int n)     // peek at index n
116    {
117        return stackArray[n];
118    }
119
120    public void displayStack(String s) {
121        System.out.print(s);
122        System.out.print("Stack (bottom-->top): ");
123        for (int j = 0; j < size(); j++) {
124            System.out.print(peekN(j));
125            System.out.print(' ');
126        }
127        System.out.println("");
128    }
129}
130
131import java.io.BufferedReader;
132import java.io.IOException;
133import java.io.InputStreamReader;
134
135/**
136 * Create by Administrator
137 * 2018/6/13 0013
138 * 下午 2:38
139 **/
140public class InTOPost {
141
142    private StackX stackX;
143    private StackR stackR;
144    private String input;
145    private String outPut = "";
146
147    public InTOPost(String in) {
148        this.input = in;
149        int stackSize = input.length();
150        stackX = new StackX(stackSize);
151
152    }
153
154    /**
155     * 中缀表达式转后缀表达式
156     * @return
157     */
158    public String doTrans() {
159        for (int i = 0; i < input.length(); i++) {
160            char ch = input.charAt(i);//拿到每个字符
161            stackX.displayStack("For " + ch + " ");
162            switch (ch) {
163                case '+':
164                case '-':
165                    getOpera(ch, 1);
166                    break;
167                case '*':
168                case '/':
169                    getOpera(ch, 2);
170                    break;
171                case ')':
172                    getParen(ch);
173                    break;
174                case '(':
175                    stackX.push(ch);
176                    break;
177                default:
178                    outPut = outPut + ch;           //是数字将其写入输出
179                    break;
180            }
181        }
182        while (!stackX.isEmpty()) {
183            stackX.displayStack("While ");
184            outPut = outPut + stackX.pop();
185        }
186        stackX.displayStack("End ");
187        return outPut;
188    }
189
190    private void getOpera(char opThis, int prec1) {
191        while (!stackX.isEmpty()) {
192            char opTop = stackX.pop();
193            if (opTop == '(') {
194                stackX.push(opTop);
195                break;
196            } else {
197                int prec2;
198                if (opTop == '+' || opTop == '-') {
199                    prec2 = 1;
200                } else {
201                    prec2 = 2;
202                }
203                if (prec2 < prec1) {
204                    stackX.push(opTop);
205                    break;
206                } else {
207                    outPut = outPut + opTop;
208                }
209            }
210        }
211        stackX.push(opThis);
212    }
213
214    private void getParen(char ch) {
215        while (!stackX.isEmpty()) {
216            char chx = stackX.pop();
217            if (chx == '(') {
218                break;
219            } else {
220                outPut = outPut + chx;
221            }
222        }
223    }
224
225    /**
226     * 计算后缀表达式的结果
227     * @param output
228     * @return
229     */
230    public int doParse(String output) {
231        stackR = new StackR(20);            //新建堆栈
232        char ch;
233        int num1, num2, interAns;
234        for (int i = 0; i < output.length(); i++) { //遍历后缀表达式的字符串
235            ch = output.charAt(i);               // 读取到每一个字符
236            stackR.displayStack(ch + " ");
237            if (ch >= '0' && ch <= '9') {        // 判断是不是数字
238                stackR.push((int) (ch - '0'));   // 放入到栈里
239            } else {
240                num2 = stackR.pop();             // 如果不是数字，就从栈里取出两个数字
241                num1 = stackR.pop();
242                switch (ch) {                   // 判断是哪个运算符，并计算
243                    case '+':
244                        interAns = num1 + num2;
245                        break;
246                    case '-':
247                        interAns = num1 - num2;
248                        break;
249                    case '*':
250                        interAns = num1 * num2;
251                        break;
252                    case '/':
253                        interAns = num1 / num2;
254                        break;
255                    default:
256                        interAns = 0;
257                }
258                stackR.push(interAns);      // 把计算结果放入栈里
259            }
260        }
261        interAns = stackR.pop();           // 获得最终结果
262        return interAns;
263    }
264
265    /**
266     * 获取用户输入
267     * @return
268     * @throws IOException
269     */
270    public static String getString() throws IOException {
271        InputStreamReader isr = new InputStreamReader(System.in);
272        BufferedReader br = new BufferedReader(isr);
273        String s = br.readLine();
274        return s;
275    }
276
277    public static void main(String[] args) throws IOException {
278        String input, output;
279        while (true) {
280            System.out.print("Enter infix: ");
281            System.out.flush();
282            input = getString();
283            if (input.equals("")) {
284                break;
285            }
286            InTOPost toPost = new InTOPost(input);
287            output = toPost.doTrans();
288            System.out.println("Postfix is " + output + "\n");
289            int result = toPost.doParse(output);
290            System.out.println("结果：" + result);
291        }
292    }

　　运行测试：

请输入:  (4+2*3)/2

For ( Stack (bottom-->top):
For 4 Stack (bottom-->top): (
For + Stack (bottom-->top): (
For 2 Stack (bottom-->top): ( +
For * Stack (bottom-->top): ( +
For 3 Stack (bottom-->top): ( + *
For ) Stack (bottom-->top): ( + *
For / Stack (bottom-->top):
For 2 Stack (bottom-->top): /
While Stack (bottom-->top): /
End Stack (bottom-->top):
Postfix is 423*+2/

4 Stack (bottom-->top):
2 Stack (bottom-->top): 4
3 Stack (bottom-->top): 4 2
* Stack (bottom-->top): 4 2 3
+ Stack (bottom-->top): 4 6
2 Stack (bottom-->top): 10
/ Stack (bottom-->top): 10 2
结果：5