對四則運算表達式字符串進行解析后計算出結果，可以使用逆波蘭表達式進行處理。
首先說明一下什是逆波蘭表達式：
逆波蘭表達式又叫做后綴表達式。在通常的表達式中，二元運算符總是置于與之相關的兩個運算對象之間，所以，這種表示法也稱為中綴表示。波蘭邏輯學家J.Lukasiewicz于1929年提出了另一種表示表達式的方法。按此方法，每一運算符都置于其運算對象之后，故稱為后綴表示。
將一個普通的中序表達式轉換為逆波蘭表達式的一般算法是：
(1)首先構造一個運算符棧，此運算符在棧內遵循越往棧頂優先級越高的原則。
(2)讀入一個用中綴表示的簡單算術表達式，為方便起見,設該簡單算術表達式的右端多加上了優先級最低的特殊符號“#”。
(3)從左至右掃描該算術表達式，從第一個字符開始判斷，如果該字符是數字，則分析到該數字串的結束并將該數字串直接輸出。
(4)如果不是數字，該字符則是運算符，此時需比較優先關系。
做法如下：將該字符與運算符棧頂的運算符的優先關系相比較。如果，該字符優先關系高于此運算符棧頂的運算符，則將該運算符入棧。倘若不是的話，則將棧頂的運算符從棧中彈出，直到棧頂運算符的優先級低于當前運算符，將該字符入棧。
(5)重復上述操作(3)-(4)直至掃描完整個簡單算術表達式，確定所有字符都得到正確處理，我們便可以將中綴式表示的簡單算術表達式轉化為逆波蘭表示的簡單算術表達式。
以上內容來源百度
下面進入正題，按照以上的算法說明自己實現四則運算如下：
1 package com.snoics.jdk.arithmetic;
2
3 import java.math.BigDecimal;
4 import java.math.RoundingMode;
5 import java.util.ArrayList;
6 import java.util.LinkedList;
7 import java.util.List;
8
9 /**
10 *
11 * 通過四則運算表達式字符串，構造逆波蘭表達式，計算結果
12 *
13 * (1)從左至右掃描該算術表達式，從第一個字符開始判斷，
14 * 如果該字符是數字，則分析到該數字串的結束并將該數字串直接輸出。
15 *
16 * (2)如果不是數字，該字符則是運算符，此時需比較優先關系。
17 做法如下：將該字符與運算符棧頂的運算符的優先關系相比較。
18 如果，該字符優先關系高于此運算符棧頂的運算符，則將該運算符入棧。
19 倘若不是的話，則將棧頂的運算符從棧中彈出，直到棧頂運算符的優先級
20 低于當前運算符，將該字符入棧。
21
22 (3)重復上述操作(1)-(2)直至掃描完整個簡單算術表達式，確定所有字符都得到正確處理，
23 我們便可以將中綴式表示的簡單算術表達式轉化為逆波蘭表示的簡單算術表達式。
24 *
25 * @author:shiwei
26 *
27 *
28 */
29 public class Arithmetic {
30
31 /**
32 * +
33 */
34 private final static String OP1 = "+";
35
36 /**
37 * -
38 */
39 private final static String OP2 = "-";
40
41 /**
42 * *
43 */
44 private final static String OP3 = "*";
45
46 /**
47 * /
48 */
49 private final static String OP4 = "/";
50
51 /**
52 * (
53 */
54 private final static String OPSTART = "(";
55
56 /**
57 * )
58 */
59 private final static String OPEND = ")";
60
61 //四則運算式
62 private String exp;
63
64 //精確到小數點后幾位
65 private int precision=2;
66
67 //取舍模式
68 private RoundingMode roundingMode=RoundingMode.HALF_UP;
69
70 //四則運算解析
71 private List<String> expList = new ArrayList<String>();
72
73 //存放逆波蘭表達式
74 private List<String> rpnList = new ArrayList<String>();
75
76 /**
77 * 四則運算
78 * @param exp 四則運算表達式
79 * @param precision 精確到小數點后幾位
80 * @param roundingMode 取舍模式
81 */
82 public Arithmetic(String exp,int precision,RoundingMode roundingMode) {
83 this.exp = exp;
84 this.precision=precision;
85 this.roundingMode=roundingMode;
86
87 parse();
88 createRPN();
89 }
90
91 /**
92 * 分析四則運算表達式，將數字與運算符進行分解
93 */
94 private void parse() {
95 int length = exp.length();
96
97 String tempStr = "";
98 for (int i = 0; i < length; i++) {
99 String tempChar = exp.substring(i, i + 1);
100 if (isNumber(tempChar)) {
101 tempStr += tempChar;
102 } else {
103 if (!tempStr.equals("")) {
104 expList.add(tempStr);
105 }
106 expList.add(tempChar);
107 tempStr = "";
108 }
109 }
110 if (!tempStr.equals("")) {
111 expList.add(tempStr);
112 }
113
114 }
115
116 /**
117 * 判斷當前字符或字符串是否是數字
118 * @param str
119 * @return
120 */
121 private boolean isNumber(String str) {
122 return str.startsWith("0")
123 || str.startsWith("1")
124 || str.startsWith("2")
125 || str.startsWith("3")
126 || str.startsWith("4")
127 || str.startsWith("5")
128 || str.startsWith("6")
129 || str.startsWith("7")
130 || str.startsWith("8")
131 || str.startsWith("9")
132 || str.startsWith(".");
133
134 }
135
136 /**
137 * 判斷當前字符是否是 (
138 * @param str
139 * @return
140 */
141 private boolean isParenthesesStart(String str) {
142 return str.equals(OPSTART);
143 }
144
145 /**
146 * 判斷當前字符是否是 )
147 * @param str
148 * @return
149 */
150 private boolean isParenthesesEnd(String str) {
151 return str.equals(OPEND);
152 }
153
154 /**
155 * 判斷當前字符是否是高優先級運算符 * /
156 * @param str
157 * @return
158 */
159 private boolean isHeighOperator(String str) {
160 if (str.equals(OP3)
161 || str.equals(OP4)) {
162 return true;
163 } else {
164 return false;
165 }
166 }
167
168 /**
169 * 對比兩個字符串的優先級
170 * @param str1
171 * @param str2
172 * @return
173 */
174 private boolean compare(String str1, String str2) {
175 if (str1.equals(OPSTART)) {
176 return false;
177 }
178 if (isHeighOperator(str2)) {
179 return false;
180 } else {
181 if (isHeighOperator(str1)) {
182 return true;
183 } else {
184 return false;
185 }
186 }
187 }
188
189 /**
190 * 將分解后的四則運算列表構建成逆波蘭表達式列表
191 */
192 private void createRPN() {
193 Stack stack = new Stack();
194
195 int length = expList.size();
196 for (int i = 0; i < length; i++) {
197 String c = expList.get(i);
198
199 //如果是數字，直接放到逆波蘭鏈表的最后
200 if (isNumber(c)) {
201 rpnList.add(c);
202 } else {
203 //如果不是數字
204
205 //如果是左括號，則直接將左括號壓入棧
206 if (isParenthesesStart(c)) {
207 stack.push(c);
208 } else if (isParenthesesEnd(c)) {
209 //如果是右括號
210
211 //進行出棧操作，直到棧為空或者遇到第一個左括號
212 while (!stack.isEmpty()) {
213 //將棧頂字符串做出棧操作
214 String tempC = stack.pop();
215 if (!tempC.equals(OPSTART)) {
216 //如果不是左括號，則將字符串直接放到逆波蘭鏈表的最后
217 rpnList.add(tempC);
218 }else{
219 //如果是左括號，退出循環操作
220 break;
221 }
222 }
223 } else {
224 //如果棧內為空
225 if (stack.isEmpty()) {
226 //將當前字符串直接壓棧
227 stack.push(c);
228 } else {
229 //如果棧不為空
230
231 //比較棧頂字符串與當前字符串的優先級，
232 if (compare(stack.top(), c)) {
233 //如果棧頂元素的優先級大于當前字符串,則進行出棧操作
234 //將棧頂元素直接放到逆波蘭鏈表的最后
235 //直到棧內為空，或者當前元素的優先級不小于棧頂元素優先級
236 while (!stack.isEmpty() && compare(stack.top(), c)) {
237 rpnList.add(stack.pop());
238 }
239 }
240 //將當前字符串直接壓棧
241 stack.push(c);
242 }
243 }
244
245 }
246 }
247
248 //如果棧不為空，則將棧中所有元素出棧放到逆波蘭鏈表的最后
249 while (!stack.isEmpty()) {
250 rpnList.add(stack.pop());
251 }
252 }
253
254 /**
255 * 通過逆波蘭表達式計算結果
256 * @return
257 */
258 public String calculate(){
259 Stack numberStack = new Stack();
260
261 int length=rpnList.size();
262 for(int i=0;i<length;i++){
263 String temp=rpnList.get(i);
264 if(isNumber(temp)){
265 numberStack.push(temp);
266 }else{
267 BigDecimal tempNumber1 = getBigDecimal(numberStack.pop(),
268 precision,
269 roundingMode);
270
271 BigDecimal tempNumber2 = getBigDecimal(numberStack.pop(),
272 precision,
273 roundingMode);
274
275 BigDecimal tempNumber = getBigDecimal("",
276 precision,
277 roundingMode);
278
279 if(temp.equals(OP1)){
280 tempNumber=tempNumber2.add(tempNumber1);
281 }else if(temp.equals(OP2)){
282 tempNumber=tempNumber2.subtract(tempNumber1);
283 }else if(temp.equals(OP3)){
284 tempNumber=tempNumber2.multiply(tempNumber1);
285 }else if(temp.equals(OP4)){
286 tempNumber=tempNumber2.divide(tempNumber1,
287 precision,
288 roundingMode);
289 }
290
291 numberStack.push(tempNumber.toString());
292
293 }
294 }
295
296 return numberStack.pop();
297 }
298
299 /**
300 * 獲取逆波蘭表達式字符串
301 * @return
302 */
303 public String getRPN(){
304
305 String rpn="";
306
307 int rpnLength=rpnList.size();
308 for(int i=0;i<rpnLength;i++){
309 rpn+=rpnList.get(i)+" ";
310 }
311
312 return rpn;
313 }
314
315 /**
316 * 按精確度計算結果
317 * @param numString
318 * @param precision
319 * @param roundingMode
320 * @return
321 */
322 public static BigDecimal getBigDecimal(String numString,
323 int precision,
324 RoundingMode roundingMode){
325 String precisionFlag="0";
326 if(numString==null || numString.equals("")){
327 precisionFlag="0.00";
328 }else{
329 precisionFlag=numString;
330 }
331 BigDecimal bigDecimal = new BigDecimal(precisionFlag);
332 bigDecimal.setScale(precision,roundingMode);
333 return bigDecimal;
334 }
335
336 /**
337 * 棧
338 *
339 *
340 * @author shiwei
341 *
342 */
343 private class Stack {
344
345 LinkedList<String> stackList = new LinkedList<String>();
346
347 public Stack() {
348
349 }
350
351 /**
352 * 入棧
353 * @param expression
354 */
355 public void push(String expression) {
356 stackList.addLast(expression);
357 }
358
359 /**
360 * 出棧
361 * @return
362 */
363 public String pop() {
364 return stackList.removeLast();
365 }
366
367 /**
368 * 棧頂元素
369 * @return
370 */
371 public String top() {
372 return stackList.getLast();
373 }
374
375 /**
376 * 棧是否為空
377 * @return
378 */
379 public boolean isEmpty() {
380 return stackList.isEmpty();
381 }
382 }
383
384 public static void main(String[] args) {
385
386 String str = "1+(2+3)*(100-5*(9+8))/2.3+6-19";
387
388
389
390
391 System.out.println("====================================");
392
393 //將四則運算字符串分解為逆波蘭表達式后計算結果
394 Arithmetic arithmetic=new Arithmetic(str,10,RoundingMode.HALF_UP);
395 String rpn=arithmetic.getRPN();
396 System.out.println("逆波蘭表達式 : "+rpn);
397 System.out.println("計算結果 : "+arithmetic.calculate());
398 }
399
400 }
401
最后的運行計算結果如下：
====================================
逆波蘭表達式 : 1 2 3 + 100 5 9 8 + * - 2.3 / * 6 19 - + +
計算結果 : 20.6086956520
posted on 2010-07-29 17:44
snoics 閱讀(3399)
評論(2) 編輯 收藏