////////////////////////////////////////////////////////////////////////////////
//                                                                             /
// 2012-2019 (c) Baical                                                        /
//                                                                             /
// This library is free software; you can redistribute it and/or               /
// modify it under the terms of the GNU Lesser General Public                  /
// License as published by the Free Software Foundation; either                /
// version 3.0 of the License, or (at your option) any later version.          /
//                                                                             /
// This library is distributed in the hope that it will be useful,             /
// but WITHOUT ANY WARRANTY; without even the implied warranty of              /
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU           /
// Lesser General Public License for more details.                             /
//                                                                             /
// You should have received a copy of the GNU Lesser General Public            /
// License along with this library.                                            /
//                                                                             /
////////////////////////////////////////////////////////////////////////////////
#ifndef EXPRESSION_H
#define EXPRESSION_H

////////////////////////////////////////////////////////////////////////////////
//Class CExpression provides functionality to compute math & logic expressions /
//Next functionality are available:                                            /
// - operations under constants (int64, decimal & hex representation)          /
// - operations under variables                                                /
// - unary operations - [~ ! + -]                                              /
// - binary math operations - [* / % - + >> << & ^ |]                          /
// - binary logical operations - [&& || > >= < <= != ==]                       /
////////////////////////////////////////////////////////////////////////////////
//Usage example:                                                               /
// CExpression l_cExpression;                                                  /
// if (FALSE != l_cExpression.Set(L"10 + 20 > 29"))                            /
// {                                                                           /
//     wprintf(L"Result = %lld\n", l_cExpression->Compute());                  /
// }                                                                           /
//                                                                             /
//If you want to use variables:                                                /
// if (FALSE != l_cExpression.Set(L"10 + 20 > X"))                             /
// {                                                                           /
//     l_cExpression.Get_Variable(0)->m_llValue = 30;                          /
//     wprintf(L"Result = %lld\n", l_cExpression->Compute());                  /
// }                                                                           /
////////////////////////////////////////////////////////////////////////////////


#include "GTypes.h"
#include "AList.h"
#include "Length.h"
#include "PString.h"

////////////////////////////////////////////////////////////////////////////////
//SETs definition for parser
#define TOKEN_VARIABLE        TM("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
#define TOKEN_DIGIT           TM("0123456789")
#define TOKEN_DIGIT_HEX       TM("xABCDEF")
#define TOKEN_UNARY           TM("~!+-")
#define TOKEN_OPERATOR        TM("~!*/%-+<>=&^|")
#define TOKEN_OPERATOR_UNARY  TM("+-~!")
#define TOKEN_OPERATOR_BINARY TM("*/%-+<>=!&^|")
#define TOKEN_PARENTHESES_O   TM('(')
#define TOKEN_PARENTHESES_C   TM(')')

#define SAFE_DELETE(pX) if (pX) { delete pX; pX = NULL; }
#define SAFE_DELETE_LIST(pX, bFree) if (pX) { pX->Clear(bFree); delete pX; pX = NULL; }

#define OP_MAX_LENGTH                                                        (3)

////////////////////////////////////////////////////////////////////////////////
//CExpression
class CExpression
{
public:
    ////////////////////////////////////////////////////////////////////////////
    //variable
    struct sVariable
    {
        XCHAR  *m_pName;
        tINT64  m_llValue;

        sVariable(const XCHAR *i_pName)
            : m_pName(NULL)
            , m_llValue(0)
        {
            m_pName = PStrDub(i_pName);
        }

        ~sVariable()
        {
            if (m_pName)
            {
                PStrFreeDub(m_pName);
                m_pName = NULL;
            }
        }
    }; //sVariable

//protected:
    ////////////////////////////////////////////////////////////////////////////
    //operators


    struct sOp
    {
        XCHAR m_pText[OP_MAX_LENGTH];
        int   m_iPriority;

        enum eClass
        {
            CLASS_POSTFIX,
            CLASS_UNARY  ,
            CLASS_BINARY ,
        } m_eClass;

        enum eType
        {
            TYPE_BITWISE_NOT            = 0,
            TYPE_LOGICAL_NOT               ,
            TYPE_UNARY_MINUS               ,
            TYPE_UNARY_PLUS                ,
            TYPE_MULTIPLICATION            ,
            TYPE_DIVISION                  ,
            TYPE_MODULO                    ,
            TYPE_PLUS                      ,
            TYPE_MINUS                     ,
            TYPE_BITWISE_LEFT_SHIFT        ,
            TYPE_BITWISE_RIGHT_SHIFT       ,
            TYPE_GREATER                   ,
            TYPE_GREATER_OR_EQUAL          ,
            TYPE_LESS                      ,
            TYPE_LESS_OR_EQUAL             ,
            TYPE_EQUAL                     ,
            TYPE_NOT_EQUAL                 ,
            TYPE_BITWISE_AND               ,
            TYPE_BITWISE_XOR               ,
            TYPE_BITWISE_OR                ,
            TYPE_LOGICAL_AND               ,
            TYPE_LOGICAL_OR                ,

            TYPES_COUNT
        } m_eType;
    };

    ////////////////////////////////////////////////////////////////////////////
    //token structures
    enum eToken_Type
    {
        ETYPE_UNKNOWN         = 0x0000,
        ETYPE_PARENTHESES_O   = 0x0001,
        ETYPE_PARENTHESES_C   = 0x0002,
        ETYPE_VARIABLE        = 0x0004,
        ETYPE_CONST           = 0x0008,
        ETYPE_UNARY_OPERATOR  = 0x0010,
        ETYPE_BINARY_OPERATOR = 0x0020,
    };

