exprpars.c

数学表达式计算和解析 用c语言编写的,内含有例.速度较快

/* 
    File: ExprPars.c
    Auth: Brian Allen Vanderburg II
    Date: Wednesday, April 30, 2003
    Desc: Actual parsing routines for this library

    This file is part of ExprEval.
*/

/* Includes */
#include "expreval.h"
#include "exprincl.h"
#include "exprint.h"
#include "exprmem.h"

/* Internal functions */
int exprMultiParse(exprObj *o, exprNode *n, char *expr);
int exprInternalParse(exprObj *o, exprNode *n, char *expr, int start, int end);
int exprInternalParseAssign(exprObj *o, exprNode *n, char *expr, int start, int end, int index);
int exprInternalParseAdd(exprObj *o, exprNode *n, char *expr, int start, int end, int index);
int exprInternalParseSub(exprObj *o, exprNode *n, char *expr, int start, int end, int index);
int exprInternalParseMul(exprObj *o, exprNode *n, char *expr, int start, int end, int index);
int exprInternalParseDiv(exprObj *o, exprNode *n, char *expr, int start, int end, int index);
int exprInternalParsePosNeg(exprObj *o, exprNode *n, char *expr, int start, int end, int index);
int exprInternalParseFunction(exprObj *o, exprNode *n, char *expr, int start, int end, int p1, int p2);
int exprInternalParseVarVal(exprObj *o, exprNode *n, char *expr, int start, int end);

/* This is the main parsing routine */
int exprParse(exprObj *o, char *expr)
    {
    /* Buffer to hold expression copy */
    char *exprcopy;
    int err;
    exprNode *tmp;

    /* Have we already been parsed? */
    if(o->parsedbad != 0)
        return EXPR_ERROR_ALREADYPARSEDBAD;

    if(o->parsedgood != 0)
        return EXPR_ERROR_ALREADYPARSEDGOOD;

    /* Make sure an object was passed */
    if(o == NULL)
        return EXPR_ERROR_NULLPOINTER;

    if(expr == NULL)
        return EXPR_ERROR_NULLPOINTER;

    if(expr[0] == '\0') /* Empty string */
        return EXPR_ERROR_EMPTYEXPR;

    /* Allocate memory to copy expression */
    exprcopy = exprAllocMem(strlen(expr) + 1);

    if(exprcopy == NULL)
        return EXPR_ERROR_MEMORY;

    /* Copy the expression */
    strcpy(exprcopy, expr);

    /* Strip whitespace and comments from the expression */
    err = exprStripChars(exprcopy);

    if(err != EXPR_ERROR_NOERROR)
        {
        /* Error during strip */
        exprFreeMem(exprcopy);
        return err;
        }

    /* Validate the characters */
    err = exprValidChars(exprcopy);

    if(err != EXPR_ERROR_NOERROR)
        {
        /* Invalid characters in expression */
        exprFreeMem(exprcopy);
        return err;
        }

    /* Create head pointer */
    tmp = exprAllocMem(sizeof(exprNode));
    if(tmp == NULL)
        {
        exprFreeMem(exprcopy);
        return EXPR_ERROR_MEMORY;
        }

    /* zero the memory */
    memset(tmp, 0, sizeof(exprNode));

    o->headnode = tmp;

    /* Call the multiparse routine to parse subexpressions */
    err = exprMultiParse(o, tmp, exprcopy);

    /* Free the copy of the expression */
    exprFreeMem(exprcopy);

    /* successful parse? */
    if(err == EXPR_ERROR_NOERROR)
        {
        o->parsedgood = 1;
        o->parsedbad = 0;
        }
    else
        {
        o->parsedbad = 1;
        o->parsedgood = 0;
        }

    return err;
    }


