C/C++带括号的四则运算

(1).首先从string读入表达式，取出每一个字符后装入deque容器coll1中（源码在后面）。

(2).从该容器取出每一个元素，利用栈将中缀表达式转换成后缀表达式（可参考：http://blog.csdn.net/anye3000/article/details/7939203），将后缀表达式装入容器coll3中。

(3).最后从coll3中取出元素逐一处理，既使用逆波兰式求值（如下图）。

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

C++源码

可编译并正常运行，此程序只支持一位数字运算，例如 3*(2+8)/5+6，有需要多位运算或者浮点型运算请自行修改，原理相同。

[cpp]  view plain copy

1. #include<stack>  
2. #include<iostream>  
3. #include<deque>  
4. #include<string>  
5. using namespace std;  
6.   
7. //判断是否为括号  
8. bool isPra(char c)   
9. {  
10.     if(c=='('||c==')')   
11.         return true;   
12.     else   
13.         return false;  
14. }  
15.   
16. //获得符号的优先性  
17. int getPri(char c)   
18. {  
19.     switch(c)   
20.     {  
21.     case '+':  
22.     case '-':  
23.         return 0;   //如果是加减，返回0  
24.         break;  
25.     case '*':  
26.     case '/':  
27.         return 1;   //如果是乘除，返回1  
28.         break;  
29.     case '(':  
30.     case ')':  
31.         return -1;  //注意，这里将括号设为最低优先级，因此括号不会被弹出，除非遇到右括号  
32.         break;  
33.      }  
34. }  
35.   
36. //判断符号的优先性  
37. void check(char c, stack<char>& coll2, deque<char>& coll3)   
38. {    
39.     if(coll2.empty())   
40.     {  
41.         coll2.push(c);  
42.         return;  
43.     }  
44.    
45.     if(isPra(c))   
46.     {  
47.         if(c=='(')   
48.             coll2.push(c);  
49.         else   
50.         {  
51.             //弹出所有元素直到遇到左括号  
52.             while(coll2.top()!='(')   
53.             {    
54.                 char ch = coll2.top();  
55.                 coll3.push_back(ch);  
56.                 coll2.pop();  
57.             }  
58.   
59.             //当遇到左括号时，弹出但不加入coll3(后缀表达式中）  
60.             coll2.pop();    
61.         }  
62.     }  
63.     else    //如果不是括号  
64.     {  
65.         //取出栈顶元素，与当前符号进行优先性比较  
66.         char sym = coll2.top();    
67.   
68.         //比较两符号的优先性  
69.         if(getPri(c)<=getPri(sym))    
70.         {  
71.             //如果c的优先性比栈顶符号小或等于，弹出栈顶元素  
72.             coll2.pop();  
73.             //并将其压入coll3（后缀表达式）中  
74.             coll3.push_back(sym);  
75.             //递归调用check,比较当前符号c与下一个栈顶符号的优先性  
76.             check(c,coll2,coll3);     
77.         }  
78.         else   
79.         {  
80.             //如果c比栈顶符号优先级大，那将c压入coll2(操作符栈）中  
81.             coll2.push(c);    
82.         }  
83.     }  
84. }  
85.   
86. //从coll中取出元素，分配元素到coll2和coll3中  
87. void allocate(deque<char>& coll1, stack<char>& coll2, deque<char>& coll3)   
88. {    
89.     while(!coll1.empty())   
90.     {  
91.         char c = coll1.front();  
92.         coll1.pop_front();  
93.   
94.         if(c>='0'&&c<='9')  
95.         {  
96.             coll3.push_back(c);  
97.         }  
98.         else   
99.         {  
100.             //调用check函数，针对不同情况作出不同操作  
101.             check(c,coll2,coll3);    
102.         }  
103.   
104.     }  
105.   
106.     //如果输入结束，将coll2的元素全部弹出，加入后缀表达式中  
107.     while(!coll2.empty())   
108.     {    
109.         char c = coll2.top();  
110.         coll3.push_back(c);  
111.         coll2.pop();  
112.     }  
113. }  
114.   
115. //计算后缀表达式  
116. void calculate(deque<char>& coll3, stack<int>& coll4)   
117. {    
118.     while(!coll3.empty())   
119.     {  
120.         char c = coll3.front();  
121.         coll3.pop_front();  
122.           
123.         //如果是操作数，压入栈中  
124.         if(c>='0'&&c<='9')   
125.         {  
126.             //减去'0'得出偏移值，即为真实数值（如果直接转换成int，结果不对，因为char 转换为int是其编码值，例如'1'的编码值为49  
127.             int op = c-'0';      
128.             coll4.push(op);       
129.         }  
130.         else     //如果是操作符，从栈中弹出元素进行计算  
131.         {   
132.             int op1 = coll4.top();  
133.             coll4.pop();  
134.             int op2 = coll4.top();  
135.             coll4.pop();  
136.             switch(c)   
137.             {  
138.             case '+':  
139.                 coll4.push(op2+op1);  
140.                 break;  
141.             case '-':  
142.                 coll4.push(op2-op1);  
143.                 break;  
144.             case '*':  
145.                 coll4.push(op2*op1);  
146.                 break;  
147.             case '/':  
148.                 coll4.push(op2/op1);  //注意是op2(op)op1而不是op1(op)op2  
149.                 break;  
150.             }  
151.         }  
152.     }  
153. }  
154.   
155.   
156. int main()  
157. {  
158.     deque<char> coll1;  //盛放中缀表达式  
159.     stack<char> coll2;  //盛放操作符  
160.     deque<char> coll3;    //盛放后缀表达式  
161.     stack<int>coll4;  //计算后缀表达式的辅助容器  
162.     string str;  
163.     cout<<"请输入表达式，按enter结束："<<endl;  
164.     cin>>str;  
165.     for(int i=0;i!=str.size();++i)   
166.     {  
167.         //逐一加入每个字符，这里使用deque因为deque在两端删除添加的速度最快  
168.         coll1.push_back(str[i]);    
169.     }  
170.    
171.     //从coll中取出元素，分配元素到coll2和coll3中  
172.     allocate(coll1,coll2,coll3);   
173.   
174.     //计算后缀表达式  
175.     calculate(coll3,coll4);    
176.     cout<<"计算结果为:"<<coll4.top()<<endl;  
177. }  

转载自： http://blog.csdn.net/mvpsendoh/article/details/6440835