    struct sToken
    {
        const XCHAR *m_pText;
        size_t       m_szOffset; //offset in source expression
        eToken_Type  m_eType;

        sToken(const XCHAR *i_pText, size_t i_szOffset, eToken_Type i_eType)
        {
            m_pText    = i_pText;
            m_szOffset = i_szOffset;
            m_eType    = i_eType;
        }
    };


    ////////////////////////////////////////////////////////////////////////////
    //sNode
    struct sNode
    {
        enum eType
        {
            TYPE_OPERATION     ,
            TYPE_GROUP         ,
            TYPE_LEAF_CONST    ,
            TYPE_LEAF_VARIABLE ,
        } m_eType;

        sNode *m_pPrev;

        struct sOpB
        {
            const sOp          *m_pOpBinary;
            sNode              *m_pLeft;
            sNode              *m_pRight;
        };

        struct sGr
        {
            CBList<const sOp*> *m_pOpUnary;
            sNode              *m_pSub;
        };

        struct sArg
        {
            CBList<const sOp*> *m_pOpUnary;
            tINT64              m_llValue;
            sVariable          *m_pVariable;
        };

        union
        {
            sOpB m_sOp;
            sGr m_sGr;
            sArg m_sArg;
        };

        ////////////////////////////////////////////////////////////////////////
        //sNode()
        sNode(sNode::eType i_eType)
        {
            m_eType  = i_eType;
            m_pPrev  = NULL;
            memset(&m_sOp,   0, sizeof(m_sOp));
            memset(&m_sGr,   0, sizeof(m_sGr));
            memset(&m_sArg,  0, sizeof(m_sArg));

        }//sNode()

        ////////////////////////////////////////////////////////////////////////
        //~sNode()
        ~sNode()
        {
            if (TYPE_OPERATION == m_eType)
            {
                SAFE_DELETE(m_sOp.m_pLeft);
                SAFE_DELETE(m_sOp.m_pRight);
                m_sOp.m_pOpBinary = NULL;
            }
            else if (TYPE_GROUP == m_eType)
            {
                //m_sGr.m_pOpUnary->Clear(TRUE); //contains links to static data
                SAFE_DELETE_LIST(m_sGr.m_pOpUnary, FALSE);
                SAFE_DELETE(m_sGr.m_pSub);
            }
            else if (    (TYPE_LEAF_CONST == m_eType)
                      || (TYPE_LEAF_VARIABLE == m_eType)
                    )
            {
                //m_sArg.m_pOpUnary->Clear(TRUE); //contains links to static data
                SAFE_DELETE_LIST(m_sArg.m_pOpUnary, FALSE);
                m_sArg.m_pVariable = NULL;
            }
        }//~sNode()
    };//sNode

    ////////////////////////////////////////////////////////////////////////////
    //class variables
    XCHAR             *m_pBuffer;
    size_t             m_szBuffer; //in bytes
    CBList<sToken*>    m_cTokens;
    const XCHAR       *m_pError_Text;
    size_t             m_szError_Offset;
    CBList<sVariable*> m_cVariables;
    sNode             *m_pAST_Root;
    sOp                m_pOperators[sOp::TYPES_COUNT];

public: 
    ////////////////////////////////////////////////////////////////////////////
    //CExpression
    CExpression()
        : m_pBuffer(NULL)
        , m_szBuffer(0)
        , m_pError_Text(NULL)
        , m_szError_Offset(0)
        , m_pAST_Root(NULL)
    {
        const sOp l_pOperators[] = 
        {
            {TM("~") , 15, sOp::CLASS_UNARY , sOp::TYPE_BITWISE_NOT        },
            {TM("!") , 15, sOp::CLASS_UNARY , sOp::TYPE_LOGICAL_NOT        },
            {TM("+") , 15, sOp::CLASS_UNARY , sOp::TYPE_UNARY_PLUS         },
            {TM("-") , 15, sOp::CLASS_UNARY , sOp::TYPE_UNARY_MINUS        },
            {TM("*") , 13, sOp::CLASS_BINARY, sOp::TYPE_MULTIPLICATION     },
            {TM("/") , 13, sOp::CLASS_BINARY, sOp::TYPE_DIVISION           },
            {TM("%") , 13, sOp::CLASS_BINARY, sOp::TYPE_MODULO             },
            {TM("-") , 12, sOp::CLASS_BINARY, sOp::TYPE_MINUS              },
            {TM("+") , 12, sOp::CLASS_BINARY, sOp::TYPE_PLUS               },
            {TM("<<"), 11, sOp::CLASS_BINARY, sOp::TYPE_BITWISE_LEFT_SHIFT },
            {TM(">>"), 11, sOp::CLASS_BINARY, sOp::TYPE_BITWISE_RIGHT_SHIFT},
            {TM(">") , 10, sOp::CLASS_BINARY, sOp::TYPE_GREATER            },
            {TM("<") , 10, sOp::CLASS_BINARY, sOp::TYPE_LESS               },
            {TM(">="), 10, sOp::CLASS_BINARY, sOp::TYPE_GREATER_OR_EQUAL   },
            {TM("<="), 10, sOp::CLASS_BINARY, sOp::TYPE_LESS_OR_EQUAL      },
            {TM("=="),  9, sOp::CLASS_BINARY, sOp::TYPE_EQUAL              },
            {TM("!="),  9, sOp::CLASS_BINARY, sOp::TYPE_NOT_EQUAL          },
            {TM("&") ,  8, sOp::CLASS_BINARY, sOp::TYPE_BITWISE_AND        },
            {TM("^") ,  7, sOp::CLASS_BINARY, sOp::TYPE_BITWISE_XOR        },
            {TM("|") ,  6, sOp::CLASS_BINARY, sOp::TYPE_BITWISE_OR         },
            {TM("&&"),  5, sOp::CLASS_BINARY, sOp::TYPE_LOGICAL_AND        },
            {TM("||"),  4, sOp::CLASS_BINARY, sOp::TYPE_LOGICAL_OR         },
        };                               

        if (sizeof(m_pOperators) == sizeof(l_pOperators))
        {
            memcpy(m_pOperators, l_pOperators, sizeof(m_pOperators));
        }
        else
        {
            memset(m_pOperators, 0, sizeof(m_pOperators));
        }
    }//CExpression