/* Parse the subexpressions, each ending with semicolons */
int exprMultiParse(exprObj *o, exprNode *n, char *expr)
    {
    int pos, plevel, last;
    int num, cur, err;
    int len;
    exprNode *tmp;

    plevel = 0;
    num = 0;
    last = -1;

    len = (int)strlen(expr);

    /* First count the number of arguments */
    for(pos = 0; pos < len; pos++)
        {
        switch(expr[pos])
            {
            case '(':
                /* increase plevel */
                plevel++;
                break;
            case ')':
                /* decrease plevel */
                plevel--;

                if(plevel < 0)
                    return EXPR_ERROR_UNMATCHEDPAREN;

                break;

            case ';':
                if(plevel == 0)
                    {
                    if(last == pos - 1 || pos == 0)
                        {
                        /* last semicolon is before us or we are at the start */
                        return EXPR_ERROR_SYNTAX;
                        }
                    else
                        {
                        /* last semicolon is not right before us */
                        num++;
                        }
                    }
                else
                    {
                    /* Semicolon should not be in a parenthesis */
                    return EXPR_ERROR_SYNTAX;
                    }

                last = pos; /* update position of last semicolon */
                break;
            }
        }

    /* plevel should be zero now */
    if(plevel != 0)
        return EXPR_ERROR_UNMATCHEDPAREN;

    /* the last character should be a semicolon */
    if(last != pos - 1)
        return EXPR_ERROR_MISSINGSEMICOLON;

    /* Now we know how many arguments there are */

    /* Allocate array of subnodes */
    tmp = exprAllocMem(sizeof(exprNode) * num);
    if(tmp == NULL)
        return EXPR_ERROR_MEMORY;

    memset(tmp, 0, sizeof(tmp) * num);

    /* Set the current node's data */
    n->type = EXPR_NODETYPE_FUNCTION;
    n->data.function.nodecount = num;
    n->data.function.nodes = tmp;
    n->data.function.fptr = __exprMultiFunc;

    /* now we parse each subexpression */
    last = 0; /* Not for last semicolon, but for first char of subexpr */
    cur = 0;

    for(pos = 0; pos < len; pos++)
        {
        if(expr[pos] == ';')
            {
            /* Everything from last up to pos - 1 is a parameter */
            err = exprInternalParse(o, &(tmp[cur]), expr, last, pos - 1);
            if(err != EXPR_ERROR_NOERROR)
                return err;

            /* Update last position and current argument */
            last = pos + 1;
            cur++;
            }
        }

    return EXPR_ERROR_NOERROR;
    }

/* This function parses each subnode and recurses if needed */
int exprInternalParse(exprObj *o, exprNode *n, char *expr, int start, int end)
    {
    int pos;
    int plevel = 0; /* Paren level */
    int fgopen = -1; /* First paren group open index */
    int fgclose = -1; /* First paren group close index */
    int assignindex = -1; /* First = at plevel 0 for assignment */
    int addsubindex = -1; /* Last + or - at plevel 0 for adding or subtracting */
    int muldivindex = -1; /* Last * or / at plevel 0 for multiplying or dividing */
    int posnegindex = -1; /* First +,- at plevel 0 for positive,negative */
    int lastposnegindex = -1; /* Last +,- found at plevel for for positive,negative */

    /* Make sure some conditions are right */
    if(start > end)
        return EXPR_ERROR_SYNTAX;

    if(expr[start] == '\0' || expr[end] == '\0')
        return EXPR_ERROR_SYNTAX; /* Neither should be at the end of the expression */

    /* Scan the string for certain characters */
    for(pos = start; pos <= end; pos++)
        {
        switch(expr[pos])
            {
            case '(':
                plevel++;

                /* First group open? */
                if(plevel == 1 && fgopen == -1)
                    fgopen = pos;
                break;

            case ')':
                plevel--;

                /* First group close? */
                if(plevel == 0 && fgclose == -1)
                    fgclose = pos;

                if(plevel < 0)
                    return EXPR_ERROR_UNMATCHEDPAREN;
                break;

            case '=':
                /* Assignment found */
                if(plevel == 0 && assignindex == -1)
                    assignindex = pos;
                break;

            case '*':
            case '/':
                /* Multiplication or division */
                if(plevel == 0)
                    muldivindex = pos;
                break;


            case '+':
            case '-':
                /* Addition or positive or subtraction or negative*/
                if(plevel == 0)
                    {
                    /* After any of these, we are positive sign */
                    if(pos == start || pos == assignindex + 1 ||
                        pos == addsubindex + 1 || pos == muldivindex + 1 ||
                        pos == lastposnegindex + 1)
                        {
                        /* We are a positive sign or negative sign */
                        if(posnegindex == -1) /* First positive,negative sign? */
                            posnegindex = pos;

                        /* Keep track of the last one */
                        lastposnegindex = pos;
                        }
                    else
                        {
                        /* We are an addition or subtraction sign */
                        addsubindex = pos;
                        }
                    }
                break;

            }
        }

    /* plevel should now be zero */
    if(plevel != 0)
        return EXPR_ERROR_UNMATCHEDPAREN;

    /* We must parse the data in a certain order to maintain the
       correct order of operators at evaluation time */

    /* First, take care of assignment */
    if(assignindex != -1)
        return exprInternalParseAssign(o, n, expr, start, end, assignindex);

    /* Addition or subtraction is next */
    if(addsubindex != -1)
        {
        if(expr[addsubindex] == '+')
            return exprInternalParseAdd(o, n, expr, start, end, addsubindex);
        else
            return exprInternalParseSub(o, n, expr, start, end, addsubindex);
        }


    /* Multiplycation or division */
    if(muldivindex != -1)
        {
        if(expr[muldivindex] == '*')
            return exprInternalParseMul(o, n, expr, start, end, muldivindex);
        else
            return exprInternalParseDiv(o, n, expr, start, end, muldivindex);
        }


    /* Negation */
    if(posnegindex != -1)
        return exprInternalParsePosNeg(o, n, expr, start, end, posnegindex);


    /* Grouped parenthesis */
    if(fgopen == start)
        {
        /* Closing paren. should be at the end */
        if(fgclose == end)
            {
            /* Anything between them */
            if(fgclose > fgopen + 1)
                {
                return exprInternalParse(o, n, expr, fgopen + 1, fgclose - 1);
                }
            else
                {
                /* Nothing between them */
                return EXPR_ERROR_SYNTAX;
                }
            }
        else /* Closing paren not at the end */
            return EXPR_ERROR_SYNTAX;
        }

    /* Functions */
    if(fgopen > start)
        {
        /* Closing paren should be at end */
        if(fgclose == end)
            {
            return exprInternalParseFunction(o, n, expr, start, end, fgopen, fgclose);
            }
        else /* Closing paren not at end */
            return EXPR_ERROR_SYNTAX;
        }

    /* If it was none of the above, it must be a variable or value */
    return exprInternalParseVarVal(o, n, expr, start, end);
    }

