#ifndef LR_H
#define LR_H
#include <stack>
#include <string>
#include <map>
#include<algorithm>
#define NNUM 4
#define TNUM 8
#define PNUM 9
#define SNUM 30
using namespace std;
/*
*产生式
*(0) S -> E
*(1) E -> T
*(2) E -> E + T
*(3) E -> E - T
*(4) T -> F
*(5) T -> T * F 
*(6) T -> T / F
*(7) F -> ( E )
*(8) F -> i
*
*
*/

enum Action
{
    ACC=1,
    SHIFT,
    REDUCE
};
struct Production
{
    int num;
    char Left;
    string Right;
};
struct Node
{
    Action action;
    int destState;
    Production production;
};

char token;
char VN[] = {'S', 'E', 'T', 'F'};
char VT[] = { '+', '-', '*', '/','(',')', 'i','#'};
bool isVT(char);
bool isVN(char);
stack<char> symbolStack;
stack<int> stateStack;
map<int, map<char, Node>> LRMap;
Production production[PNUM];
char leftP[PNUM] = {'S','E','E','E','T','T','T','F','F'};
string rightP[PNUM]={"E","T","E+T","E-T","F","T*F","T/F","(E)","i"};
Node rNode [PNUM];
Node sNode [SNUM];
Node aNode; 
void nodeInit();
void mapInit();
void init();
string stackString(stack<char>& s);
string stackString(stack<int>& s);
bool existNode(int state, char symbol);
bool isVN(char c)
{
    for (int i = 0; i < NNUM; i++)
    {
        if (c == VN[i])
            return true;
    }
    return false;
}
bool isVT(char c)
{
    for (int i = 0; i < TNUM; i++)
    {
        if (c == VT[i])
            return true;
    }
    return false;
}
string stackString(stack<char>& s) 
{
    char c;
    stack<char> temp;
    string str;
    while(!s.empty())
    {
        str.push_back(s.top());
        //s.append(to_string(analyseStack.top()));
        temp.push(s.top());
        s.pop();
    }
    while(!temp.empty())
    {
        s.push(temp.top());
        temp.pop();
    }
    reverse(str.begin(),str.end());
    return str;
}
string stackString(stack<int>& s) 
{
    char c;
    stack<int> temp;
    string str;
    int *array;
    array = new int [s.size()];
    int i=0;
    while(!s.empty())
    {
    
        array[i++]=s.top();
        //str.append(to_string(s.top()));
        //s.append(to_string(analyseStack.top()));
        temp.push(s.top());
        s.pop();
    }
    while(!temp.empty())
    {
        s.push(temp.top());
        temp.pop();
    }
    while(i--)
    {
        str+=to_string(array[i]);
        str+=" ";
    }
    //reverse(str.begin(),str.end());
    delete [] array;
    return str;
}
bool existNode(int state, char symbol) 
{
    auto it = LRMap.find(state);
    if(it!=LRMap.end())
    {
        if(it->second.find(symbol)!=it->second.end())
            return true;
    } 
    return false;   
}
void init() 
{
    
   nodeInit();
   mapInit();
   symbolStack.push('#');
   stateStack.push(0);
}
void nodeInit() 
{
     for(int i=0;i<PNUM;i++)
    {
        production[i].num=i;
        production[i].Left = leftP[i];
        production[i].Right = rightP[i];
    }
   
    for(int i=0;i<PNUM;i++)
    {
        rNode[i].action = REDUCE;
        rNode[i].production = production[i];
    }
   
    for(int i=0;i<SNUM;i++)
    {
        sNode[i].action = SHIFT;
        sNode[i].destState = i;
    }
    
    aNode.action = ACC;
}

