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