1 //Jeremy Wu {Wushuaiyi} CS1301   2 //#pragma comment(linker, "/STACK:16777216") //for c++ Compiler  3 #include <stdio.h>  4 #include <iostream>  5 #include <climits>  6 #include <cstring>  7 #include <stack>  8 #include <vector>  9 #include <map> 10 #include <algorithm> 11 #define ll long long 12 using namespace std; 13  14 const int INF = 0x3f3f3f3f; 15 const int MAXN = 8; 16 const int LEN = 10000; 17 int iCount; 18 string ee = "e";                //Epsilon express 19 string hh;                      //Handle 20 string now, cur;                //Solve Handle 21 vector <string> a, b;           //Stack and input array 22 map <string, int> Map;          //Map 23 map <int, string> Map_out;      //Map_out 24 int Real[MAXN][MAXN];           //Map_realation 25 void init(){ 26     iCount = 1; 27     a.clear(); 28     b.clear(); 29     Map.clear(); 30     Map_out.clear(); 31     memset(Real, 0, sizeof(Real)); 32     Map["E"] = 1, Map["E‘"] = 2, Map["T"] = 3, Map["T‘"] = 4, Map["F"] = 5; 33     Map["i"] = 6, Map["+"] = 7, Map["*"] = 8, Map["("] = 9, Map["#"] = 10; 34     Map_out[11] = "TE‘", Map_out[12] = "+TE‘", Map_out[13] = "e"; 35     Map_out[14] = "FT‘", Map_out[15] = "*FT‘", Map_out[16] = "(E)", Map_out[17] = "i"; 36     Real[Map["E"]][Map["i"]] = 11, Real[Map["E"]][Map["("]] = 11, 37     Real[Map["E‘"]][Map["+"]] = 12, Real[Map["E‘"]][Map[")"]] = 13, 38     Real[Map["E‘"]][Map["#"]] = 13, Real[Map["T"]][Map["i"]] = 14, 39     Real[Map["T"]][Map["("]] = 14, Real[Map["T‘"]][Map["+"]] = 13, 40     Real[Map["T‘"]][Map["*"]] = 15, Real[Map["T‘"]][Map[")"]] = 13, 41     Real[Map["T‘"]][Map["#"]] = 13, Real[Map["F"]][Map["i"]] = 17, 42     Real[Map["F"]][Map["("]] = 16; 43 } 44  45 void LookAhead(){ 46     for(int i = hh.size() - 1; i >= 0; --i){ 47         string tt; 48            if(hh[i] == ‘\‘‘ && hh[i - 1] == ‘E‘){ 49                b.push_back("E‘"); 50             --i; 51         } else if(hh[i] == ‘\‘‘ && hh[i - 1] == ‘T‘){ 52                b.push_back("T‘"); 53             --i; 54         } else{ 55                tt = hh[i]; 56             b.push_back(tt); 57         } 58     } 59 } 60  61 void print(){ 62     cout << "iCount = " << iCount << endl; 63     cout << "Stack : " ; 64     for(int i = 0; i < b.size(); ++i){ 65         cout << b[i]; 66     } 67     cout << endl << "Input : "; 68     for(int i = a.size()- 1; i >= 0; --i){ 69         cout << a[i]; 70     } 71     cout << endl << endl; 72 } 73  74 bool ErrorReport(){ 75     map<int, string>::iterator iter; 76     iter = Map_out.find(Real[Map[now]][Map[cur]]); 77     if(iter == Map_out.end()){ 78         cout << "Error" << endl; 79         return true; 80     } 81     return false; 82 } 83  84 int main(){ 85     int i; 86     char ch[LEN]; 87     init(); 88     cin >> ch; 89         a.push_back("#"); 90     for(i = strlen(ch); i >= 0; --i){ 91         string temp; 92         temp = ch[i]; 93         a.push_back(temp); 94     } 95     b.push_back("#"); 96     b.push_back("E"); 97     print(); 98     while(!a.empty()){ 99         ++iCount;100         cur = a.back();101         now = b.back();102         b.pop_back();103         if(cur == now){                                     //Reduce104             a.pop_back();105         } else{                                             //Shift106             if(ErrorReport()){107                 return 0;                                    //Exit Program108             }109             hh = Map_out[Real[Map[now]][Map[cur]]];110             if(hh == ee){111                 print();112                 if(b.back() == "#"){113                     cout << "Accecpt" << endl;              //Exit Program114                     return 0;115                 }116                 continue;117             }118             LookAhead();119         }120         print();121     }122     return 0;123 }