使用栈将中缀表达式转换为后缀表达式

 1 void inToPostfix()
 2 {
 3 stack<char> s;
 4 char token;
 5 cin>> token;
 6 while (token != ’=’)
 7 {
 8 if (token >= ’a’ && token <= ’z’)
 9 cout<<token<<" ";
10 else
11 switch (token)
12 {
13 case ’)’ : while(!s.empty() && s.top() != ’(’)
14 { cout<<s.top()<<" "; s.pop();}
15 s.pop(); break;
16 case ’(’ : s.push(token); break;
17 case ’^’ : while(!s.empty() && !(s.top()== ’^’ ||
18 s.top() == ’(’))
19 {cout<<s.top(); s.pop();}
20 s.push(token); break;
21 case ’*’ :
22 case ’/’ : while(!s.empty() && s.top() != ’+’
23 && s.top() != ‘-‘ && s.top() != ‘(‘)
24 {cout<<s.top(); s.pop();}
25 s.push(token); break;
26 case ‘+’ :
27 case ‘-‘ : while(!s.empty() && s.top() != ‘(‘ )
28 {cout<<s.top()<<“ ”; s.pop();}
29 s.push(token); break;
30 }
31 cin>> token;
32 }
33 while (!s.empty())
34 {cout<<s.top()<<“ ” ; s.pop();}
35 cout<<" = 
";
36 }

还有将后缀转为中缀：

 1 string postToInfix()
 2 {
 3 stack<string> s;
 4 string token;
 5 string a, b;
 6 cin>>token;
 7 while (token[0] != ’=’)
 8 {
 9 if (token[0] >= ’a’ && token[0] <= ’z’)
10 s.push(token);
11 else
12 switch (token[0])
13 {
14 case ’+’ : a = s.top(); s.pop() ; b = s.top(); s.pop();
15 s.push("("+ a+" + " + b+")"); break;
16 case ’-’ : a = s.top(); s.pop() ; b = s.top(); s.pop();
17 s.push("("+a+" - "+ b+")"); break;
18 case ’*’ : a = s.top(); s.pop() ; b = s.top(); s.pop();
19 s.push("("+a+" * "+ b+")"); break;
20 case ’/’ : a = s.top(); s.pop() ; b = s.top(); s.pop();
21 s.push("("+a+" / " + b+")"); break;
22 case ’^’ : a = s.top(); s.pop() ; b = s.top(); s.pop();
23 s.push("("+a+" ^ " + b+")"); break;
24 }
25 cin>> token;
26 }
27 return s.top();
28 }

栈的其他应用：计算后缀表达式的值

 1 double evalPostFix()
 2 {
 3     stack<double> s;
 4     string token;
 5     double a, b, result;
 6     cin >> token;
 7     while (token[0] != '=')
 8     {
 9         result = atof(token.c_str());
10         if (result != 0.0)    
11             s.push(result);
12         else if (token == "0.0")
13             s.push(result);
14         else 
15             switch (token[0])
16         {
17             case'+' :
18                 a = s.top(); s.pop();
19                 b = s.top(); s.pop();
20                 s.push(a + b);
21                 break;
22             case'-':
23                 a = s.top(); s.pop();
24                 b = s.top(); s.pop();
25                 s.push(a - b);
26                 break;
27             case'*':
28                 a = s.top(); s.pop();
29                 b = s.top(); s.pop();
30                 s.push(a * b);
31                 break;
32             case'/':
33                 a = s.top(); s.pop();
34                 b = s.top(); s.pop();
35                 s.push(a / b);
36                 break;
37             case'^':
38                 a = s.top(); s.pop();
39                 b = s.top(); s.pop();
40                 s.push(exp(a*log(b)));
41                 break;
42         }
43         cin >> token;
44     }
45     return s.top();
46 }