parser.cpp

表达式计算expression evaluate expression evaluate expression evaluate

/******************************************************************************
文件名          :Parser.cpp
版本号          : 1.0
作者            : Amos Peng
生成日期        :2008-07-08
最近修改        :
功能描述        :解析器
函数列表        :

*******************************************************************************/
#include "Parser.h"
using namespace ExprEval;

namespace
{
    bool expreval_isalpha(char c)
    {
        return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
    }
		
    bool expreval_isdigit(char c)
    {
        return (c >= '0' && c <= '9');
    }
		
    bool expreval_isalnum(char c)
    {
        return expreval_isalpha(c) || expreval_isdigit(c);
    }
	
    bool expreval_isspace(char c)
    {
        return (c == ' ') || (c == '\t') || (c == '\r') || (c == '\n');
    }
		
    double expreval_atof(const char* str)
    {
        bool negative = false;
        long double value = 0.0;
	
        // Skip space
        while(expreval_isspace(*str))
        {
            str++;
        }				
	
        // Check for sign
        if(*str == '-')
        {
            negative = true;
            str++;
        }
        else if(*str == '+')
        {
            str++;
        }
	
        // The part before the decimal
        while(*str >= '0' && *str <= '9')
        {
            value = (value * 10.0) + (double)(*str - '0');
            str++;
        }
	
        // Decimal, if any
        if(*str == '.')
        {
            long double divisor = 1.0;
            str++;
	
            // Part after the decimal, if any
            while(*str >= '0' && *str <= '9')
            {
                value = (value * 10.0) + (double)(*str - '0');
                divisor *= 10.0;
                str++;
            }
	
            value /= divisor;
        }
	
        // The result
        return negative ? -value : value;
    }
};

CParser::CParser(CExpression *expr) : m_expr(expr)
{
    if(expr == 0)
    {
        throw(CNullPointerException("Parser::Parser"));
    }        
}
    
// Destructor
CParser::~CParser()
{
}
    
// Parse an expression string
CNode *CParser::Parse(const ::std::string &exstr)
{
    BuildTokens(exstr);
    
    // Make sure it is not still empty
    if(m_tokens.size() == 0)
    {
        throw(CEmptyExpressionException());
    }        
        
    // Parse the range
    return ParseRegion(0, m_tokens.size() - 1);
}