/* Function to parse an assignment node */
int exprInternalParseAssign(exprObj *o, exprNode *n, char *expr, int start, int end, int index)
    {
    int len;
    exprNode *tmp;
    char buf[EXPR_MAXIDENTSIZE + 1];
    exprValList *l;
    EXPRTYPE *addr;


    /* Make sure the equal sign is not at the start or end */
    if(index <= start || index >= end)
        return EXPR_ERROR_SYNTAX;

    /* Length of the variable to assign */
    len = index - start;

    if(len > EXPR_MAXIDENTSIZE)
        return EXPR_ERROR_BADIDENTIFIER;

    /* Copy the variable into the buffer */
    strncpy(buf, expr + start, len);
    buf[len] = '\0';

    /* Make sure this is a valid identifier */
    if(exprValidIdent(buf) == 0)
        {
        return EXPR_ERROR_BADIDENTIFIER;
        }


    /* Create expression subnode */
    tmp = exprAllocMem(sizeof(exprNode));
    if(tmp == NULL)
        {
        return EXPR_ERROR_MEMORY;
        }

    /* Zero the memory */
    memset(tmp, 0, sizeof(exprNode));


    /* Set the data */
    n->type = EXPR_NODETYPE_ASSIGN;
    n->data.assign.node = tmp;


    /*
        The fast access method directly accesses the memory address
        of the variable's value at evaluation time.  Because of this,
        we must make sure the variable does exists in the variable list.
    */

    /* Get the variable list */
    l = exprGetVarList(o);
    if(l == NULL)
        return EXPR_ERROR_NOVARLIST;

    /* Get variable address if already in the list */
    exprValListGetAddress(l, buf, &addr);
    if(addr == NULL) /* Variable not in the list, add it */
        {
        exprValListAdd(l, buf, 0.0);
        
        /* Try to get address again */
        exprValListGetAddress(l, buf, &addr);
        if(addr == NULL) /* Could not add variable */
            return EXPR_ERROR_MEMORY; /* Could not add variable to list */
        }

    n->data.assign.var_addr = addr;

    /* Parse the subnode */
    return exprInternalParse(o, tmp, expr, index + 1, end);
    }

/* Function to parse an addition function */
int exprInternalParseAdd(exprObj *o, exprNode *n, char *expr, int start, int end, int index)
    {
    exprNode *tmp;
    int err;

    /* Make sure plus sign is at a good place */
    if(index <= start || index >= end)
        return EXPR_ERROR_SYNTAX;

    /* Allocate space for 2 subnodes */
    tmp = exprAllocMem(sizeof(exprNode) * 2);
    if(tmp == NULL)
        return EXPR_ERROR_MEMORY;

    /* Zero out the subnodes */
    memset(tmp, 0, sizeof(exprNode) * 2);

    /* Set the data */
    n->type = EXPR_NODETYPE_FUNCTION;
    n->data.function.fptr = __exprAddFunc;
    n->data.function.nodecount = 2;
    n->data.function.nodes = tmp;

    /* parse the left side */
    err = exprInternalParse(o, &(tmp[0]), expr, start, index - 1);
    if(err != EXPR_ERROR_NOERROR)
        return err;

    /* parse the right side */
    return exprInternalParse(o, &(tmp[1]), expr, index + 1, end);
    }

/* Function to parse a subtraction function */
int exprInternalParseSub(exprObj *o, exprNode *n, char *expr, int start, int end, int index)
    {
    exprNode *tmp;
    int err;

    /* Make sure minus sign is at a good place */
    if(index <= start || index >= end)
        return EXPR_ERROR_SYNTAX;

    /* Allocate space for 2 subnodes */
    tmp = exprAllocMem(sizeof(exprNode) * 2);
    if(tmp == NULL)
        return EXPR_ERROR_MEMORY;