赵玉伟的博客

java实现简单四则运算

题目

若干年前有一次面试,被问及的题目为:
有一个字符串表达式,只包含数字以及 +、-、*、/、(、)六种运算符,比如:(5-3)*3+10/3-6,计算这种表达式的结果。
当时第一思考的是通过构造一棵树来实现计算符号的优先级问题,但是没有一个完整的思路。后来做了作业,这个问题需要两个知识点:

1、逆波兰式
2、栈

多说一句, 算法是需要长时间积累的,针对某一种特定问题,其实有其固定的算法,可以理解为套路。这些算法算是领域内的精华。如果在自己的算法库中,没有积累解决某种问题的算法,哪怕想破天,大部分人也不会立刻想到解决问题的算法。所以, 当被问及某种算法的问题时,其实考验的并不是聪明与否, 而是对于所涉猎的算法的广度。

逆波兰式

算法表达式的表示方法有以下三种:

中缀表达法;运算符在中间,eg: a + b
前缀表示法; 运算符在前面, eg: +ab
后缀表示法; 运算符在后面,eg: ab+

而逆波兰式,其实就是后缀表示法; 波兰式,就是中缀表示法。由于我们的习惯,我们对于中缀表示法的理解是最直观的;但是,计算机在计算的时候是一个字符一个字符的扫描,然后进行相应的处理。所以,计算机不太善于理解中缀表示法,但是计算机善于理解后缀表示法, 因为有一种数据结构, 叫做栈, 可以将操作数入栈, 碰到操作符时,出栈,完成计算; 然后再次将计算结果作为操作数入栈……。

那么,回到问题,要计算一个算术表达式, 第一步首先需要先将其转换成后缀表达式。如何转换?
网上的例子

原则: 转换成后缀表达式之后, 从左到右扫描字符串,碰到第一个操作符, 就把当前操作符的前两个操作数取出来,进行计算,然后再继续扫描,这一步可以通过人工检查,和中缀表达式进行比对,来检查数据的正确性。

主要用来临时存储计算过程中产生的值,需要将中缀表达式频繁的出栈, 入栈。

例子

直接上代码

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
194
195
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import org.apache.commons.lang.StringUtils;
public class CalculateUtil {
/**
* 将字符串,按照操作数,以及操作符,存储到List中
* @return
*/
private static List<String> convertFromCalcStr(String calcStr){
List<String> output = new ArrayList<String>();
StringBuffer sb = new StringBuffer();
for(char c : calcStr.toCharArray()){
if(Constants.CALC_SYMBOL.indexOf(c) >= 0){
if(sb.length() > 0){
output.add(sb.toString());
}
sb = new StringBuffer();
output.add(String.valueOf(c));
}else{
sb.append(String.valueOf(c));
}
}
if(sb.length() > 0){
output.add(sb.toString());
}
return output;
}
/**
* 将中缀表达式转成后缀表达式
* @param middleExp
* @return
*/
private static List<String> makePostfixExpress(List<String> middleExp){
List<String> postFixExp = new ArrayList<String>();
Stack<String> stack = new Stack<String>();
for(String el : middleExp){
if(el.equals("+") || el.equals("-")){
while(!stack.isEmpty()){
String temp = stack.peek();
if(!temp.equals("(")){
postFixExp.add(stack.pop());
}else{
break;
}
}
stack.push(el);
}else if(el.equals("*") || el.equals("/")){
while(!stack.isEmpty()){
String temp = stack.peek();
if((temp.equals("*") || temp.equals("/")) && !temp.equals("(")){
postFixExp.add(stack.pop());
}else{
break;
}
}
stack.push(el);
}else if(el.equals("(")){
stack.push("(");
}else if(el.equals(")")){
while(!stack.isEmpty()){
String temp = stack.peek();
if(!temp.equals("(")){
postFixExp.add(stack.pop());
}else{
break;
}
}
stack.pop();
}else{
postFixExp.add(el);
}
}
while(!stack.isEmpty()){
postFixExp.add(stack.pop());
}
return postFixExp;
}
/**
* 按照精度,计算后缀表达式的值
* @param input
* @return
*/
private static BigDecimal calcPostExpress(List<String> input, int scale){
Stack<BigDecimal> ms = new Stack<BigDecimal>();
for(String s : input){
if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")){
BigDecimal right = ms.pop(), left = ms.pop();
BigDecimal temp = calcExpress(left, right, s, scale);
ms.push(temp);
}else{
ms.push(new BigDecimal(s));
}
}
// the result is stored into stack
BigDecimal ret = ms.pop();
if(ret == null){
throw new RuntimeException("calc express error. result is null!!!");
}
return ret;
}
/**
* 进行实际的四则运算
* @param left 左操作数
* @param right 右操作数
* @param op 运算符
* @param scale 精度
* @return
*/
public static BigDecimal calcExpress(BigDecimal left, BigDecimal right, String op, int scale){
if(left == null || right == null){
return BigDecimal.ZERO;
}
BigDecimal ret = BigDecimal.ZERO;
if(op.equals("+")){
ret = left.add(right);
}else if(op.equals("-")){
ret = left.subtract(right);
}else if(op.equals("*")){
ret = left.multiply(right);
}else if(op.equals("/")){
if(left.compareTo(BigDecimal.ZERO) == 0 || right.compareTo(BigDecimal.ZERO) == 0){
// 记录日志
ret = BigDecimal.ZERO;
}else{
ret = left.divide(right, scale, BigDecimal.ROUND_HALF_UP);
}
}
return ret.setScale(scale, BigDecimal.ROUND_HALF_UP);
}
/**
* 计算表达式的入口方法
* @param express
* @param precision
* @return
*/
public static BigDecimal doExpCalc(String express, int scale){
if(StringUtils.isEmpty(express)){
throw new RuntimeException("express is null. calc abort.");
}
if(scale < 0){
throw new RuntimeException("scale must >= 0.");
}
express = express.replaceAll("\\s*", "");
List<String> expList = convertFromCalcStr(express);
List<String> postExp = makePostfixExpress(expList);
BigDecimal result = BigDecimal.ZERO;
try {
result = calcPostExpress(postExp, scale);
} catch (Exception e) {
// 记录日志
}
return result;
}
}