#include <vector>
#include <iostream>
#include <assert.h>

using namespace std;

#define MAX_ID_LENGTH 20

#define ID        1
#define DIGIT    2
#define EQUAL    3
#define PLUS    4
#define MUL        5
#define SUB        6

 

#define INPUT_CODE "var = 20 - 59"

char* KeyWord[] =
{
    "print",
    "status",
};

typedef struct _TOKEN_
{
    int         type;
    char        str[MAX_ID_LENGTH];
    int         value;
}Token;

typedef vector<Token> Tokens;
Tokens g_tokens;
int g_tokenIndex = 0;

int ParseStatement();
int ParseExpresstion();
int ParseTerm();
int ParseFactor();

void PushBackToken(int type, const char* str)
{
    Token token = { 0 };
    token.type = type;
    token.value = 0;
    strcpy(token.str, str);

    g_tokens.push_back(token);
}

bool IsEnd()
{
    return g_tokenIndex == g_tokens.size();
}

Token& GetNextToken()
{
    if ( g_tokenIndex <= g_tokens.size() - 1 )
    {
        if ( g_tokens[g_tokenIndex].type == ID )
        {
            for(int i = 0; i < g_tokens.size(); ++i)
            {
                if ( 0 == strcmp(g_tokens[g_tokenIndex].str, g_tokens[i].str) )
                {
                    g_tokenIndex++;
                    return g_tokens[i];
                }
            }
        }
        return g_tokens[g_tokenIndex++];
    }
    else
    {
        std::cout << "out of range" << std::endl;
        Token token = { 0 };
        return token;
    }
}

void UnGetNextToken()
{
    --g_tokenIndex;
}

void ShowAllTokens()
{
    for (int i = 0; i < g_tokens.size(); i++)
    {
        cout << g_tokens[i].str;
    }
}

 

 

int ParseStatement()
{
    Token& token = GetNextToken();

    if ( ID != token.type )
    {
        cout << "statement should begin with identifier" << endl;
    }

    Token tmpToken = GetNextToken();
    if ( EQUAL != tmpToken.type )
    {
        cout << "= lost" << endl;
    }

    token.value = ParseExpresstion();

    return token.value;
}

int ParseExpresstion()
{
    int sum = ParseTerm();
    while (true)
    {
        if ( IsEnd() )
        {
            return sum;
        }

        Token token = GetNextToken();
        if ( PLUS == token.type )
        {
            sum += ParseTerm();
        }
        else if ( SUB == token.type )
        {
            sum -= ParseTerm();
        }
        //todo: add "-"
        else
        {
            UnGetNextToken();
            break;
        }
    }

    return sum;
}

int ParseTerm()
{
    int mulResult = ParseFactor();
    while ( true )
    {
        if ( IsEnd() )
        {
            return mulResult;
        }
        Token token = GetNextToken();

        if ( MUL == token.type )
        {
            mulResult *= ParseFactor();
        }
        else
        {
            UnGetNextToken();
            break;
        }
        //todo add "/"
    }

    return mulResult;
}

int ParseFactor()
{
    Token token = GetNextToken();

    if ( ID == token.type )
    {
        return token.value;
        //cout << "statement should begin with identifier" << endl;
    }
    else if( DIGIT == token.type )
    {
        return atoi(token.str);
    }
    else
    {
        UnGetNextToken();
        //cout << "bug found" << endl;
    }

    return 1;
}

void TestPlus()
{
    g_tokenIndex = 0;
    g_tokens.clear();
    PushBackToken(ID,    "a");
    PushBackToken(EQUAL, "=");
    PushBackToken(DIGIT, "20");
    PushBackToken(PLUS, "+");
    PushBackToken(DIGIT, "30");
    PushBackToken(PLUS, "+");
    PushBackToken(DIGIT, "30");
    PushBackToken(SUB, "-");
    PushBackToken(DIGIT, "1");
    assert(79 == ParseStatement());
}

void TestPlusVar()
{
    PushBackToken(ID,    "b");
    PushBackToken(EQUAL, "=");
    PushBackToken(DIGIT, "20");
    PushBackToken(PLUS, "+");
    PushBackToken(DIGIT, "30");
    PushBackToken(PLUS, "+");
    PushBackToken(DIGIT, "30");
    PushBackToken(SUB, "-");
    PushBackToken(DIGIT, "1");
    PushBackToken(PLUS, "+");
    PushBackToken(ID, "a");

    assert(158 == ParseStatement());
}

void TestPlusVar1()
{
    PushBackToken(ID,    "c");
    PushBackToken(EQUAL, "=");
    PushBackToken(DIGIT, "20");
    PushBackToken(PLUS, "+");
    PushBackToken(ID, "a");
    ShowAllTokens();
    assert(99 == ParseStatement());
}

void TestPlusVar2()
{
    PushBackToken(ID,    "d");
    PushBackToken(EQUAL, "=");
    PushBackToken(ID, "a");
    PushBackToken(PLUS, "+");
    PushBackToken(ID, "b");
    ShowAllTokens();
    assert(158+79 == ParseStatement());
}

void TestMulVar2()
{
    PushBackToken(ID,    "e");
    PushBackToken(EQUAL, "=");
    PushBackToken(ID, "a");
    PushBackToken(MUL, "*");
    PushBackToken(ID, "b");
    ShowAllTokens();
    assert(158*79 == ParseStatement());
}

void TestSub()
{
    g_tokenIndex = 0;
    g_tokens.clear();
    PushBackToken(ID,    "var");
    PushBackToken(EQUAL, "=");
    PushBackToken(DIGIT, "20");
    PushBackToken(SUB, "-");
    PushBackToken(DIGIT, "30");
    assert(-10 == ParseStatement());
}

void TestMul()
{
    g_tokenIndex = 0;
    g_tokens.clear();
    PushBackToken(ID,    "var");
    PushBackToken(EQUAL, "=");
    PushBackToken(DIGIT, "20");
    PushBackToken(PLUS, "+");
    PushBackToken(DIGIT, "30");
    PushBackToken(MUL, "*");
    PushBackToken(DIGIT, "30");
    assert(920 == ParseStatement());
}

int main()
{
    TestPlus();    //测试加法
    TestPlusVar();
    TestPlusVar1();
    TestPlusVar2();
    TestMulVar2();
    //TestSub();    //测试减法
    //TestMul();    //测试乘法

    return 0;
}