void mapInit() 
{
    LRMap[0]['('] = sNode[4];
    LRMap[0]['i'] = sNode[5];
    LRMap[0]['E'] = sNode[1];
    LRMap[0]['T'] = sNode[2];
    LRMap[0]['F'] = sNode[3];
    

    LRMap[1]['+'] = sNode[6];
    LRMap[1]['-'] = sNode[7];
    LRMap[1]['#'] = aNode;

    LRMap[2]['+'] = rNode[1];
    LRMap[2]['-'] = rNode[4];
    LRMap[2]['*'] = sNode[8];
    LRMap[2]['/'] = sNode[9];
    LRMap[2]['#'] = rNode[1];

    LRMap[3]['+'] = rNode[4];
    LRMap[3]['-'] = rNode[4];
    LRMap[3]['*'] = rNode[4];
    LRMap[3]['/'] = rNode[4];
    LRMap[3]['#'] = rNode[4];

    LRMap[4]['('] = sNode[13];
    LRMap[4]['i'] = sNode[14];
    LRMap[4]['E'] = sNode[10];
    LRMap[4]['T'] = sNode[11];
    LRMap[4]['F'] = sNode[12];

    LRMap[5]['+'] = rNode[8];
    LRMap[5]['-'] = rNode[8];
    LRMap[5]['*'] = rNode[8];
    LRMap[5]['/'] = rNode[8];
    LRMap[5]['#'] = rNode[8];

    LRMap[6]['('] = sNode[4];
    LRMap[6]['i'] = sNode[5];
    LRMap[6]['T'] = sNode[15];
    LRMap[6]['F'] = sNode[3];

    LRMap[7]['('] = sNode[4];
    LRMap[7]['i'] = sNode[5];
    LRMap[7]['T'] = sNode[16];
    LRMap[7]['F'] = sNode[3];

    LRMap[8]['('] = sNode[4];
    LRMap[8]['i'] = sNode[5];
    LRMap[8]['F'] = sNode[17];
    
    LRMap[9]['('] = sNode[4];
    LRMap[9]['i'] = sNode[5];
    LRMap[9]['F'] = sNode[18];

    LRMap[10]['+'] = sNode[19];
    LRMap[10]['-'] = sNode[20];
    LRMap[10][')'] = sNode[21];

    LRMap[11]['+'] = rNode[1];
    LRMap[11]['-'] = rNode[1];
    LRMap[11]['*'] = sNode[22];
    LRMap[11]['/'] = sNode[23];
    LRMap[11][')'] = rNode[1];

    LRMap[12]['+'] = rNode[4];
    LRMap[12]['-'] = rNode[4];
    LRMap[12]['*'] = rNode[4];
    LRMap[12]['/'] = rNode[4];
    LRMap[12][')'] = rNode[4];

    LRMap[13]['('] = sNode[13];
    LRMap[13]['i'] = sNode[14];
    LRMap[13]['E'] = sNode[24];
    LRMap[13]['T'] = sNode[11];
    LRMap[13]['F'] = sNode[12];

    LRMap[14]['+'] = rNode[8];
    LRMap[14]['-'] = rNode[8];
    LRMap[14]['*'] = rNode[8];
    LRMap[14]['/'] = rNode[8];
    LRMap[14][')'] = rNode[8];

    LRMap[15]['+'] = rNode[2];
    LRMap[15]['-'] = rNode[2];
    LRMap[15]['*'] = sNode[8];
    LRMap[15]['/'] = sNode[9];
    LRMap[15]['#'] = rNode[2];
    
    LRMap[16]['+'] = rNode[3];
    LRMap[16]['-'] = rNode[2];
    LRMap[16]['*'] = sNode[8];
    LRMap[16]['/'] = sNode[9];
    LRMap[16]['#'] = rNode[3];

    LRMap[17]['+'] = rNode[5];
    LRMap[17]['-'] = rNode[5];
    LRMap[17]['*'] = rNode[5];
    LRMap[17]['/'] = rNode[5];
    LRMap[17]['#'] = rNode[5];

    LRMap[18]['+'] = rNode[6];
    LRMap[18]['-'] = rNode[6];
    LRMap[18]['*'] = rNode[6];
    LRMap[18]['/'] = rNode[6];
    LRMap[18]['#'] = rNode[6];
    
    LRMap[19]['('] = sNode[13];
    LRMap[19]['i'] = sNode[14];
    LRMap[19]['T'] = sNode[25];
    LRMap[19]['F'] = sNode[12];

    LRMap[20]['('] = sNode[13];
    LRMap[20]['i'] = sNode[14];
    LRMap[20]['T'] = sNode[26];
    LRMap[20]['F'] = sNode[12];

    LRMap[21]['+'] = rNode[7];
    LRMap[21]['-'] = rNode[7];
    LRMap[21]['*'] = rNode[7];
    LRMap[21]['/'] = rNode[7];
    LRMap[21]['#'] = rNode[7];
    
    LRMap[22]['('] = sNode[13];
    LRMap[22]['i'] = sNode[14];
    LRMap[22]['F'] = sNode[27];

    LRMap[23]['('] = sNode[13];
    LRMap[23]['i'] = sNode[14];
    LRMap[23]['F'] = sNode[28];

    LRMap[24]['+'] = sNode[19];
    LRMap[24]['-'] = sNode[20];
    LRMap[24][')'] = sNode[29];

    LRMap[25]['+'] = rNode[2];
    LRMap[25]['-'] = rNode[2];
    LRMap[25]['*'] = sNode[22];
    LRMap[25]['/'] = sNode[23];
    LRMap[25][')'] = rNode[2];

    LRMap[26]['+'] = rNode[3];
    LRMap[26]['-'] = rNode[3];
    LRMap[26]['*'] = sNode[22];
    LRMap[26]['/'] = sNode[23];
    LRMap[26][')'] = rNode[3];

    LRMap[27]['+'] = rNode[5];
    LRMap[27]['-'] = rNode[5];
    LRMap[27]['*'] = rNode[5];
    LRMap[27]['/'] = rNode[5];
    LRMap[27][')'] = rNode[5];

    LRMap[28]['+'] = rNode[6];
    LRMap[28]['-'] = rNode[6];
    LRMap[28]['*'] = rNode[6];
    LRMap[28]['/'] = rNode[6];
    LRMap[28][')'] = rNode[6];

    LRMap[29]['+'] = rNode[7];
    LRMap[29]['-'] = rNode[7];
    LRMap[29]['*'] = rNode[7];
    LRMap[29]['/'] = rNode[7];
    LRMap[29][')'] = rNode[7];
}

#endif