Data Structure Stack: Infix to Postfix

efn阿克说

　　http://geeksquiz.com/stack-set-2-infix-to-postfix/



1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4 #include <queue>
5 #include <stack>
6 #include <string>
7 #include <fstream>
8 #include <map>
9 #include <set>
10 using namespace std;
11
12 bool isoprand(char x) {
13     return x >= 'A' && x <= 'Z' || x >= 'a' && x <= 'z';
14 }
15
16 int prec(char x) {
17     if (x == '+' || x == '-') return 1;
18     if (x == '*' || x == '/') return 2;
19     if (x == '^') return 3;
20     return -1;
21 }
22
23 int infixtopostfix(string s) {
24     string ans;
25     stack<char> T;
26     for (int i = 0; i < s.size(); i++) {
27         if (isoprand(s)) ans += s;
28         else if (s == '(') T.push(s);
29         else if (s == ')') {
30             while (!T.empty() && T.top() != '(') {
31                 ans += T.top();
32                 T.pop();
33             }
34             if (!T.empty() && T.top() != '(') return -1;
35             T.pop();
36         }
37         else {
38             while (!T.empty() && prec(s) <= prec(T.top())) {
39                 ans += T.top();
40                 T.pop();
41             }
42             T.push(s);
43         }
44     }
45     while (!T.empty()) {
46         ans += T.top();
47         T.pop();
48     }
49     cout << ans << endl;
50 }
51
52 int main() {
53     string s = "a+b*(c^d-e)^(f+g*h)-i";
54     infixtopostfix(s);
55     return 0;
56 }