很久没有回来这里写技术BLOG了，这里的氛围还行，大家都对一个问题积极的思考（至少之前这里给我的感觉是这样的），2年里面自己也忙着做些事情，没有写，最近有空也就写写，偶尔会去oschine.net看看新闻，然后就在那里看到了一个人提出的问题很有意思，就是怎么表达式求解，例如(1 + 2) / 3 - 1 * 2 + 5 / (3 + 2)这样的字符串输入，怎么样解析之后输出结果。说来也好笑，对于我这个不是计算机专业出身的人，自然也不知道用逆波兰和递归下降（后来看回帖才知道有这两个算法，然后google之发现全是这样的算法求解），我的目标很简单，就是想去解决这个问题。所以我花了近3小时（太笨）从构思到写范例程序到调试了一番，结果还不错，所以记录下来，给看多了逆波兰，看多了标准递归下降的人一点新鲜空气。
其实我的想法很简单，就是模拟人的思维去解决这个问题，我们人解决算式的时候，不管算得多快，都是a+b,a-b,a*b,a/b这样最原始的一个一个的求解的，所以我把这样的方式称为原子表达式，就是不可再分割的表达式，而我的解法就是要去将表达式分解成原子的之后进行计算，然后再递归回来，最后得出答案。很朴素，很简单的想法吧。就拿(1 + 2) / 3 - 1 * 2 + 5 / (3 + 2)这个来分析过程吧。我们先看到()，所以取出()中的内容，刚好，()中的内容是原子的，1+2，于是我们得出答案3，然后与后面的式子形成新的表达式，3/3-1*2+5/(3+2)，这时候我们继续找()，3+2，之后的表达式成了3/3-1*2+5/5，然后继续找括号，没有了，于是我们按照计算法则，先乘除，找到*/，然后取出原子式3/3，于是有了1-1×2+5/5，然后继续，1×2，1-2+5/5，然后继续，5/5，有了1-2+1，然后没有乘除了，我们来算加减，找到1-2，于是有了-1+1，找到-1+1，最后输出0。
下面贴出我的范例代码，没有重构，没有优化（比如可以尝试将平级的()，*/和+,-一次迭代就计算完毕，上例中的(1+2)和(3+2)一次迭代计算完成3/3-1×2+5/5，然后3/3，1×2，5/5一次迭代完成1-2+1，然后再完成1-2，-1+1，这样便少了几步表达式的重新组合)，测试的算式也就几个，仅仅是一个示意，如有BUG，可自行修改。还是老规矩，先上运算结果吧。
1+(-1-2)/3-2*(-2+1) = 2.0
122+2*(11-1)/(-3-(2-3)) = 112.0
-2*3 + (-3+4) = -5.0
((1 + 2) / 3 + 1) * 2 = 4.0
(1 + 2) / 3 - 1 * 2 + 5 / (3 + 2) = 0.0
(1.5 + 2.5) / 4 + 1 * 2 - 5 / (2 - 4) = 5.5
10-4+123+100*98*8/100*4*3+3-12/3/4*2*12*12/4+4-8+12/3*12+12 = 9524.0
1 public class Cal {
2
3 public static void main(String[] args) {
4 Cal cal = new Cal();
5 String expression = "1+(-1-2)/3-2*(-2+1)";
6 double result = cal.caculate(expression);
7 System.out.println(expression + " = " + result);
8 expression = "122+2*(11-1)/(-3-(2-3))";
9 result = cal.caculate(expression);
10 System.out.println(expression + " = " + result);
11 expression = "-2*3 + (-3+4)";
12 result = cal.caculate(expression);
13 System.out.println(expression + " = " + result);
14 expression = "((1 + 2) / 3 + 1) * 2";
15 result = cal.caculate(expression);
16 System.out.println(expression + " = " + result);
17 expression = "(1 + 2) / 3 - 1 * 2 + 5 / (3 + 2)";
18 result = cal.caculate(expression);
19 System.out.println(expression + " = " + result);
20 expression = "(1.5 + 2.5) / 4 + 1 * 2 - 5 / (2 - 4)";
21 result = cal.caculate(expression);
22 System.out.println(expression + " = " + result);
23 expression = "10-4+123+100*98*8/100*4*3+3-12/3/4*2*12*12/4+4-8+12/3*12+12";
24 result = cal.caculate(expression);
25 System.out.println(expression + " = " + result);
26 }
27
28 double caculate(String expression) {
29 expression = clean(expression);
30 return parse(expression);
31 }
32
33 private String clean(String expression) {
34 StringBuilder sb = new StringBuilder();
35 char[] chars = expression.toCharArray();
36 for (char c : chars) {
37 if (c != ' ')
38 sb.append(c);
39 }
40 return sb.toString();
41 }
42
43 private double parse(String expression) {
44 // System.out.println(expression);
45 char[] chars = expression.toCharArray();
46 // 已经是原子状态，则直接计算
47 if (isAtomic(expression)) {
48 int delimIndex = findFirstDelimIndex(expression);
49 char delim = expression.charAt(delimIndex);
50 double first = Double.valueOf(expression.substring(0, delimIndex));
51 double second = Double.valueOf(expression.substring(delimIndex + 1));
52 switch (delim) {
53 case '+':
54 return first + second;
55 case '-':
56 return first - second;
57 case '*':
58 return first * second;
59 case '/':
60 return first / second;
61 default:
62 throw new RuntimeException("parse error. 未知的运算符号");
63 }
64 }
65 // 不是原子状态，那就来解析表达式
66 // 先查找是否有()的状态
67 int first = -1;
68 int last = -1;
69 for (int i = 0; i < chars.length; i++) {
70 char c = chars[i];
71 if (c == '(') {
72 first = i;
73 } else if (c == ')') {
74 last = i;
75 break; // 如果遇到)括号了，则说明有包含关系，退出，进行解析。
76 }
77 }
78 if ((first >= 0 && first >= last)) {
79 throw new RuntimeException("parse error.表达式错误，缺少反括号");
80 }
81 if (first >= 0 && last > first) { // 正常情况
82 String newExpression = expression.substring(first + 1, last);
83 // 将括号中的表达式弄出来，进行计算
84 double result = parse(newExpression);
85 // 然后将计算结果替换这个表达式，然后递归处理
86 StringBuilder sb = new StringBuilder();
87 if (first > 0)
88 sb.append(expression.substring(0, first));
89 sb.append(result);
90 sb.append(expression.substring(last + 1));
91 return parse(sb.toString());
92 }
93
94 // 不是括号，那么就来处理乘除，3+3*2/3*2 + 1这样的情况
95 last = -1;
96 for (int i = 0; i < chars.length; i++) {
97 char c = chars[i];
98 if (c == '*' || c == '/') {
99 last = i;
100 break; // 如果遇到*或者/了，则先进行解析。
101 }
102 }
103 if (last >= 0) {
104 // 找到之后，就看靠近的前面是否有+，-运算符，如果有则，得到那个+，-的index(也有可能是负数)，然后便可通过index得到*,/前面的数字
105 // 然后后面是否有+，-,*,/运算符，如果存在，则得到index，然后通last和Index来得到后一个数字
106 // 然后形成新的expression，进行计算，然后通过计算结果替换这个expression，继续解析
107 // 如 2+3+3*2/3*2 +1 ，在完成之后形成新的2+3+6/3*2+1，继续进行解析
108 String forward = expression.substring(0, last);
109 String appendForward = null;
110 int addIndex = forward.lastIndexOf("+");
111 int divIndex = forward.lastIndexOf("-"); // 减号要特殊处理，有可能这是个负数
112 if (divIndex > 0 && isDelim(forward.charAt(divIndex - 1))) {
113 divIndex = divIndex - 1;
114 }
115 StringBuilder sb = new StringBuilder();
116 if (addIndex != -1 && addIndex >= divIndex) { // 这里>=是因为可能是因为减号其实是负号，所以移位了
117 sb.append(forward.substring(addIndex + 1));
118 appendForward = forward.substring(0, addIndex + 1);
119 } else if (divIndex != -1 && addIndex < divIndex) {
120 sb.append(forward.substring(divIndex + 1));
121 appendForward = forward.substring(0, divIndex + 1);
122 } else {
123 sb.append(forward); // 前面没有符号，直接就是数字(有可能是负数)
124 }
125
126 sb.append(expression.charAt(last)); // 运算符号
127
128 String backward = expression.substring(last + 1);
129 String appendBackward = null;
130 int index = findFirstDelimIndex(backward);
131 if (index != -1) {
132 sb.append(backward.substring(0, index));
133 appendBackward = backward.substring(index);// 这里自带了运算符，后面不用加了
134 } else {
135 sb.append(backward);
136 }
137 double result = parse(sb.toString());
138
139 sb = new StringBuilder();
140 if (appendForward != null)
141 sb.append(appendForward);
142 sb.append(result);
143 if (appendBackward != null)
144 sb.append(appendBackward);
145 return parse(sb.toString());
146 }
147
148 // 不是括号，也不是乘除，只有加减，例如 3+2+1-5-3
149 last = -1;
150 for (int i = 0; i < chars.length; i++) {
151 char c = chars[i];
152 if (c == '+' || (c == '-' && i != 0)) {
153 last = i;
154 break; // 谁是第一个，就弄谁
155 }
156 }
157 if (last >= 0) {
158 // 查找后面是否有+，-,*,/运算符，如果存在，则得到index，然后通last和Index来得到后一个数字
159 // 然后形成新的expression，进行计算，然后通过计算结果替换这个expression，继续解析
160 // 如 2+3+3+1 ，在完成之后形成新的5+3+1，继续进行解析
161 String forward = expression.substring(0, last);
162 StringBuilder sb = new StringBuilder();
163 sb.append(forward); // 前面没有符号，直接就是数字(有可能是负数)
164 sb.append(expression.charAt(last)); // 运算符号
165 String backward = expression.substring(last + 1);
166 String appendBackward = null;
167 int index = findFirstDelimIndex(backward);
168 if (index != -1) {
169 sb.append(backward.substring(0, index));
170 appendBackward = backward.substring(index); // 这里自带了运算符，后面不用加了
171 } else {
172 sb.append(backward);
173 }
174 double result = parse(sb.toString());
175 sb = new StringBuilder();
176 sb.append(result);
177 if (appendBackward != null) {
178 sb.append(appendBackward);
179 }
180 return parse(sb.toString());
181 }
182 return 0;
183 }
184
185 private boolean isDelim(char c) {
186 return (c == '+' || c == '*' || c == '/' || c == '-');
187 }
188
189 /**
190 * 查找第一个运算符号的index
191 */
192 private int findFirstDelimIndex(String expression) {
193 char[] chars = expression.toCharArray();
194 for (int i = 0; i < chars.length; i++) {
195 char c = chars[i];
196 if (c == '+' || c == '*' || c == '/') {
197 return i;
198 }
199 if (c == '-') {
200 if (i != 0 && chars[i - 1] != '+' && chars[i - 1] != '-' && chars[i - 1] != '*' && chars[i - 1] != '/') // 前面有可能是负数
201 return i;
202 }
203 }
204 return -1;
205 }
206
207 /**
208 * 是否是原子式子
209 */
210 private boolean isAtomic(String expression) {
211 char[] chars = expression.toCharArray();
212 int delimCount = 0;
213 for (int i = 0; i < chars.length; i++) {
214 char c = chars[i];
215 if (c == '+' || c == '*' || c == '/' || (c == '-' && i != 0 && chars[i - 1] != '+' && chars[i - 1] != '-' && chars[i - 1] != '*' && chars[i - 1] != '/'))
216 delimCount++;
217 }
218 return delimCount == 1;
219 }
220 }
请忽略我代码的英文，我随便写的，这里如果取消注释掉的44行，我们就可以看到运算轨迹了，我帖2个比较简单的，1个是我们刚刚提到的范例，一个是有双括号的，看看算法是否按我心意，快快显灵。
第一个：(1 + 2) / 3 - 1 * 2 + 5 / (3 + 2)，可以看到先清空了空格，方便取得下标。
(1+2)/3-1*2+5/(3+2)
1+2
3.0/3-1*2+5/(3+2)
3+2
3.0/3-1*2+5/5.0
3.0/3
1.0-1*2+5/5.0
1*2
1.0-2.0+5/5.0
5/5.0
1.0-2.0+1.0
1.0-2.0
-1.0+1.0
(1 + 2) / 3 - 1 * 2 + 5 / (3 + 2) = 0.0
嗯，跟算法的运算轨迹是一致的。
第二个：122+2*(11-1)/(-3-(2-3))，双括号嵌套的。
122+2*(11-1)/(-3-(2-3))
11-1
122+2*10.0/(-3-(2-3))
2-3
122+2*10.0/(-3--1.0)
-3--1.0
122+2*10.0/-2.0
2*10.0
122+20.0/-2.0
20.0/-2.0
122+-10.0
122+2*(11-1)/(-3-(2-3)) = 112.0
嗯，不错，不错，跟算法所设想的运算轨迹是一致的。
本文的目的在于能通过这样一个老问题构思出的不同的解法来抛砖引玉，希望如果要回帖的童鞋们不要简单的说，用中缀转后缀（逆波兰）多简单啊，用递归下降（这个知道的可能不如逆波兰多）多简单啊，这样我就是抛砖引瓦了，这种教科书式的方式在已知问题和解答的情况下咱们可以照本宣科，但是假设我们遇到一个全新的问题，而且没有教科书告诉你用这个方法去解的情况，就是逼自己想办法的时候了。
PS1：
有回帖说，这也算递归下降，并且说我的原子式是树叶子节点，也就是说这位仁兄把我的处理过程映射到树的结构中去，我觉得树的这个想法很好，所以我立刻尝试了并构造了一个树结构(1 + 2) / 3 - 1 * 2 + 5 / (3 + 2)，这里假设我们的节点有{运算符，数字，结果}三个字段。
+
/ \
- /
/ \ / \
/ * 5 +
/ \ / \ / \
+ 3 1 2 3 2
/ \
1 2
这样，这个树的特点就是最底层的子节点都是数字，如果该节点存在子节点（左，右，且不是数字），那么继续向下，如果是数字则返回，然后看右边的子节点是否是数字，如果不是继续向下，直到左右子节点都是数字，然后得到父节点的运算符，然后进行计算，并且将结果存储起来，然后递归回去，最后得到结果。我来模拟一下这个树的变化，第一次，我们找到了1+2，所以
计算之后变为了:
+
/ \
- /
/ \ / \
/ * 5 +
/ \ / \ / \
3 3 1 2 3 2
这个时候回到“/”这个节点，然后查看右节点，是数字，左右子节点都是数字了计算出结果之后：
+
/ \
- /
/ \ / \
1 * 5 +
/ \ / \
1 2 3 2
这个时候回到“-”号，但是右边还是“×”号，所以继续查看“×”号的左右子节点，是数字，计算结果：
+
/ \
- /
/ \ / \
1 2 5 +
/ \
3 2
接着×号有了结果，回到“-”号，左右都是数字了，计算结果，以此类推，最后得到结果为0。当然这是我根据那位仁兄树结构的提示构思的运算过程，那么运算过程有了，如何通过表达式构造树，还有就是我这个树的构造方式是否正确，我就留给大家了，重要的是能引起大家的思考，一个问题带来的不同解法（直吸管变成弯吸管就算创新了，所以大家要是有一点点的想法或就在我这个方法上有改进也可以说出来探讨），再次感谢那位回帖的仁兄。
posted on 2011-11-09 10:36
ruislan 阅读(1731)
评论(6) 编辑 收藏