栈实现表达式求值——逆波兰法

正儿八经地学习数据结构有一个多月了，基本的线性表和vector、list、deque等等都浅浅地接触了一下。实验做了学生信息管理的顺序表实现和链表实现，二者各有利弊。但是通过学习数据结构和一些算法，我对那些厉害人物以及他们写的神奇的算法非常崇拜，胸中有一片火热尽管现实摧残得我不敢轻举妄动。

这不刚刚接触数据结构中的受限表——栈。栈是先进后出（FILO）的，这一特性赋予了该数据类型独特的个性。他只能从一端进行push压入和pop弹出操作。这恰好符号了我做表达式求值的要求。当然我想，既然学了，那就往深处挖挖，看看更深的地方人们所做的建树与探索。

按常理来说，计算机处理一个表达式，比如 a + b * c + (d* e + f)*g.需要按照运算符的优先级来先后计算子式。故采用 中缀转后缀法()转换成无二义性且可以顺序处理的表达式。源代码：

1. //2011-10-10 by bibodeng 
2. //对输入的表达式求值 
3. //主要思路：先将中缀表达式转换成后缀表达式 
4. //再对后缀表达式进行求值 
5. #include <iostream> 
6. #include <stack> 
7. #include <vector> 
8. #include <string> 
9. #include <sstream> 
10. using namespace std; 
11. typedef vector<string> STRVECTOR; 
12. void show_vector( STRVECTOR &v); 
13. double str2num(string s); 
14. string num2str(double i); 
15.  
16. void main() 
17. { 
18.     //声明一个栈，中缀到后缀时转换的符号储存在该栈中 
19.     stack <string,vector<string>> st1 ; 
20.     vector<string> input;//存放首次输入的中缀式子vector数组 
21.     vector<string> temp;//用于存放后缀式子 
22.      
23.     char ans; 
24.     string a; 
25. //******************************************** 
26.     do 
27.     { 
28.         system("cls"); 
29.         STRVECTOR::iterator ite; 
30.         cout<<"请输入式子的长度"<<endl; 
31.         int APPY_SIZE; 
32.         cin>>APPY_SIZE; 
33.          
34.         cout<<"请输入要进行运算的式子,式子的每个元素以空格隔开："<<endl; 
35.         for( int i=0;i<APPY_SIZE;i++) 
36.         { 
37.             cin>>a; 
38.             input.push_back(a); 
39.         } 
40.         cout<<"您输入的表达式是："<<endl; 
41.         show_vector(input); 
42.  
43.         //标示是否正在处理闭合括号 0 为不是，1为是, 2 为两重,依次类推 
44.         int flag=0; 
45.  
46. //*******************进行中缀到后缀的转换******************* 
47. //***********************开始循环************************** 
48.         for(unsigned int i=0;i<input.size();i++) 
49.         { 
50.             //对于input，若是操作符视情况压入栈中，若是操作数，直接送到temp 
51.             //低优先级的+ 和 - 
52.              
53.  
54.              //遇到低优先级的+ - 
55.                if("+"==input[i] || "-"==input[i]) 
56.                 {               
57.                     //没有比这个优先级更低的了，弹出直至空或者碰到( 
58.                     while(!st1.empty()) 
59.                     { 
60.                         if(st1.top()=="(") 
61.                             break; //若碰到（ 需要停止，因为只有碰到），（才被弹出 
62.  
63.                         temp.push_back(st1.top()); 
64.                         st1.pop(); 
65.                         //弹出一个 
66.                     } 
67.                     //所有都弹出后，再把+ 或 - 压入 
68.                     st1.push(input[i]); 
69.                 } 
70. //************************遇到乘除*************************** 
71. //只需考虑前面是否有+ - ，若有则入栈 
72.  
73.             else if("*"==input[i] || "/"==input[i]) 
74.             {    
75.                         if(!st1.empty())    //非空 
76.                         { 
77.                             //若遇到等级低的直接压入 
78.                             if(st1.top()=="+"||st1.top()=="-") 
79.                             st1.push(input[i]); 
80.                              
81.                             //若等级相同，则弹出后压入 
82.                             else if(st1.top()=="*"||st1.top()=="/") 
83.                                 { 
84.                                     while(!st1.empty()&&st1.top()!="(") 
85.                                     { 
86.                                         temp.push_back(st1.top()); 
87.                                         st1.pop();//弹出 
88.                                     } 
89.                                 }    
90.                             else if(st1.top()=="(") 
91.                                 st1.push(input[i]); 
92.                         }    
93.                         //碰到正在处理括号，则把符号压入 
94.                             if (st1.empty()) 
95.                                     st1.push(input[i]);      
96.  
97.                     } 
98. //************************遇到括号**************************** 
99.  
100.                 //优先级最高,直接压入 
101.                 else if(input[i]== "(") 
102.                     { 
103.                         st1.push(input[i]); 
104.                         flag++;  //提起标志，正在处理括号中 
105.                     } 
106.               //碰到右括号，与左括号相匹配，将中间的都弹出来 
107.                else if(input[i]== ")") 
108.                     { 
109.                         //弹出所有非（的运算符 
110.                         if(!st1.empty()) 
111.                         { 
112.                             while(st1.top()!="(")//非空且不为括号 
113.                             { 
114.                                 temp.push_back(st1.top()); 
115.                                 st1.pop(); 
116.                             } 
117.                             if(st1.top()=="(") 
118.                             { 
119.                                 st1.pop();//弹出且改变flag 
120.                                 flag--; 
121.                             }                    
122.                         } 
123.                     } 
124. //*********************************数值直接输出到temp************************ 
125.                 else if(input[i]!="+"&& input[i]!="-"&&input[i]!="*"&&input[i]!="/"&&input[i]!="("&&input[i]!=")") 
126.                 temp.push_back(input[i]); 
127. //************************转换循环结束************************* 
128.         } 
129.  
130.  
131.     //将所有符号弹空送到temp中 
132.     while(!st1.empty()) 
133.         { 
134.             temp.push_back(st1.top()); 
135.             st1.pop(); 
136.         } 
137.  
138.  
139.     //输出后缀式子 
140.     show_vector(temp); 
141. //********************************************************** 
142.     //用于最终计算的栈，可以弹出与压入 
143.     stack <string,vector<string>> final; 
144.     double x=0,y=0; //x,y 用于存储从栈中取出的数字
145.     double result=0; //result 用于存储产生的结果
146.  
147.         //进行式子的计算 
148.     for(unsigned int i=0;i<temp.size();i++) 
149.         { 
150.             //如果碰到是数字 
151.             if(temp[i]!="+"&& temp[i]!="-"&&temp[i]!="*"&&temp[i]!="/"&&temp[i]!="("&&temp[i]!=")") 
152.                 final.push(temp[i]);//将数字压入栈中 
153.  
154.             else //若是遇到运算符,则将两个数弹出来然后进行计算，将结果压入栈中 
155.             { 
156.                 if(!final.empty()) 
157.                 { 
158.                     x=str2num(final.top()); 
159.                     final.pop(); 
160.                     y=str2num(final.top()); 
161.                     final.pop(); 
162.                 } 
163.  
164.                     if(temp[i]== "+")result=x+y; 
165.                     else if(temp[i]== "-")result=y-x; 
166.                     else if(temp[i]== "*")result=x*y; 
167.                     else if (temp[i]=="/")result=y/x; 
168.                                          
169.                     string temp1; 
170.                     temp1=num2str(result); 
171.                      
172.                     final.push(temp1); 
173.             } 
174.  
175.         } 
176.     cout<<result<<endl; 
177.          
178. //******************************************************************** 
179.         cout<<"是否继续运算(Y/n) "<<endl; 
180.         cin>>ans; 
181.         input.clear(); 
182.         temp.clear(); 
183.     }while(ans=='y'||ans=='Y'); 
184. //******************************************** 
185. } 
186.  
187.  
188.  
189.  
190. //输出vector内容 
191. void show_vector( STRVECTOR &v) 
192. { 
193.     STRVECTOR::iterator ite; 
194.     for(ite=v.begin();ite!=v.end();ite++) 
195.         cout<<*ite; 
196.     cout<<endl; 
197. } 
198.  
199. //字符串转数字 
200. double str2num(string s) 
201.  {   
202.         double num; 
203.         stringstream ss(s); 
204.         ss>>num; 
205.         return num; 
206. } 
207. //数字转字符串 
208. string num2str(double i) 
209. { 
210.         stringstream ss; 
211.         ss<<i; 
212.         return ss.str(); 
213. } 

