对四则运算表达式字符串进行解析后计算出结果，可以使用逆波兰表达式进行处理。
首先说明一下什是逆波兰表达式：
逆波兰表达式又叫做后缀表达式。在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，所以，这种表示法也称为中缀表示。波兰逻辑学家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 阅读(3384)
评论(2) 编辑 收藏