很久沒(méi)有回來(lái)這里寫(xiě)技術(shù)BLOG了，這里的氛圍還行，大家都對(duì)一個(gè)問(wèn)題積極的思考（至少之前這里給我的感覺(jué)是這樣的），2年里面自己也忙著做些事情，沒(méi)有寫(xiě)，最近有空也就寫(xiě)寫(xiě)，偶爾會(huì)去oschine.net看看新聞，然后就在那里看到了一個(gè)人提出的問(wèn)題很有意思，就是怎么表達(dá)式求解，例如(1 + 2) / 3 - 1 * 2 + 5 / (3 + 2)這樣的字符串輸入，怎么樣解析之后輸出結(jié)果。說(shuō)來(lái)也好笑，對(duì)于我這個(gè)不是計(jì)算機(jī)專業(yè)出身的人，自然也不知道用逆波蘭和遞歸下降（后來(lái)看回帖才知道有這兩個(gè)算法，然后google之發(fā)現(xiàn)全是這樣的算法求解），我的目標(biāo)很簡(jiǎn)單，就是想去解決這個(gè)問(wèn)題。所以我花了近3小時(shí)（太笨）從構(gòu)思到寫(xiě)范例程序到調(diào)試了一番，結(jié)果還不錯(cuò)，所以記錄下來(lái)，給看多了逆波蘭，看多了標(biāo)準(zhǔn)遞歸下降的人一點(diǎn)新鮮空氣。
其實(shí)我的想法很簡(jiǎn)單，就是模擬人的思維去解決這個(gè)問(wèn)題，我們?nèi)私鉀Q算式的時(shí)候，不管算得多快，都是a+b,a-b,a*b,a/b這樣最原始的一個(gè)一個(gè)的求解的，所以我把這樣的方式稱為原子表達(dá)式，就是不可再分割的表達(dá)式，而我的解法就是要去將表達(dá)式分解成原子的之后進(jìn)行計(jì)算，然后再遞歸回來(lái)，最后得出答案。很樸素，很簡(jiǎn)單的想法吧。就拿(1 + 2) / 3 - 1 * 2 + 5 / (3 + 2)這個(gè)來(lái)分析過(guò)程吧。我們先看到()，所以取出()中的內(nèi)容，剛好，()中的內(nèi)容是原子的，1+2，于是我們得出答案3，然后與后面的式子形成新的表達(dá)式，3/3-1*2+5/(3+2)，這時(shí)候我們繼續(xù)找()，3+2，之后的表達(dá)式成了3/3-1*2+5/5，然后繼續(xù)找括號(hào)，沒(méi)有了，于是我們按照計(jì)算法則，先乘除，找到*/，然后取出原子式3/3，于是有了1-1×2+5/5，然后繼續(xù)，1×2，1-2+5/5，然后繼續(xù)，5/5，有了1-2+1，然后沒(méi)有乘除了，我們來(lái)算加減，找到1-2，于是有了-1+1，找到-1+1，最后輸出0。
下面貼出我的范例代碼，沒(méi)有重構(gòu)，沒(méi)有優(yōu)化（比如可以嘗試將平級(jí)的()，*/和+,-一次迭代就計(jì)算完畢，上例中的(1+2)和(3+2)一次迭代計(jì)算完成3/3-1×2+5/5，然后3/3，1×2，5/5一次迭代完成1-2+1，然后再完成1-2，-1+1，這樣便少了幾步表達(dá)式的重新組合)，測(cè)試的算式也就幾個(gè)，僅僅是一個(gè)示意，如有BUG，可自行修改。還是老規(guī)矩，先上運(yùn)算結(jié)果吧。
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 // 已經(jīng)是原子狀態(tài)，則直接計(jì)算
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. 未知的運(yùn)算符號(hào)");
63 }
64 }
65 // 不是原子狀態(tài)，那就來(lái)解析表達(dá)式
66 // 先查找是否有()的狀態(tài)
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; // 如果遇到)括號(hào)了，則說(shuō)明有包含關(guān)系，退出，進(jìn)行解析。
76 }
77 }
78 if ((first >= 0 && first >= last)) {
79 throw new RuntimeException("parse error.表達(dá)式錯(cuò)誤，缺少反括號(hào)");
80 }
81 if (first >= 0 && last > first) { // 正常情況
82 String newExpression = expression.substring(first + 1, last);
83 // 將括號(hào)中的表達(dá)式弄出來(lái)，進(jìn)行計(jì)算
84 double result = parse(newExpression);
85 // 然后將計(jì)算結(jié)果替換這個(gè)表達(dá)式，然后遞歸處理
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 // 不是括號(hào)，那么就來(lái)處理乘除，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; // 如果遇到*或者/了，則先進(jìn)行解析。
101 }
102 }
103 if (last >= 0) {
104 // 找到之后，就看靠近的前面是否有+，-運(yùn)算符，如果有則，得到那個(gè)+，-的index(也有可能是負(fù)數(shù))，然后便可通過(guò)index得到*,/前面的數(shù)字
105 // 然后后面是否有+，-,*,/運(yùn)算符，如果存在，則得到index，然后通last和Index來(lái)得到后一個(gè)數(shù)字
106 // 然后形成新的expression，進(jìn)行計(jì)算，然后通過(guò)計(jì)算結(jié)果替換這個(gè)expression，繼續(xù)解析
107 // 如 2+3+3*2/3*2 +1 ，在完成之后形成新的2+3+6/3*2+1，繼續(xù)進(jìn)行解析
108 String forward = expression.substring(0, last);
109 String appendForward = null;
110 int addIndex = forward.lastIndexOf("+");
111 int divIndex = forward.lastIndexOf("-"); // 減號(hào)要特殊處理，有可能這是個(gè)負(fù)數(shù)
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) { // 這里>=是因?yàn)榭赡苁且驗(yàn)闇p號(hào)其實(shí)是負(fù)號(hào)，所以移位了
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); // 前面沒(méi)有符號(hào)，直接就是數(shù)字(有可能是負(fù)數(shù))
124 }
125
126 sb.append(expression.charAt(last)); // 運(yùn)算符號(hào)
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);// 這里自帶了運(yùn)算符，后面不用加了
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 // 不是括號(hào)，也不是乘除，只有加減，例如 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; // 誰(shuí)是第一個(gè)，就弄誰(shuí)
155 }
156 }
157 if (last >= 0) {
158 // 查找后面是否有+，-,*,/運(yùn)算符，如果存在，則得到index，然后通last和Index來(lái)得到后一個(gè)數(shù)字
159 // 然后形成新的expression，進(jìn)行計(jì)算，然后通過(guò)計(jì)算結(jié)果替換這個(gè)expression，繼續(xù)解析
160 // 如 2+3+3+1 ，在完成之后形成新的5+3+1，繼續(xù)進(jìn)行解析
161 String forward = expression.substring(0, last);
162 StringBuilder sb = new StringBuilder();
163 sb.append(forward); // 前面沒(méi)有符號(hào)，直接就是數(shù)字(有可能是負(fù)數(shù))
164 sb.append(expression.charAt(last)); // 運(yùn)算符號(hào)
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); // 這里自帶了運(yùn)算符，后面不用加了
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 * 查找第一個(gè)運(yùn)算符號(hào)的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] != '/') // 前面有可能是負(fù)數(shù)
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 }
請(qǐng)忽略我代碼的英文，我隨便寫(xiě)的，這里如果取消注釋掉的44行，我們就可以看到運(yùn)算軌跡了，我帖2個(gè)比較簡(jiǎn)單的，1個(gè)是我們剛剛提到的范例，一個(gè)是有雙括號(hào)的，看看算法是否按我心意，快快顯靈。
第一個(gè)：(1 + 2) / 3 - 1 * 2 + 5 / (3 + 2)，可以看到先清空了空格，方便取得下標(biāo)。
(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
嗯，跟算法的運(yùn)算軌跡是一致的。
第二個(gè)：122+2*(11-1)/(-3-(2-3))，雙括號(hào)嵌套的。
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
嗯，不錯(cuò)，不錯(cuò)，跟算法所設(shè)想的運(yùn)算軌跡是一致的。
本文的目的在于能通過(guò)這樣一個(gè)老問(wèn)題構(gòu)思出的不同的解法來(lái)拋磚引玉，希望如果要回帖的童鞋們不要簡(jiǎn)單的說(shuō)，用中綴轉(zhuǎn)后綴（逆波蘭）多簡(jiǎn)單啊，用遞歸下降（這個(gè)知道的可能不如逆波蘭多）多簡(jiǎn)單啊，這樣我就是拋磚引瓦了，這種教科書(shū)式的方式在已知問(wèn)題和解答的情況下咱們可以照本宣科，但是假設(shè)我們遇到一個(gè)全新的問(wèn)題，而且沒(méi)有教科書(shū)告訴你用這個(gè)方法去解的情況，就是逼自己想辦法的時(shí)候了。
PS1：
有回帖說(shuō)，這也算遞歸下降，并且說(shuō)我的原子式是樹(shù)葉子節(jié)點(diǎn)，也就是說(shuō)這位仁兄把我的處理過(guò)程映射到樹(shù)的結(jié)構(gòu)中去，我覺(jué)得樹(shù)的這個(gè)想法很好，所以我立刻嘗試了并構(gòu)造了一個(gè)樹(shù)結(jié)構(gòu)(1 + 2) / 3 - 1 * 2 + 5 / (3 + 2)，這里假設(shè)我們的節(jié)點(diǎn)有{運(yùn)算符，數(shù)字，結(jié)果}三個(gè)字段。
+
/ \
- /
/ \ / \
/ * 5 +
/ \ / \ / \
+ 3 1 2 3 2
/ \
1 2
這樣，這個(gè)樹(shù)的特點(diǎn)就是最底層的子節(jié)點(diǎn)都是數(shù)字，如果該節(jié)點(diǎn)存在子節(jié)點(diǎn)（左，右，且不是數(shù)字），那么繼續(xù)向下，如果是數(shù)字則返回，然后看右邊的子節(jié)點(diǎn)是否是數(shù)字，如果不是繼續(xù)向下，直到左右子節(jié)點(diǎn)都是數(shù)字，然后得到父節(jié)點(diǎn)的運(yùn)算符，然后進(jìn)行計(jì)算，并且將結(jié)果存儲(chǔ)起來(lái)，然后遞歸回去，最后得到結(jié)果。我來(lái)模擬一下這個(gè)樹(shù)的變化，第一次，我們找到了1+2，所以
計(jì)算之后變?yōu)榱?
+
/ \
- /
/ \ / \
/ * 5 +
/ \ / \ / \
3 3 1 2 3 2
這個(gè)時(shí)候回到“/”這個(gè)節(jié)點(diǎn)，然后查看右節(jié)點(diǎn)，是數(shù)字，左右子節(jié)點(diǎn)都是數(shù)字了計(jì)算出結(jié)果之后：
+
/ \
- /
/ \ / \
1 * 5 +
/ \ / \
1 2 3 2
這個(gè)時(shí)候回到“-”號(hào)，但是右邊還是“×”號(hào)，所以繼續(xù)查看“×”號(hào)的左右子節(jié)點(diǎn)，是數(shù)字，計(jì)算結(jié)果：
+
/ \
- /
/ \ / \
1 2 5 +
/ \
3 2
接著×號(hào)有了結(jié)果，回到“-”號(hào)，左右都是數(shù)字了，計(jì)算結(jié)果，以此類推，最后得到結(jié)果為0。當(dāng)然這是我根據(jù)那位仁兄樹(shù)結(jié)構(gòu)的提示構(gòu)思的運(yùn)算過(guò)程，那么運(yùn)算過(guò)程有了，如何通過(guò)表達(dá)式構(gòu)造樹(shù)，還有就是我這個(gè)樹(shù)的構(gòu)造方式是否正確，我就留給大家了，重要的是能引起大家的思考，一個(gè)問(wèn)題帶來(lái)的不同解法（直吸管變成彎吸管就算創(chuàng)新了，所以大家要是有一點(diǎn)點(diǎn)的想法或就在我這個(gè)方法上有改進(jìn)也可以說(shuō)出來(lái)探討），再次感謝那位回帖的仁兄。
posted on 2011-11-09 10:36
ruislan 閱讀(1768)
評(píng)論(6) 編輯 收藏