很久沒有回來這里寫技術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 閱讀(1762)
評論(6) 編輯 收藏