// Parse a region of tokens
CNode* CParser::ParseRegion(CParser::size_type start, CParser::size_type end)
{
    size_type pos;
    size_type fgopen = (size_type)-1;
    size_type fgclose = (size_type)-1;
    size_type assignindex = (size_type)-1;
    size_type addsubindex = (size_type)-1;
    size_type muldivindex = (size_type)-1;
    size_type posnegindex = (size_type)-1;
    size_type expindex = (size_type)-1;
    bool multiexpr = false;
    int plevel = 0;
    
    // Check simple syntax
    if(start > end)
    {
        throw(CSyntaxException());
    }
        
        
    // Scan through tokens
    for(pos = start; pos <= end; pos++)
    {
        switch(m_tokens[pos].GetType())
        {
            case CToken::TypeOpenParenthesis:
            {
                plevel++;
                
                // Opening of first group?
                if(plevel == 1 && fgopen == (size_type)-1)
                {
                    fgopen = pos;
                }
                    
                break;
            };
                
            case CToken::TypeCloseParenthesis:
            {
                plevel--;
                
                // First group closed?
                if(plevel == 0 && fgclose == (size_type)-1)
                {
                    fgclose = pos;
                }                    
                    
                if(plevel < 0)
                {
                    CUnmatchedParenthesisException e;
                    
                    e.SetStart(m_tokens[pos].GetStart());
                    e.SetEnd(m_tokens[pos].GetEnd());
                    throw(e);
                }
                    
                break;
            }
                
            case CToken::TypeEqual:
            {
                if(plevel == 0)
                {
                    if(assignindex == (size_type)-1)
                    {
                        assignindex = pos;
                    }
                        
                }
                    
                break;
            }
                
            case CToken::TypeAsterisk:
            case CToken::TypeForwardSlash:
            {
                if(plevel == 0)
                {
                    muldivindex = pos;
                }
                    
                break;
            }
                
            case CToken::TypeHat:
            {
                if(plevel == 0)
                {
                    expindex = pos;
                }
                
                break;
            }
                
            case CToken::TypePlus:
            case CToken::TypeHyphen:
            {
                if(plevel == 0)
                {
                    if(pos == start)
                    {
                        // Positive or negative sign
                        if(posnegindex == (size_type)-1)
                        {
                            posnegindex = pos;
                        }
                            
                    }
                    else
                    {
                        // What is before us
                        switch(m_tokens[pos - 1].GetType())
                        {
                            case CToken::TypeEqual:
                            case CToken::TypePlus:
                            case CToken::TypeHyphen:
                            case CToken::TypeAsterisk:
                            case CToken::TypeForwardSlash:
                            case CToken::TypeHat:
                                // After any of these, we are a positive/negative
                                if(posnegindex == (size_type)-1)
                                {
                                    posnegindex = pos;
                                }                                    
                                break;
                                
                            default:
                                // After any other, we are addition/subtration
                                addsubindex = pos;
                                break;
                        }
                    }
                }
                    
                break;
            }
                
            case CToken::TypeSemicolon:
            {
                if(plevel == 0)
                {
                    multiexpr = true;
                }
                
                break;
            }
        }
    }
        
    // plevel should be 0
    if(plevel != 0)
    {
        CUnmatchedParenthesisException e;
        
        e.SetStart(end);
        e.SetEnd(end);
        throw(e);
    }
        
    // Parse in certain order to maintain order of operators
    
    // Multi-expression first
    if(multiexpr)
    {
        ::std::auto_ptr<CNode> n(new CMultiNode(m_expr));
        n->Parse(*this, start, end);
        return n.release();
    }
    else if(assignindex != (size_type)-1)
    {
        // Assignment next
        ::std::auto_ptr<CNode> n(new CAssignNode(m_expr));
        n->Parse(*this, start, end, assignindex);
        return n.release();
    }
    else if(addsubindex != (size_type)-1)
    {
        // Addition/subtraction next
        if(m_tokens[addsubindex].GetType() == CToken::TypePlus)
        {
            // Addition
            ::std::auto_ptr<CNode> n(new CAddNode(m_expr));
            n->Parse(*this, start, end, addsubindex);
            return n.release();
        }
        else
        {
            // Subtraction
            ::std::auto_ptr<CNode> n(new CSubtractNode(m_expr));
            n->Parse(*this, start, end, addsubindex);
            return n.release();
        }
    }
    else if(muldivindex != (size_type)-1)
    {
        // Multiplication/division next
        
        if(m_tokens[muldivindex].GetType() == CToken::TypeAsterisk)
        {
            // Multiplication
            ::std::auto_ptr<CNode> n(new CMultiplyNode(m_expr));
            n->Parse(*this, start, end, muldivindex);
            return n.release();
        }
        else
        {
            // Division
            ::std::auto_ptr<CNode> n(new CDivideNode(m_expr));
            n->Parse(*this, start, end, muldivindex);
            return n.release();
        }
    }
    else if(posnegindex == start)
    {
        // Positive/negative next, must be at start and check before exponent
        if(m_tokens[posnegindex].GetType() == CToken::TypePlus)
        {
            // Positive
            return ParseRegion(posnegindex + 1, end);
        }
        else
        {
            ::std::auto_ptr<CNode> n(new CNegateNode(m_expr));
            n->Parse(*this, start, end, posnegindex);
            return n.release();
        }
    }
    else if(expindex != (size_type)-1)
    {
        // Exponent
        ::std::auto_ptr<CNode> n(new CExponentNode(m_expr));
        n->Parse(*this, start, end, expindex);
        return n.release();
    }
    else if(posnegindex != (size_type)-1)
    {
        // Check pos/neg again.  After testing for exponent, a pos/neg
        // at plevel 0 is syntax error
        CSyntaxException e;
        
        e.SetStart(m_tokens[posnegindex].GetStart());
        e.SetEnd(m_tokens[posnegindex].GetEnd());
        throw(e);
    }
    else if(fgopen == start)
    {
        // Group parenthesis, make sure something in between them
        if(fgclose == end && fgclose > fgopen + 1)
        {
            return ParseRegion(fgopen + 1, fgclose - 1);
        }