首先说明我算法不好&＃xff0c;跳槽的时候发现自己的基础薄弱而且不成体系&＃xff0c;所以这段时间&＃xff08;大约3个月&＃xff09;我将用全部可以利用的时间把常用的数据结构、算法、C&＃43;&＃43;对象模型、STL、泛型编程、设计模式整理一遍&＃xff0c;然后梳理一下思路&＃xff0c;做到对C&＃43;&＃43;基础知识体系“巨细匪遗&＃xff0c;秩序井然”。这个目标并没有看上去那么难&＃xff0c;可以一试。首先要攻克的是常用的数据结构和算法&＃xff0c;这样可以结合STL容器和算法一起学习。等整理完成后就列一个表&＃xff0c;现在暂时没有详细的计划&＃xff0c;先列一个粗略的计划&＃xff1a;
/* 基本结构&＃xff1a;顺序表、链表、栈、队列、哈希表、平衡二叉树、红黑树、哈夫曼树、堆、B-树、结构应用&＃xff1a;动态数组、循环队列、内存池、基本算法&＃xff1a;二分查找、快排、基数排序、堆排序、归并排序、希尔排序、算法思想&＃xff1a;回溯法、贪心法、分治法、动态规划、随机算法算法应用&＃xff1a;算术表达式解析、迷宫寻路、N皇后、综合应用&＃xff1a;脚本解释器&＃xff08;脚本与宿主程序交互、分支语句解析、循环语句解析、函数调用&＃xff09;、内存数据库&＃xff08;哈希索引、键值映射、增删改查、排序&＃xff09;*/
上面这些就够忙的了&＃xff0c;如果有好的思想则继续补充。
用vim写了一上午&＃xff0c;搞定了一个公式计算器&＃xff0c;使用一个操作栈和一个数据栈&＃xff0c;思路如下&＃xff1a;
/* 1.格式化&＃xff1a;对输入格式化处理为无空格字符串2.有效性检查&＃xff1a;每个字符的合法性、括号匹配、运算符前后必须有操作数3.入栈扫描&＃xff1a;字符为数字则视为有符号浮点数连续读入&＃xff0c;然后push到数字栈&＃xff1b;字符为操作符则判断上一个操作符的优先级&＃xff0c;决定出栈计算或push到操作栈&＃xff1b;4.出栈计算&＃xff1a;操作符出栈直到遇到 ( 或栈空&＃xff0c;操作数出栈计算&＃xff0c;结果push回栈5.重复3、4直到表达式结束 */
下面是C&＃43;&＃43;代码&＃xff1a;
1 #include
2 #include<string.h>
3 #include
4 #include
5 #include
6 #include
7 using namespace std;
8
9 stack<double> nust;
10 stack<char> chst;
11 void trimspace(char*& exp)
12 {
13 if(exp&＃61;&＃61;NULL)return;
14 while(isblank(*exp)) exp&＃43;&＃43;;
15 char* p&＃61;exp&＃43;strlen(exp)-1;
16 while(isblank(*p))p--;
17 *(p&＃43;1)&＃61;&＃39;\0&＃39;;
18 }
19
20 bool checkvalid(char* exp)
21 {
22 char validchar[]&＃61;{
23 &＃39;(&＃39;,&＃39;)&＃39;,&＃39;&＃43;&＃39;,&＃39;-&＃39;,&＃39;*&＃39;,&＃39;/&＃39;,&＃39;%&＃39;,&＃39;^&＃39;,&＃39;.&＃39;
24 };
25 int unmatch&＃61;0;
26 while(*exp!&＃61;&＃39;\0&＃39;)
27 {
28 bool valid&＃61;false;
29 for(unsigned int i&＃61;0;i<sizeof(validchar);&＃43;&＃43;i)
30 {
31 if(*exp&＃61;&＃61;validchar[i])
32 {
33 valid&＃61;true;
34 if(*exp&＃61;&＃61;&＃39;(&＃39;)
35 unmatch&＃43;&＃43;;
36 else if(*exp&＃61;&＃61;&＃39;)&＃39;)
37 unmatch--;
38 else if(!isdigit(*(exp&＃43;1))&&&＃39;(&＃39;!&＃61;*(exp&＃43;1))
39 {
40 cout<<"[8]error expression: "<<*exp<<" needs option number"<<endl;
41 return false;
42 }
43 break;
44 }
45 }
46 if(!valid && !isdigit(*exp)){
47 return false;
48 }
49 exp&＃43;&＃43;;
50 }
51 if(unmatch!&＃61;0)
52 {
53 cout<<"find unmatched ()"<<endl;
54 return false;
55 }
56 return true;
57 }
58
59 bool readfloat(char* p,int *diglen)
60 {
61 *diglen&＃61;0;
62 if(p&＃61;&＃61;NULL)return false;
63 char num[32]&＃61;{0};
64 int cnt&＃61;0;
65 int dot&＃61;0;
66 if(*p&＃61;&＃61;&＃39;-&＃39;){
67 p&＃43;&＃43;;
68 if(p&&!isdigit(*p)){
69 cout<<"[5]error expression"<<endl;
70 return false;
71 }
72 num[cnt&＃43;&＃43;]&＃61;&＃39;-&＃39;;
73 }
74 while(*p!&＃61;&＃39;\0&＃39;)
75 {
76 if(isdigit(*p))
77 num[cnt&＃43;&＃43;]&＃61;*p;
78 else if(*p&＃61;&＃61;&＃39;.&＃39;)
79 {
80 dot&＃43;&＃43;;
81 if(dot>1){
82 cout<<"[6]error expression"<<endl;
83 return false;
84 }
85 num[cnt&＃43;&＃43;]&＃61;&＃39;.&＃39;;
86 }
87 else
88 {
89 break;
90 }
91 p&＃43;&＃43;;
92 }
93 *diglen&＃61;cnt;
94 double dval &＃61; atof(num);
95 nust.push(dval);
96 cout<<"push "<
97 return true;
98 }
99
100 /*
101 * ( has 0 priority
102 * &＃43; - have 1 priority
103 * * / have 2 priority
104 * % ^ have 3 priority
105 *
106 */
107
108 int getlastpriority()
109 {
110 if(chst.empty())return 0;
111 char op&＃61;chst.top();
112 switch(op)
113 {
114 case &＃39;(&＃39;:
115 return 0;
116 case &＃39;&＃43;&＃39;:
117 case &＃39;-&＃39;:
118 return 1;
119 case &＃39;*&＃39;:
120 case &＃39;/&＃39;:
121 case &＃39;%&＃39;:
122 return 2;
123 case &＃39;^&＃39;:
124 return 3;
125 default:
126 return 0;
127 }
128 }
129
130 bool calc()
131 {
132 while(!chst.empty())
133 {
134 char op&＃61;chst.top();
135 chst.pop();
136 if(op&＃61;&＃61;&＃39;(&＃39;) break;
137 if(nust.size()<2)
138 {
139 cout<<"[2]expression error number stack size&＃61;"<
140 return false;
141 }
142 double r&＃61;nust.top();
143 nust.pop();
144 double l&＃61;nust.top();
145 nust.pop();
146 switch(op)
147 {
148 case &＃39;&＃43;&＃39;:
149 cout<<"push "<
150 nust.push(l&＃43;r); break;
151 case &＃39;-&＃39;:
152 cout<<"push "<
153 nust.push(l-r); break;
154 case &＃39;*&＃39;:
155 cout<<"push "<
156 nust.push(l*r); break;
157 case &＃39;/&＃39;:
158 cout<<"push "<
159 nust.push(l/r); break;
160 case &＃39;%&＃39;:
161 cout<<"push "<<(int)l%(int)r<<endl;
162 nust.push((int)l%(int)r); break;
163 case &＃39;^&＃39;:
164 cout<<"push "<
165 nust.push(pow(l,r)); break;
166 default:
167 break;
168 }
169 }
170 return true;
171 }
172
173
174 /*push option when last option&＃39;s priority less than the current one*/
175 bool scan(char* exp)
176 {
177 int length&＃61;strlen(exp);
178 for(int i&＃61;0;i
179 {
180 if(isdigit(exp[i])){
181 int len;
182 bool ret&＃61;readfloat(exp&＃43;i,&len);
183 if(!ret){
184 return false;
185 }
186 i&＃43;&＃61;len;
187 }
188 if(i>&＃61;length)
189 break;
190 switch(exp[i])
191 {
192 case &＃39;(&＃39;:
193 chst.push(&＃39;(&＃39;);
194 break;
195 case &＃39;)&＃39;:
196 calc();
197 break;
198 case &＃39;&＃43;&＃39;:
199 if(getlastpriority()>&＃61;1)
200 {
201 calc();
202 }
203 chst.push(&＃39;&＃43;&＃39;);
204 cout<<"push &＃43;"<<endl;
205 break;
206 case &＃39;-&＃39;:
207 if(i&＃61;&＃61;0||exp[i-1]&＃61;&＃61;&＃39;(&＃39;)
208 {
209 if(exp[i&＃43;1]&＃61;&＃61;&＃39;(&＃39;){
210 nust.push(0);
211 chst.push(&＃39;-&＃39;);
212 cout<<"push 0"<<endl;
213 cout<<"push -"<<endl;
214 break;
215 }
216 int diglen;
217 bool ret&＃61;readfloat(exp&＃43;i,&diglen);
218 if(!ret){
219 cout<<"read float falied line:"<<__LINE__<<endl;
220 return false;
221 }
222 i&＃43;&＃61;diglen-1;
223 break;
224 }else{
225 if(getlastpriority()>&＃61;1)
226 calc();
227 chst.push(&＃39;-&＃39;);
228 cout<<"push -"<<endl;
229 break;
230 }
231 case &＃39;*&＃39;:
232 if(getlastpriority()>&＃61;2)
233 calc();
234 chst.push(&＃39;*&＃39;);
235 cout<<"push *"<<endl;
236 break;
237 case &＃39;/&＃39;:
238 if(getlastpriority()>&＃61;2)
239 calc();
240 chst.push(&＃39;/&＃39;);
241 cout<<"push /"<<endl;
242 break;
243 case &＃39;%&＃39;:
244 if(getlastpriority()>&＃61;2)
245 {
246 }else
247 calc();
248 chst.push(&＃39;%&＃39;);
249 cout<<"push %"<<endl;
250 break;
251 case &＃39;^&＃39;:
252 if(getlastpriority()>&＃61;3)
253 calc();
254 chst.push(&＃39;^&＃39;);
255 cout<<"push ^"<<endl;
256 break;
257 default:
258 cout<<"[1]error expression"<<endl;
259 break;
260 }
261 }
262 return true;
263 }
264 int main(int argc,char* argv[])
265 {
266 if(argc!&＃61;2){
267 cout<<"usage:calc express"<<endl;
268 }
269 char* exp&＃61;argv[1];
270 trimspace(exp);
271 bool suc&＃61;false;
272 suc&＃61;checkvalid(exp);
273 if(!suc)return 1;
274 suc&＃61;scan(exp);
275 if(!suc){
276 cout<<"scan failed"<<endl;
277 return 1;
278 }
279 suc&＃61;calc();
280 if(!suc){
281 cout<<"calc failed"<<endl;
282 return 1;
283 }
284 if(nust.size()!&＃61;1)
285 {
286 cout<<"[3]error expression number stack size&＃61;"<
287 return 1;
288 }
289 double rst&＃61;nust.top();
290 nust.pop();
291 cout<
292 return 0;
293 }
后来看了一下数据结构里的方法&＃xff0c;先把中缀表达式转成后缀表达式&＃xff0c;然后遍历表达式&＃xff0c;将数字入栈&＃xff0c;直接运算即可。省去了操作栈&＃xff0c;需要一个辅助数组保存操作符&＃xff0c;看上去数字需要用一个占位符代替。不过时间复杂度上是一样的。
京公网安备 11010802041100号