    ////////////////////////////////////////////////////////////////////////////
    //~CExpression
    ~CExpression()
    {
        SAFE_DELETE(m_pAST_Root);
        m_cTokens.Clear(TRUE);
        m_cVariables.Clear(TRUE);

        if (m_pBuffer)
        {
            free(m_pBuffer);
            m_pBuffer = NULL;
        }
    }//~CExpression

    ////////////////////////////////////////////////////////////////////////////
    //Set
    tBOOL Set(const XCHAR *i_pExpression)
    {
        pAList_Cell l_pEl_Token = NULL;

        if (NULL == i_pExpression)
        {
            return FALSE;
        }

        m_cTokens.Clear(TRUE);
        m_cVariables.Clear(TRUE);

        m_pError_Text    = NULL;
        m_szError_Offset = 0;

        ////////////////////////////////////////////////////////////////////////
        //create buffer to store tokens <toke0><\0><toke1><\0> .. <tokeN><\0>
        //multiply length by 2 to be sure that every character we can follow by 0
        size_t l_szBuffer = (PStrLen(i_pExpression) + 1) * 2 * sizeof(XCHAR);

        if (l_szBuffer > m_szBuffer)
        {
            if (m_pBuffer)
            {
                free(m_pBuffer);
                m_pBuffer = NULL;
            }

            m_pBuffer  = (XCHAR*) malloc(l_szBuffer);
            m_szBuffer = l_szBuffer;
        }

        if (NULL == m_pBuffer)
        {
            return FALSE;
        }

        ////////////////////////////////////////////////////////////////////////
        //run lexical scanner, it will create list of tokens
        if (FALSE == Lexical_Scan(i_pExpression))
        {
            return FALSE;
        }

        ////////////////////////////////////////////////////////////////////////
        //run grammatical scanner, it will check grammar 
        if (FALSE == Grammatical_Scan())
        {
            return FALSE;
        }


        ////////////////////////////////////////////////////////////////////////
        //build AST
        SAFE_DELETE(m_pAST_Root);
        m_pAST_Root = new sNode(sNode::TYPE_GROUP);

        return AST_Build(m_pAST_Root, l_pEl_Token);
    }//Set

    //Function to get variables

    ////////////////////////////////////////////////////////////////////////////
    //Compute
    tINT64 Compute()
    {
        return Compute_Binary(m_pAST_Root);
    }//Compute

    ////////////////////////////////////////////////////////////////////////////
    //Get_Variables_Count
    tUINT32 Get_Variables_Count()
    {
        return m_cVariables.Count();
    }//Get_Variables_Count

    ////////////////////////////////////////////////////////////////////////////
    //Get_Variable_Name
    sVariable *Get_Variable(tUINT32 i_dwIdx)
    {
        return m_cVariables[i_dwIdx];
    }//Get_Variable_Name

