首先说明我算法不好，跳槽的时候发现自己的基础薄弱而且不成体系，所以这段时间（大约3个月）我将用全部可以利用的时间把常用的数据结构、算法、C++对象模型、STL、泛型编程、设计模式整理一遍，然后梳理一下思路，做到对C++基础知识体系“巨细匪遗，秩序井然”。这个目标并没有看上去那么难，可以一试。首先要攻克的是常用的数据结构和算法，这样可以结合STL容器和算法一起学习。等整理完成后就列一个表，现在暂时没有详细的计划，先列一个粗略的计划：

　　

/*　基本结构：顺序表、链表、栈、队列、哈希表、平衡二叉树、红黑树、哈夫曼树、堆、B-树、　　结构应用：动态数组、循环队列、内存池、　　基本算法：二分查找、快排、基数排序、堆排序、归并排序、希尔排序、　　算法思想：回溯法、贪心法、分治法、动态规划、随机算法　　算法应用：算术表达式解析、迷宫寻路、N皇后、　　综合应用：脚本解释器（脚本与宿主程序交互、分支语句解析、循环语句解析、函数调用）、内存数据库（哈希索引、键值映射、增删改查、排序）*/

 

　　上面这些就够忙的了，如果有好的思想则继续补充。

　　用vim写了一上午，搞定了一个公式计算器，使用一个操作栈和一个数据栈，思路如下：

/*  1.格式化：对输入格式化处理为无空格字符串　　2.有效性检查：每个字符的合法性、括号匹配、运算符前后必须有操作数　　3.入栈扫描：字符为数字则视为有符号浮点数连续读入，然后push到数字栈；字符为操作符则判断上一个操作符的优先级，决定出栈计算或push到操作栈；　　4.出栈计算：操作符出栈直到遇到 ( 或栈空，操作数出栈计算，结果push回栈　　5.重复3、4直到表达式结束 */

 

下面是C++代码：

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 using namespace std; 8 9 stack
            
              nust; 10 stack
             
               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)='\0'; 18 } 19 20 bool checkvalid(char* exp) 21 { 22 char validchar[]={ 23 '(',')','+','-','*','/','%','^','.' 24 }; 25 int unmatch=0; 26 while(*exp!='\0') 27 { 28 bool valid=false; 29 for(unsigned int i=0;i
              
               1){ 82 cout<<"[6]error expression"<
               
                =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 +"<
                
                 =1)226 calc();227 chst.push('-');228 cout<<"push -"<
                 
                  =2)233 calc();234 chst.push('*');235 cout<<"push *"<
                  
                   =2)239 calc();240 chst.push('/');241 cout<<"push /"<
                   
                    =2)245 {246 }else247 calc();248 chst.push('%');249 cout<<"push %"<
                    
                     =3)253 calc();254 chst.push('^');255 cout<<"push ^"<
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      

　　后来看了一下数据结构里的方法，先把中缀表达式转成后缀表达式，然后遍历表达式，将数字入栈，直接运算即可。省去了操作栈，需要一个辅助数组保存操作符，看上去数字需要用一个占位符代替。不过时间复杂度上是一样的。