samedi 2 mai 2015

What is the proper design pattern for parsing an expression of the type [A][B][A][B]....[B][A]?

I'm making an algorithm that parses a mathematical function into a function tree. The idea behind it is that the function, represented as a string, will look like

[expression][operator][expression][operator]...[operator][expression]

and my algorithm will be like

  1. Get first expression
  2. Make first expression be the root of the tree
  3. While not at end of string, get operator and expression following it. Add expression to its proper place in the tree.

Get last operator and expression following it

I've outlined what's going to happen in the comments of the below code.

node * buildTree ( char * str )
{
/*
    str is expected to be of the form 

        [expr_0][op_1][expr_1][op_2][expr_2]...[op_n][expr_n]

    For example, 

        "x^2*(5+x)"

    has 
        expr_0 = "x",
         op_1  = "^"
        expr_1 = "2"
         op_2  = "*"
        expr_2 = "(5+x)"

    The function expressions are represented as node elements. Returns the root of the function
    tree that is built.
*/

    node * rt; // Node to return, the root of the function tree
    node * thisExpr; // Current function
    char thisOp; // Current operator

    /* The beginning of str is expected to be a function expression (rather than an operator). 
       The following sets thisExpr equal to that expression and advance the pointer str to the character following it.
    */
    if (!throughNextExpr(&str, &thisExpr))
    {
        return NULL;
    }
    else
    {
        rt = thisExpr;
    }

    while (str)
    {
        /* Current caracter is expected to be an operator. Set thisOp equal to it and advance to the next character 
        */
        thisOp = *str;
        if (indexOf(thisOp, opstack) == -1)
        {
            return NULL;
        }
        ++str;
        /* Current character is expected to be the beginning of an expression. Set thisExpr equal to it and avance to the character following the epxression
        */
        if (throughNextExpr(&str, &thisExpr))
        {
            // ...
        }
        else // error in trying to get next expression
        {
            return NULL;
        }

    }
    return rt;
}

int throughNextExpr ( char * * str, node * * N )
{
    int goodSoFar = 1;
    // .... Yet to be implemented
    return goodSoFar;
}

The problem is that this seems like very unelegant way of doing things, since getting the first expression is separated from the loop that gets the others. I feel like there should be a way of doing this all in a loop rather than separating into cases. Is there a known design pattern that I should be looking at instead?

Aucun commentaire:

Enregistrer un commentaire