    ////////////////////////////////////////////////////////////////////////////
    //Get_Error
    const XCHAR *Get_Error(size_t *o_pExpression_Offset)
    {
        if (o_pExpression_Offset)
        {
            *o_pExpression_Offset = m_szError_Offset;
        }

        return m_pError_Text;        
    }//Get_Error

private:
    ////////////////////////////////////////////////////////////////////////////
    //Lexical_Scan
    tBOOL Lexical_Scan(const XCHAR *i_pExpression)
    {
        const XCHAR *l_pExToken = i_pExpression;
        XCHAR       *l_pBuToken = m_pBuffer;
        sToken      *l_pPrToken = NULL;
        tBOOL        l_bReturn  = TRUE;

        memset(m_pBuffer, 0, m_szBuffer);  

        while (*l_pExToken)
        {
            if (PStrChr(TOKEN_VARIABLE, *l_pExToken))
            {
                l_pPrToken = new sToken(l_pBuToken, l_pExToken - i_pExpression, ETYPE_VARIABLE);
                m_cTokens.Add_After(m_cTokens.Get_Last(), l_pPrToken);

                while (    (PStrChr(TOKEN_VARIABLE, *l_pExToken))
                        || (PStrChr(TOKEN_DIGIT, *l_pExToken))
                      )
                {
                    *l_pBuToken = *l_pExToken;
                    l_pBuToken ++;
                    l_pExToken ++;

                    if (0 == *l_pExToken)
                    {
                        break;
                    }
                }

                l_pBuToken ++; //skip 0
            }
            else if (PStrChr(TOKEN_DIGIT, *l_pExToken))
            {
                l_pPrToken = new sToken(l_pBuToken, l_pExToken - i_pExpression, ETYPE_CONST);
                m_cTokens.Add_After(m_cTokens.Get_Last(), l_pPrToken);

                while (    (PStrChr(TOKEN_DIGIT, *l_pExToken))
                        || (PStrChr(TOKEN_DIGIT_HEX, *l_pExToken))
                      )
                {
                    *l_pBuToken = *l_pExToken;
                    l_pBuToken ++;
                    l_pExToken ++;

                    if (0 == *l_pExToken)
                    {
                        break;
                    }
                }

                l_pBuToken ++; //skip 0
            }
            else if (PStrChr(TOKEN_OPERATOR, *l_pExToken))
            {
                //if we expect to get binary operators, it follows after "const",
                //"var" or ")"
                //Unary operator follows after "bin op", "unary op", "("
                if (    (l_pPrToken)
                     && (    (ETYPE_CONST == l_pPrToken->m_eType)
                          || (ETYPE_VARIABLE == l_pPrToken->m_eType)
                          || (ETYPE_PARENTHESES_C == l_pPrToken->m_eType)
                        )
                   )
                {
                    l_pPrToken = new sToken(l_pBuToken, l_pExToken - i_pExpression, ETYPE_BINARY_OPERATOR);
                    m_cTokens.Add_After(m_cTokens.Get_Last(), l_pPrToken);

                    while (PStrChr(TOKEN_OPERATOR_BINARY, *l_pExToken))
                    {
                        *l_pBuToken = *l_pExToken;
                        l_pBuToken ++;
                        l_pExToken ++;

                        if (0 == *l_pExToken)
                        {
                            break;
                        }
                    }
                }
                else
                {
                    l_pPrToken = new sToken(l_pBuToken, l_pExToken - i_pExpression, ETYPE_UNARY_OPERATOR);
                    m_cTokens.Add_After(m_cTokens.Get_Last(), l_pPrToken);
                    *l_pBuToken = *l_pExToken;
                    l_pBuToken ++;
                    l_pExToken ++;
                }

                l_pBuToken ++;  //skip 0
            }
            else if (TOKEN_PARENTHESES_O == *l_pExToken)
            {
                l_pPrToken = new sToken(l_pBuToken, l_pExToken - i_pExpression, ETYPE_PARENTHESES_O);
                m_cTokens.Add_After(m_cTokens.Get_Last(), l_pPrToken);
                *l_pBuToken = *l_pExToken;
                l_pBuToken += 2;
                l_pExToken ++;
            }
            else if (TOKEN_PARENTHESES_C == *l_pExToken)
            {
                l_pPrToken = new sToken(l_pBuToken, l_pExToken - i_pExpression, ETYPE_PARENTHESES_C);
                m_cTokens.Add_After(m_cTokens.Get_Last(), l_pPrToken);
                *l_pBuToken = *l_pExToken;
                l_pBuToken += 2; //skip 0
                l_pExToken ++;
            }
            else if (    (32 == *l_pExToken) //space
                      || (9  == *l_pExToken) //tab
                      || (10 == *l_pExToken) //0xA new
                      || (13 == *l_pExToken) //0xD line
                    )
            {
                l_pExToken++;
            }
            else
            {
                m_pError_Text    = TM("Error, unknown token !");
                m_szError_Offset = l_pExToken - i_pExpression;

                l_bReturn = FALSE;
            }
        }//while (*l_pToken)

        return l_bReturn;
    }//Lexical_Scan


