Data Structure Stack: Infix to Postfix
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 }
页:
[1]