最关键的一步是中缀转后缀，分四种情况进行若是+ - ，优先级最低，只管将st1栈中的运算符弹出，直到遇到（或者st1为空为止。而遇到* / 等优先级较高的，又分若干种情况。不过基本上有三种：

1、遇到优先级低的，直接压入 

2、遇到同等优先级的弹出后压入

3、碰到（直接压入。

最后两种情况（“（”和“）”）比较好处理，遇到（优先级最高，直接压入。遇到“）”则将与左括号“（”之间的运算符弹出送到结果当中，最后将“（”弹出，不送到结果当中。

编码的时候遇到了相当多的问题，最后是用监视将各类bugs进行清扫。计算机里面的一些细微逻辑的确不容忽视，每一个语句都要经得起考验。

据了解，这个表达式求值居然是编译器工程的一个重要组成部分，这里涉及到许多符号平衡，以及众多匹配问题（如简单的if else）。编译器必须将语法正确的算法语言的语义正确地翻译成机器语言。然而这当中又有如此多常人难以考虑周全的细节，虽然作为一个编译器使用者根本不需要操心这类事情。但是从我们使用的算法语言的灵活性来看，这的确够让那些写编译器的人喝一壶了。因此，我由衷地崇拜那些能够写出庞大的编译器的人。像stallman这样的天才型***，到时候一定要看看他写的gcc里面的一些巧夺天工的代码……扯远了 ：P

最近觉得学了数据结构就能对现实中的很多东西能够刻画成模型并实现之，而且有些还非常的有趣。比如用栈走迷宫，用循环链表来解约瑟夫环。这些问题都非常地有趣，而且这其中不乏有好的算法，像大名鼎鼎的knuth写的约瑟夫环算法，相当地简练，效率也高，而一般人写出的算法一大串且效率低下，很不幸我自己也是一般人。在现实社会中，好的算法往往能够让人为之一振，而且让效率成倍增长。特别是在这个信息迅猛发展的时代，算法更是举足轻重。想想如此大的运算量，假如算法好，那么一次处理节省了多少时间与空间。眼下之时，正式学好算法的时代。

2011-10-11    by bibodeng