    ////////////////////////////////////////////////////////////////////////////
    //Grammatical_Scan
    tBOOL Grammatical_Scan()
    {
        pAList_Cell l_pEl          = NULL;
        tBOOL       l_bReturn      = TRUE;
        int         l_iParentheses = 0; 
        sToken     *l_pToken       = NULL;
        eToken_Type l_eExptected   = (eToken_Type)(   ETYPE_PARENTHESES_O
                                                    | ETYPE_VARIABLE
                                                    | ETYPE_CONST
                                                    | ETYPE_UNARY_OPERATOR
                                                  );

        ////////////////////////////////////////////////////////////////////////
        //scan tokens sequence
        l_pEl = NULL;
        while ((l_pEl = m_cTokens.Get_Next(l_pEl)))
        {
            l_pToken = m_cTokens.Get_Data(l_pEl);
            if (    (l_pToken)
                 && (l_eExptected & l_pToken->m_eType)
               )
            {
                switch (l_pToken->m_eType)
                {
                    case ETYPE_PARENTHESES_O:
                    {
                        l_iParentheses ++;
                        l_eExptected = (eToken_Type)(   ETYPE_PARENTHESES_O
                                                      | ETYPE_VARIABLE
                                                      | ETYPE_CONST
                                                      | ETYPE_UNARY_OPERATOR
                                                    );
                        break;
                    }
                    case ETYPE_PARENTHESES_C:
                    {
                        l_iParentheses --;
                        l_eExptected = (eToken_Type)(   ETYPE_PARENTHESES_C
                                                      | ETYPE_BINARY_OPERATOR
                                                    );
                        break;
                    }
                    case ETYPE_VARIABLE:
                    case ETYPE_CONST:
                    {
                        l_eExptected = (eToken_Type)(   ETYPE_PARENTHESES_C
                                                      | ETYPE_BINARY_OPERATOR
                                                    );
                        break;
                    }
                    case ETYPE_UNARY_OPERATOR:
                    {
                        l_eExptected = (eToken_Type)(   ETYPE_PARENTHESES_O
                                                      | ETYPE_UNARY_OPERATOR
                                                      | ETYPE_VARIABLE
                                                      | ETYPE_CONST
                                                    );
                        break;
                    }
                    case ETYPE_BINARY_OPERATOR:
                    {
                        l_eExptected = (eToken_Type)(   ETYPE_PARENTHESES_O
                                                      | ETYPE_UNARY_OPERATOR
                                                      | ETYPE_VARIABLE
                                                      | ETYPE_CONST
                                                    );
                        break;
                    }
                    case ETYPE_UNKNOWN:
                    {
                        //shut up paranoic GCC
                        break;
                    }
                };
            }
            else
            {
                m_pError_Text    = TM("Error, unexpected token !");
                m_szError_Offset = l_pToken ? l_pToken->m_szOffset : 0;
                l_bReturn        = FALSE;
                goto l_lblExit;
            }
        }//while (l_pEl = m_cTokens.Get_Next(l_pEl))

        ////////////////////////////////////////////////////////////////////////
        //check type of the last token
        if (    (l_pToken)
             && (ETYPE_PARENTHESES_C != l_pToken->m_eType)
             && (ETYPE_VARIABLE != l_pToken->m_eType)
             && (ETYPE_CONST != l_pToken->m_eType)
           )
        {
            m_pError_Text    = TM("Error, unexpected token !");
            m_szError_Offset = l_pToken->m_szOffset;
            l_bReturn        = FALSE;
            goto l_lblExit;
        }

        ////////////////////////////////////////////////////////////////////////
        //check Parentheses
        if (0 != l_iParentheses)
        {
            m_pError_Text    = TM("Error, parentheses are not paired!");
            m_szError_Offset = 0;
            l_bReturn        = FALSE;
            goto l_lblExit;
        }

        ////////////////////////////////////////////////////////////////////////
        //scan binary operators
        l_pEl = NULL;
        while ((l_pEl = m_cTokens.Get_Next(l_pEl)))
        {
            sToken *l_pToken = m_cTokens.Get_Data(l_pEl);
            if (    (l_pToken)
                 && (    (ETYPE_BINARY_OPERATOR == l_pToken->m_eType)
                      || (ETYPE_UNARY_OPERATOR  == l_pToken->m_eType)
                    )
               )
            {
                l_bReturn = FALSE;
                for (tUINT32 l_dwI = 0; l_dwI < LENGTH(m_pOperators); l_dwI++)
                {
                    if (    (    (    (sOp::CLASS_UNARY == m_pOperators[l_dwI].m_eClass)
                                   && (ETYPE_UNARY_OPERATOR  == l_pToken->m_eType)
                                 )
                              || (    (sOp::CLASS_BINARY == m_pOperators[l_dwI].m_eClass)
                                   && (ETYPE_BINARY_OPERATOR  == l_pToken->m_eType)
                                 )
                            )
                         && (0 == PStrCmp(m_pOperators[l_dwI].m_pText, l_pToken->m_pText))
                       )
                    {
                        l_bReturn = TRUE;
                        break;
                    }
                }

                if (FALSE == l_bReturn)
                {
                    m_pError_Text    = TM("Error, unknown operator");
                    m_szError_Offset = l_pToken->m_szOffset;
                    break;
                }
            }
        }//while (l_pEl = m_cTokens.Get_Next(l_pEl))

        if (FALSE == l_bReturn)
        {
            goto l_lblExit;
        }


        ////////////////////////////////////////////////////////////////////////
        //scan HEX constants for errors
        l_pEl = NULL;
        while ((l_pEl = m_cTokens.Get_Next(l_pEl)))
        {
            sToken *l_pToken = m_cTokens.Get_Data(l_pEl);
            if (    (l_pToken)
                 && (ETYPE_CONST == l_pToken->m_eType)
               )
            {
                const XCHAR *l_pX  = l_pToken->m_pText;

                if (0 == PStrNCmp(l_pToken->m_pText, TM("0x"), 2))
                {
                    tUINT32 l_dwX_Count = 0;
                    while (*l_pX)
                    {   
                        if (TM('x') == *l_pX)
                        {
                            l_dwX_Count ++;
                            if (2 >= l_dwX_Count)
                            {
                                m_pError_Text    = TM("Error, wrong hex value!");
                                m_szError_Offset = l_pToken->m_szOffset;
                                l_bReturn        = FALSE;
                                break;
                            }
                        }

                        l_pX++;
                    }
                }
                else
                {
                    while (*l_pX)
                    {   
                        if (PStrChr(TOKEN_DIGIT_HEX, *l_pX))
                        {
                            m_pError_Text    = TM("Error, wrong hex value!");
                            m_szError_Offset = l_pToken->m_szOffset;
                            l_bReturn        = FALSE;
                            break;
                        }

                        l_pX++;
                    }
                }
            }
        }//while (l_pEl = m_cTokens.Get_Next(l_pEl))

        if (FALSE == l_bReturn)
        {
            goto l_lblExit;
        }

    l_lblExit:
        return l_bReturn;
    }//Grammatical_Scan


