對(duì)四則運(yùn)算表達(dá)式字符串進(jìn)行解析后計(jì)算出結(jié)果，可以使用逆波蘭表達(dá)式進(jìn)行處理。
首先說(shuō)明一下什是逆波蘭表達(dá)式：
逆波蘭表達(dá)式又叫做后綴表達(dá)式。在通常的表達(dá)式中，二元運(yùn)算符總是置于與之相關(guān)的兩個(gè)運(yùn)算對(duì)象之間，所以，這種表示法也稱為中綴表示。波蘭邏輯學(xué)家J.Lukasiewicz于1929年提出了另一種表示表達(dá)式的方法。按此方法，每一運(yùn)算符都置于其運(yùn)算對(duì)象之后，故稱為后綴表示。
將一個(gè)普通的中序表達(dá)式轉(zhuǎn)換為逆波蘭表達(dá)式的一般算法是：
(1)首先構(gòu)造一個(gè)運(yùn)算符棧，此運(yùn)算符在棧內(nèi)遵循越往棧頂優(yōu)先級(jí)越高的原則。
(2)讀入一個(gè)用中綴表示的簡(jiǎn)單算術(shù)表達(dá)式，為方便起見(jiàn),設(shè)該簡(jiǎn)單算術(shù)表達(dá)式的右端多加上了優(yōu)先級(jí)最低的特殊符號(hào)“#”。
(3)從左至右掃描該算術(shù)表達(dá)式，從第一個(gè)字符開(kāi)始判斷，如果該字符是數(shù)字，則分析到該數(shù)字串的結(jié)束并將該數(shù)字串直接輸出。
(4)如果不是數(shù)字，該字符則是運(yùn)算符，此時(shí)需比較優(yōu)先關(guān)系。
做法如下：將該字符與運(yùn)算符棧頂?shù)倪\(yùn)算符的優(yōu)先關(guān)系相比較。如果，該字符優(yōu)先關(guān)系高于此運(yùn)算符棧頂?shù)倪\(yùn)算符，則將該運(yùn)算符入棧。倘若不是的話，則將棧頂?shù)倪\(yùn)算符從棧中彈出，直到棧頂運(yùn)算符的優(yōu)先級(jí)低于當(dāng)前運(yùn)算符，將該字符入棧。
(5)重復(fù)上述操作(3)-(4)直至掃描完整個(gè)簡(jiǎn)單算術(shù)表達(dá)式，確定所有字符都得到正確處理，我們便可以將中綴式表示的簡(jiǎn)單算術(shù)表達(dá)式轉(zhuǎn)化為逆波蘭表示的簡(jiǎn)單算術(shù)表達(dá)式。
以上內(nèi)容來(lái)源百度
下面進(jìn)入正題，按照以上的算法說(shuō)明自己實(shí)現(xiàn)四則運(yùn)算如下：
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 * 通過(guò)四則運(yùn)算表達(dá)式字符串，構(gòu)造逆波蘭表達(dá)式，計(jì)算結(jié)果
12 *
13 * (1)從左至右掃描該算術(shù)表達(dá)式，從第一個(gè)字符開(kāi)始判斷，
14 * 如果該字符是數(shù)字，則分析到該數(shù)字串的結(jié)束并將該數(shù)字串直接輸出。
15 *
16 * (2)如果不是數(shù)字，該字符則是運(yùn)算符，此時(shí)需比較優(yōu)先關(guān)系。
17 做法如下：將該字符與運(yùn)算符棧頂?shù)倪\(yùn)算符的優(yōu)先關(guān)系相比較。
18 如果，該字符優(yōu)先關(guān)系高于此運(yùn)算符棧頂?shù)倪\(yùn)算符，則將該運(yùn)算符入棧。
19 倘若不是的話，則將棧頂?shù)倪\(yùn)算符從棧中彈出，直到棧頂運(yùn)算符的優(yōu)先級(jí)
20 低于當(dāng)前運(yùn)算符，將該字符入棧。
21
22 (3)重復(fù)上述操作(1)-(2)直至掃描完整個(gè)簡(jiǎn)單算術(shù)表達(dá)式，確定所有字符都得到正確處理，
23 我們便可以將中綴式表示的簡(jiǎn)單算術(shù)表達(dá)式轉(zhuǎn)化為逆波蘭表示的簡(jiǎn)單算術(shù)表達(dá)式。
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 //四則運(yùn)算式
62 private String exp;
63
64 //精確到小數(shù)點(diǎn)后幾位
65 private int precision=2;
66
67 //取舍模式
68 private RoundingMode roundingMode=RoundingMode.HALF_UP;
69
70 //四則運(yùn)算解析
71 private List<String> expList = new ArrayList<String>();
72
73 //存放逆波蘭表達(dá)式
74 private List<String> rpnList = new ArrayList<String>();
75
76 /**
77 * 四則運(yùn)算
78 * @param exp 四則運(yùn)算表達(dá)式
79 * @param precision 精確到小數(shù)點(diǎn)后幾位
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 * 分析四則運(yùn)算表達(dá)式，將數(shù)字與運(yùn)算符進(jìn)行分解
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 * 判斷當(dāng)前字符或字符串是否是數(shù)字
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 * 判斷當(dāng)前字符是否是 (
138 * @param str
139 * @return
140 */
141 private boolean isParenthesesStart(String str) {
142 return str.equals(OPSTART);
143 }
144
145 /**
146 * 判斷當(dāng)前字符是否是 )
147 * @param str
148 * @return
149 */
150 private boolean isParenthesesEnd(String str) {
151 return str.equals(OPEND);
152 }
153
154 /**
155 * 判斷當(dāng)前字符是否是高優(yōu)先級(jí)運(yùn)算符 * /
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 * 對(duì)比兩個(gè)字符串的優(yōu)先級(jí)
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 * 將分解后的四則運(yùn)算列表構(gòu)建成逆波蘭表達(dá)式列表
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 //如果是數(shù)字，直接放到逆波蘭鏈表的最后
200 if (isNumber(c)) {
201 rpnList.add(c);
202 } else {
203 //如果不是數(shù)字
204
205 //如果是左括號(hào)，則直接將左括號(hào)壓入棧
206 if (isParenthesesStart(c)) {
207 stack.push(c);
208 } else if (isParenthesesEnd(c)) {
209 //如果是右括號(hào)
210
211 //進(jìn)行出棧操作，直到棧為空或者遇到第一個(gè)左括號(hào)
212 while (!stack.isEmpty()) {
213 //將棧頂字符串做出棧操作
214 String tempC = stack.pop();
215 if (!tempC.equals(OPSTART)) {
216 //如果不是左括號(hào)，則將字符串直接放到逆波蘭鏈表的最后
217 rpnList.add(tempC);
218 }else{
219 //如果是左括號(hào)，退出循環(huán)操作
220 break;
221 }
222 }
223 } else {
224 //如果棧內(nèi)為空
225 if (stack.isEmpty()) {
226 //將當(dāng)前字符串直接壓棧
227 stack.push(c);
228 } else {
229 //如果棧不為空
230
231 //比較棧頂字符串與當(dāng)前字符串的優(yōu)先級(jí)，
232 if (compare(stack.top(), c)) {
233 //如果棧頂元素的優(yōu)先級(jí)大于當(dāng)前字符串,則進(jìn)行出棧操作
234 //將棧頂元素直接放到逆波蘭鏈表的最后
235 //直到棧內(nèi)為空，或者當(dāng)前元素的優(yōu)先級(jí)不小于棧頂元素優(yōu)先級(jí)
236 while (!stack.isEmpty() && compare(stack.top(), c)) {
237 rpnList.add(stack.pop());
238 }
239 }
240 //將當(dāng)前字符串直接壓棧
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 * 通過(guò)逆波蘭表達(dá)式計(jì)算結(jié)果
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 * 獲取逆波蘭表達(dá)式字符串
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 * 按精確度計(jì)算結(jié)果
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 //將四則運(yùn)算字符串分解為逆波蘭表達(dá)式后計(jì)算結(jié)果
394 Arithmetic arithmetic=new Arithmetic(str,10,RoundingMode.HALF_UP);
395 String rpn=arithmetic.getRPN();
396 System.out.println("逆波蘭表達(dá)式 : "+rpn);
397 System.out.println("計(jì)算結(jié)果 : "+arithmetic.calculate());
398 }
399
400 }
401
最后的運(yùn)行計(jì)算結(jié)果如下：
====================================
逆波蘭表達(dá)式 : 1 2 3 + 100 5 9 8 + * - 2.3 / * 6 19 - + +
計(jì)算結(jié)果 : 20.6086956520
posted on 2010-07-29 17:44
snoics 閱讀(3411)
評(píng)論(2) 編輯 收藏