本文實例講述了java實現任意四則運算表達式求值算法。分享給大家供大家參考。具體分析如下：
該程序用于計算任意四則運算表達式。如 4 * ( 10 + 2 ) + 1 的結果應該為 49。
算法說明：
1. 首先定義運算符優先級。我們用一個
|
1
|
Map<String, Map<String, String>> |
來保存優先級表。這樣我們就可以通過下面的方式來計算兩個運算符的優先級了：
|
1
2
3
4
5
6
7
8
9
|
/** * 查表得到op1和op2的優先級 * @param op1 運算符1 * @param op2 運算符2 * @return ">", "<" 或 "=" */public String priority(String op1, String op2) { return priorityMap.get(op1).get(op2);} |
2. 掃描表達式字符串，每次讀入一個 token 進行處理。
使用兩個輔助棧：optStack用于保存運算符，numStack用于保存操作數. 我們用 '#' 作為表達式的起始和結果標志符。
讀入一個token，如果它是數字，則壓入numStack棧中；
如果它是運算符，則取出optStack棧的棧頂元素A，將 A 與 token 進行優先級比較。
如果 A < token，則將 token 壓入optStack棧。
如果 A = token，則說明 token和A是一對括號，此時將optStack棧的棧頂元素彈出。
如果 A > token，則從numStack中彈出２個操作數，從optStack中彈出1個運算符，并計算結果。
當optStrack棧為空時（即棧頂元素為 '#'），numStack棧的棧頂元素即為表達式的值。
算法實現：
|
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
|
/** * 算術表達式求值。 * 3 + 4 * 12 結果為51 * @author whf * */public class EvaluateExpression { // 運算符優先級關系表 private Map<String, Map<String, String>> priorityMap = new HashMap<String, Map<String, String>>(); private LinkedStack<String> optStack = new LinkedStack<String>(); // 運算符棧 private LinkedStack<Double> numStack = new LinkedStack<Double>(); // 操作數棧 /** * 計算表達式 * @param exp 四則運算表達式, 每個符號必須以空格分隔 * @return */ public double calcualte(String exp) { StringTokenizer st = new StringTokenizer(exp); while (st.hasMoreTokens()) { String token = st.nextToken(); process(token); } return numStack.pop(); } /** * 讀入一個符號串。 * 如果是數字，則壓入numStack * 如果是運算符，則將optStack棧頂元素與該運算符進行優先級比較 * 如果棧頂元素優先級低，則將運算符壓入optStack棧,如果相同，則彈出左括號，如果高，則取出２個數字，取出一個運算符執行計算，然后將結果壓入numStack棧中 * @param token */ private void process(String token) { while (false == "#".equals(optStack.getTop()) || false == token.equals("#")) { // token is numeric if (true == isNumber(token)) { numStack.push(Double.parseDouble(token)); break; // token is operator } else { String priority = priority(optStack.getTop(), token); if ("<".equals(priority)) { optStack.push(token); break; } else if ("=".equals(priority)) { optStack.pop(); break; } else { double res = calculate(optStack.pop(), numStack.pop(), numStack.pop()); numStack.push(res); } } } } /** * 執行四則運算 * @param opt * @param n1 * @param n2 * @return */ private double calculate(String opt, double n1, double n2) { if ("+".equals(opt)) { return n2 + n1; } else if ("-".equals(opt)) { return n2 - n1; } else if ("*".equals(opt)) { return n2 * n1; } else if ("/".equals(opt)) { return n2 / n1; } else { throw new RuntimeException("unsupported operator:" + opt); } } /** * 檢查一個String是否為數字 * @param token * @return */ private boolean isNumber(String token) { int LEN = token.length(); for (int ix = 0 ; ix < LEN ; ++ix) { char ch = token.charAt(ix); // 跳過小數點 if (ch == '.') { continue; } if (false == isNumber(ch)) { return false; } } return true; } /** * 檢查一個字符是否為數字 * @param ch * @return */ private boolean isNumber(char ch) { if (ch >= '0' && ch <= '9') { return true; } return false; } /** * 查表得到op1和op2的優先級 * @param op1 運算符1 * @param op2 運算符2 * @return ">", "<" 或 "=" */ public String priority(String op1, String op2) { return priorityMap.get(op1).get(op2); } /** * 構造方法，初始化優先級表 */ public EvaluateExpression() { // initialize stack optStack.push("#"); // initialize priority table // + Map<String, String> subMap = new HashMap<String, String>(); subMap.put("+", ">"); subMap.put("-", ">"); subMap.put("*", "<"); subMap.put("/", "<"); subMap.put("(", "<"); subMap.put(")", ">"); subMap.put("#", ">"); priorityMap.put("+", subMap); // - subMap = new HashMap<String, String>(); subMap.put("+", ">"); subMap.put("-", ">"); subMap.put("*", "<"); subMap.put("/", "<"); subMap.put("(", "<"); subMap.put(")", ">"); subMap.put("#", ">"); priorityMap.put("-", subMap); // * subMap = new HashMap<String, String>(); subMap.put("+", ">"); subMap.put("-", ">"); subMap.put("*", ">"); subMap.put("/", ">"); subMap.put("(", "<"); subMap.put(")", ">"); subMap.put("#", ">"); priorityMap.put("*", subMap); // / subMap = new HashMap<String, String>(); subMap.put("+", ">"); subMap.put("-", ">"); subMap.put("*", ">"); subMap.put("/", ">"); subMap.put("(", "<"); subMap.put(")", ">"); subMap.put("#", ">"); priorityMap.put("/", subMap); // ( subMap = new HashMap<String, String>(); subMap.put("+", "<"); subMap.put("-", "<"); subMap.put("*", "<"); subMap.put("/", "<"); subMap.put("(", "<"); subMap.put(")", "="); //subMap.put("#", ">"); priorityMap.put("(", subMap); // ) subMap = new HashMap<String, String>(); subMap.put("+", ">"); subMap.put("-", ">"); subMap.put("*", ">"); subMap.put("/", ">"); //subMap.put("(", "<"); subMap.put(")", ">"); subMap.put("#", ">"); priorityMap.put(")", subMap); // # subMap = new HashMap<String, String>(); subMap.put("+", "<"); subMap.put("-", "<"); subMap.put("*", "<"); subMap.put("/", "<"); subMap.put("(", "<"); //subMap.put(")", ">"); subMap.put("#", "="); priorityMap.put("#", subMap); }} |
程序測試：
|
1
2
3
|
String exp = "4 * ( 10 + 2 ) + 1 #";EvaluateExpression ee = new EvaluateExpression();out.println(ee.calcualte(exp)); |
運行結果為 49。
希望本文所述對大家的C++程序設計有所幫助。