    ////////////////////////////////////////////////////////////////////////
    //AST_Build
    tBOOL AST_Build(sNode *i_pCursor, pAList_Cell &l_pEl_Token)
    {
        CBList<const sOp*> *l_pUnary  = NULL;
        sNode              *l_pCursor = i_pCursor;
        sNode              *l_pArg    = NULL;
        tBOOL               l_bReturn = TRUE;
        sToken             *l_pToken  = NULL;

        ////////////////////////////////////////////////////////////////////////
        //parse tokens
        while ((l_pEl_Token = m_cTokens.Get_Next(l_pEl_Token)))
        {
            sToken *l_pToken = m_cTokens.Get_Data(l_pEl_Token);
            if (ETYPE_UNARY_OPERATOR == l_pToken->m_eType)
            {
                if (NULL == l_pUnary)
                {
                    l_pUnary = new CBList<const sOp*>;
                }

                const sOp *l_pOp = Get_Operator(l_pToken->m_pText, sOp::CLASS_UNARY);
                if (l_pOp)
                {
                    l_pUnary->Add_After(l_pUnary->Get_Last(), l_pOp);
                }
                else
                {
                    m_pError_Text    = TM("Error, wrong sequence");
                    m_szError_Offset = l_pToken->m_szOffset;
                    l_bReturn        = FALSE;
                }
            }
            else if (    (ETYPE_CONST    == l_pToken->m_eType)
                      || (ETYPE_VARIABLE == l_pToken->m_eType)
                    )
            {
                l_pArg = new sNode(   (ETYPE_CONST == l_pToken->m_eType) 
                                    ? sNode::TYPE_LEAF_CONST 
                                    : sNode::TYPE_LEAF_VARIABLE
                                  );

                if (ETYPE_CONST == l_pToken->m_eType) 
                {
                    l_pArg->m_sArg.m_llValue = Scan_Value(l_pToken->m_pText);
                }
                else
                {
                    l_pArg->m_sArg.m_pVariable = Get_Variable(l_pToken->m_pText);
                }

                l_pArg->m_sArg.m_pOpUnary = l_pUnary;
                l_pUnary = NULL;
            }
            else if (ETYPE_BINARY_OPERATOR == l_pToken->m_eType)
            {
                sNode *l_pOp = new sNode(sNode::TYPE_OPERATION);
                l_pOp->m_sOp.m_pOpBinary = Get_Operator(l_pToken->m_pText, sOp::CLASS_BINARY);

                if (sNode::TYPE_GROUP == l_pCursor->m_eType)
                {
                    l_pCursor->m_sGr.m_pSub = l_pOp;
                    l_pOp->m_pPrev          = l_pCursor;
                    l_pOp->m_sOp.m_pLeft    = l_pArg;
                    l_pCursor               = l_pOp;
                    l_pArg                  = NULL;
                }
                else 
                {
                    //if new operation has higher priority than cursor
                    if (l_pOp->m_sOp.m_pOpBinary->m_iPriority > l_pCursor->m_sOp.m_pOpBinary->m_iPriority)
                    {
                        l_pCursor->m_sOp.m_pRight = l_pOp;
                        l_pOp->m_pPrev            = l_pCursor;
                        l_pOp->m_sOp.m_pLeft      = l_pArg;
                        l_pArg                    = NULL;
                        l_pCursor                 = l_pOp;
                    }
                    else
                    {
                        sNode *l_pCurSub = NULL;
                        l_pCursor->m_sOp.m_pRight = l_pArg;
                        l_pArg                    = NULL;

                        //root operator is always group, so this is why 
                        //l_pCursor != NULL
                        while (sNode::TYPE_OPERATION == l_pCursor->m_eType)
                        {
                            if (l_pOp->m_sOp.m_pOpBinary->m_iPriority > l_pCursor->m_sOp.m_pOpBinary->m_iPriority)
                            {
                                break;
                            }
                            else
                            {
                                l_pCurSub = l_pCursor;
                                l_pCursor = l_pCursor->m_pPrev;
                            }
                        }

                        if (sNode::TYPE_GROUP == l_pCursor->m_eType)
                        {
                            l_pOp->m_sOp.m_pLeft    = l_pCursor->m_sGr.m_pSub;
                            l_pOp->m_pPrev          = l_pCursor;
                            l_pCursor->m_sGr.m_pSub = l_pOp;
                            l_pCursor               = l_pOp;
                        }
                        else
                        {
                            l_pOp->m_pPrev       = l_pCursor;
                            l_pOp->m_sOp.m_pLeft = l_pCurSub;

                            if (l_pCurSub == l_pCursor->m_sOp.m_pLeft)
                            {
                                l_pCursor->m_sOp.m_pLeft  = l_pOp;
                            }
                            else
                            {
                                l_pCursor->m_sOp.m_pRight = l_pOp;
                            }

                            l_pCursor = l_pOp;
                        }
                    }
                }
            }//else if (ETYPE_BINARY_OPERATOR == l_pToken->m_eType)
            else if (ETYPE_PARENTHESES_O == l_pToken->m_eType)
            {
                l_pArg = new sNode(sNode::TYPE_GROUP);

                l_pArg->m_sGr.m_pOpUnary = l_pUnary;
                l_pUnary  = NULL;
                l_bReturn = AST_Build(l_pArg, l_pEl_Token);
            }
            else if (ETYPE_PARENTHESES_C == l_pToken->m_eType)
            {
                break;
            }

            if (FALSE == l_bReturn)
            {
                break;
            }
        }//while (l_pEl = m_cTokens.Get_Next(l_pEl))

        if (    (l_pArg)
             && (l_bReturn)
           )
        {
            if (l_pCursor)
            {
                if (sNode::TYPE_GROUP == l_pCursor->m_eType)
                {
                    l_pCursor->m_sGr.m_pSub = l_pArg;
                }
                else 
                {
                    l_pCursor->m_sOp.m_pRight = l_pArg;
                }

                l_pArg->m_pPrev = l_pCursor;
                l_pArg          = NULL;
            }
            else
            {
                m_pError_Text    = TM("Error, unexpected token!");
                m_szError_Offset = l_pToken->m_szOffset;
                l_bReturn        = FALSE;
            }
        }

        if (l_pArg)
        {
            delete l_pArg;
            l_pArg = NULL;

            m_pError_Text    = TM("Error, algorithmic error!");
            m_szError_Offset = 0;
            l_bReturn        = FALSE;
        }

        if (l_pUnary)
        {
            l_pUnary->Clear(FALSE);
            delete l_pUnary;
            l_pUnary = NULL;

            m_pError_Text    = TM("Error, algorithmic error!");
            m_szError_Offset = 0;
            l_bReturn        = FALSE;
        }

        return l_bReturn;
    }//AST_Build


    ////////////////////////////////////////////////////////////////////////////
    //Compute_Binary
    tINT64 Compute_Binary(sNode *i_pNode)
    {
        tINT64 l_llValue = 0;
        if (sNode::TYPE_GROUP == i_pNode->m_eType)
        {
            l_llValue = Compute_Binary(i_pNode->m_sGr.m_pSub);
            if (i_pNode->m_sGr.m_pOpUnary)
            {
                Compute_Unary(i_pNode->m_sGr.m_pOpUnary, l_llValue);
            }
        }
        else if (sNode::TYPE_OPERATION == i_pNode->m_eType)
        {
            tINT64 l_llValL = 0;
            tINT64 l_llValR = 0;

            ////////////////////////////////////////////////////////////////////
            //get left argument
            if (sNode::TYPE_LEAF_CONST == i_pNode->m_sOp.m_pLeft->m_eType)
            {
                l_llValL = i_pNode->m_sOp.m_pLeft->m_sArg.m_llValue;

                if (i_pNode->m_sOp.m_pLeft->m_sArg.m_pOpUnary)
                {
                    Compute_Unary(i_pNode->m_sOp.m_pLeft->m_sArg.m_pOpUnary, l_llValL);
                }
            }
            else if (sNode::TYPE_LEAF_VARIABLE == i_pNode->m_sOp.m_pLeft->m_eType)
            {
                l_llValL = i_pNode->m_sOp.m_pLeft->m_sArg.m_pVariable->m_llValue;

                if (i_pNode->m_sOp.m_pLeft->m_sArg.m_pOpUnary)
                {
                    Compute_Unary(i_pNode->m_sOp.m_pLeft->m_sArg.m_pOpUnary, l_llValL);
                }
            }
            else
            {
                l_llValL = Compute_Binary(i_pNode->m_sOp.m_pLeft);
            }

            ////////////////////////////////////////////////////////////////////
            //get right argument
            if (sNode::TYPE_LEAF_CONST == i_pNode->m_sOp.m_pRight->m_eType)
            {
                l_llValR = i_pNode->m_sOp.m_pRight->m_sArg.m_llValue;

                if (i_pNode->m_sOp.m_pRight->m_sArg.m_pOpUnary)
                {
                    Compute_Unary(i_pNode->m_sOp.m_pRight->m_sArg.m_pOpUnary, l_llValR);
                }
            }
            else if (sNode::TYPE_LEAF_VARIABLE == i_pNode->m_sOp.m_pRight->m_eType)
            {
                l_llValR = i_pNode->m_sOp.m_pRight->m_sArg.m_pVariable->m_llValue;

                if (i_pNode->m_sOp.m_pRight->m_sArg.m_pOpUnary)
                {
                    Compute_Unary(i_pNode->m_sOp.m_pRight->m_sArg.m_pOpUnary, l_llValR);
                }
            }
            else
            {
                l_llValR = Compute_Binary(i_pNode->m_sOp.m_pRight);
            }

            if (sOp::TYPE_MULTIPLICATION == i_pNode->m_sOp.m_pOpBinary->m_eType)
            {
                l_llValue = l_llValL * l_llValR;
            }
            else if (sOp::TYPE_DIVISION == i_pNode->m_sOp.m_pOpBinary->m_eType)
            {
                l_llValue = l_llValL / l_llValR;
            }
            else if (sOp::TYPE_MODULO == i_pNode->m_sOp.m_pOpBinary->m_eType)
            {
                l_llValue = l_llValL % l_llValR;
            }
            else if (sOp::TYPE_MINUS == i_pNode->m_sOp.m_pOpBinary->m_eType)
            {
                l_llValue = l_llValL - l_llValR;
            }
            else if (sOp::TYPE_PLUS == i_pNode->m_sOp.m_pOpBinary->m_eType)
            {
                l_llValue = l_llValL + l_llValR;
            }
            else if (sOp::TYPE_BITWISE_LEFT_SHIFT == i_pNode->m_sOp.m_pOpBinary->m_eType)
            {
                l_llValue = l_llValL << l_llValR;
            }
            else if (sOp::TYPE_BITWISE_RIGHT_SHIFT == i_pNode->m_sOp.m_pOpBinary->m_eType)
            {
                l_llValue = l_llValL >> l_llValR;
            }
            else if (sOp::TYPE_GREATER == i_pNode->m_sOp.m_pOpBinary->m_eType)
            {
                l_llValue = l_llValL > l_llValR;
            }
            else if (sOp::TYPE_LESS == i_pNode->m_sOp.m_pOpBinary->m_eType)
            {
                l_llValue = l_llValL < l_llValR;
            }
            else if (sOp::TYPE_GREATER_OR_EQUAL == i_pNode->m_sOp.m_pOpBinary->m_eType)
            {
                l_llValue = l_llValL >= l_llValR;
            }
            else if (sOp::TYPE_LESS_OR_EQUAL == i_pNode->m_sOp.m_pOpBinary->m_eType)
            {
                l_llValue = l_llValL <= l_llValR;
            }
            else if (sOp::TYPE_EQUAL == i_pNode->m_sOp.m_pOpBinary->m_eType)
            {
                l_llValue = l_llValL == l_llValR;
            }
            else if (sOp::TYPE_NOT_EQUAL == i_pNode->m_sOp.m_pOpBinary->m_eType)
            {
                l_llValue = l_llValL != l_llValR;
            }
            else if (sOp::TYPE_BITWISE_AND == i_pNode->m_sOp.m_pOpBinary->m_eType)
            {
                l_llValue = l_llValL & l_llValR;
            }
            else if (sOp::TYPE_BITWISE_XOR == i_pNode->m_sOp.m_pOpBinary->m_eType)
            {
                l_llValue = l_llValL ^ l_llValR;
            }
            else if (sOp::TYPE_BITWISE_OR == i_pNode->m_sOp.m_pOpBinary->m_eType)
            {
                l_llValue = l_llValL | l_llValR;
            }
            else if (sOp::TYPE_LOGICAL_AND == i_pNode->m_sOp.m_pOpBinary->m_eType)
            {
                l_llValue = l_llValL && l_llValR;
            }
            else if (sOp::TYPE_LOGICAL_OR == i_pNode->m_sOp.m_pOpBinary->m_eType)
            {
                l_llValue = l_llValL || l_llValR;
            }
        }
        else if (sNode::TYPE_LEAF_CONST == i_pNode->m_eType)
        {
            l_llValue = i_pNode->m_sArg.m_llValue;

            if (i_pNode->m_sArg.m_pOpUnary)
            {
                Compute_Unary(i_pNode->m_sArg.m_pOpUnary, l_llValue);
            }
        }
        else if (sNode::TYPE_LEAF_VARIABLE == i_pNode->m_eType)
        {
            l_llValue = i_pNode->m_sArg.m_pVariable->m_llValue;

            if (i_pNode->m_sArg.m_pOpUnary)
            {
                Compute_Unary(i_pNode->m_sArg.m_pOpUnary, l_llValue);
            }
        }

        return l_llValue;
    }//Compute_Binary


    ////////////////////////////////////////////////////////////////////////////
    //Compute_Unary
    void Compute_Unary(CBList<const sOp*> *i_pOpUnary, tINT64 &i_rValue)
    {
        pAList_Cell l_pEl = NULL;
        const sOp*  l_pOp;

        while ((l_pEl = i_pOpUnary->Get_Prev(l_pEl)))
        {
            l_pOp = i_pOpUnary->Get_Data(l_pEl);
            
            if (sOp::TYPE_LOGICAL_NOT == l_pOp->m_eType)
            {
                i_rValue = !i_rValue;
            }
            else if (sOp::TYPE_BITWISE_NOT == l_pOp->m_eType)
            {
                i_rValue = ~i_rValue;
            }
            else if (sOp::TYPE_UNARY_PLUS == l_pOp->m_eType)
            {
                i_rValue = +i_rValue;
            }
            else if (sOp::TYPE_UNARY_MINUS == l_pOp->m_eType)
            {
                i_rValue = -i_rValue;
            }
        }
    }//Compute_Unary

    ////////////////////////////////////////////////////////////////////////////
    //Get_Variable
    sVariable *Get_Variable(const XCHAR *i_pName)
    {
        sVariable  *l_pReturn = NULL;
        pAList_Cell l_pEl     = NULL;

        ////////////////////////////////////////////////////////////////////////
        //scan tokens sequence
        l_pEl = NULL;
        while ((l_pEl = m_cVariables.Get_Next(l_pEl)))
        {
            l_pReturn = m_cVariables.Get_Data(l_pEl);
            if (    (l_pReturn)
                 && (0 == PStrICmp(l_pReturn->m_pName, i_pName))
               )
            {
                break;
            }
            else
            {
                l_pReturn = NULL;
            }
        }

        if (NULL == l_pReturn)
        {
            l_pReturn = new sVariable(i_pName);
            m_cVariables.Add_After(m_cVariables.Get_Last(), l_pReturn);
        }
        
        return l_pReturn;
    }//Get_Variable

    ////////////////////////////////////////////////////////////////////////////
    //Get_Value
    tINT64 Scan_Value(const XCHAR *i_pText)
    {
        tINT64 l_llReturn = 0ll;
        if (NULL == i_pText)
        {
            return l_llReturn;
        }

        if (    (0 != i_pText[0])
             && (TM('x') ==  i_pText[1])
           )
        {
            PStrScan(i_pText, TM("0x%llX"), (tUINT64*)&l_llReturn);
        }
        else
        {
            PStrScan(i_pText, TM("%lld"), &l_llReturn);
        }

        return l_llReturn;
    }//Get_Value

    ////////////////////////////////////////////////////////////////////////////
    //Get_Operator
    const sOp* Get_Operator(const XCHAR *i_pText, sOp::eClass i_eClass)
    {
        const sOp *l_pReturn = NULL;

        for (tUINT32 l_dwI = 0; l_dwI < LENGTH(m_pOperators); l_dwI++)
        {
            if (    (i_eClass == m_pOperators[l_dwI].m_eClass)
                 && (0 == PStrCmp(m_pOperators[l_dwI].m_pText, i_pText))
               )
            {
                l_pReturn = &m_pOperators[l_dwI];
                break;
            }
        }

        return l_pReturn;
    }//Get_Operator
};//CExpression


#endif //EXPRESSION_H