Inefficient/Repetitious Parsing

This is a discussion on Inefficient/Repetitious Parsing within the C Programming forums, part of the General Programming Boards category; Say I have a string, an equation, with a variable, X, that I want to compute with varying values of ...

  1. #1
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587

    Inefficient/Repetitious Parsing

    Say I have a string, an equation, with a variable, X, that I want to compute with varying values of X. The most obvious and straight forward way to do this would be to parse the equation every time, inserting the value of X every time. The problem is that this is very inefficient to re-parse the whole string when the only change will be the value of X. Is there a "standard" solution to this problem?

    I've thought of a few solutions, some more complex to code than others.

    Solution 1, the easiest(other than re-parsing): Tokenize everything, make a way to encode the equation in predetermined control codes, then encode the equation in a way that sequentially(from one instruction to the next) follows order of operations that should be used in the original equation.

    Solution 2, definitely not the way I want to go, but also definitely the most efficient: Translate the equation into a machine code way to compute it(basically, translate to asm, then assemble it on the fly), making any reference to X a pointer to a variable I could change in between runnings of the code that symbolizes the equation.

  2. #2
    Registered User
    Join Date
    May 2010
    Location
    Naypyidaw
    Posts
    1,314
    Compile to some kind of byte codes. You need not necessarily translate to asm.
    like 3 + 2 *x to
    push 3
    push 2
    push var x
    multiply
    add
    print

    Hoc

  3. #3
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Can you post the equation and a sample of the input 'n output.

  4. #4
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    So solution1? I think I'll take your advice. It would make sense either way really, the byte codes could be used as an intermediate language between the equation and the asm.

    That Hoc thing is really cool. Just about what I was thinking of making, it seems a lot better than even my highest aspirations of my conceptual project.

    [Edit]
    The equation could be something like this: "9x/2+3"

    The io would ask for the equation, identify the variable(s), ask for the initial value of the variable(s), ask for the [recursive] equation to find subsequent values of the variable(s), ask how many iterations to do, and output the answer of each iteration.
    [/Edit]
    Last edited by User Name:; 06-14-2010 at 07:50 PM. Reason: I didn't see itCbitC's post.

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Put the possible values of x into a small int array numX[];

    Now use a for loop:

    Code:
    for(i=0; i<MaxNums; i++) {
      x=numX[i];
      //rest of your code
    }
    I wouldn't switch it over to asm for all the tea in china, because there goes your portability, and your clarity for others, etc. That's like waving the white flag "despite the current strength of the PC's, I am unable to make my simple math function, fast enough". No, that just won't do.

    If you need a general calculator, I'd suggest RPN. Check it out on Wikipedia.
    Last edited by Adak; 06-14-2010 at 10:26 PM.

  6. #6
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    It's not the calculator part, it's the repetitious part I'm interested in. I've recently became obsessed with limits and in particular, infinite sums. I'm making this as a practical way of evaluating limits. The variables used can be used recursively, making pseudo-infinite sums possible(I just loop until the significand from the previous iteration == the significand from the current iteration). It could take a while to overflow the significand of a double, that's why performance matters.

    It was the infamous .(9) == 1 that got me interested, but I'm unsure of whether I think it is true or not.

  7. #7
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    Here's my prototype definition of my control byte, it tells me what to do with the next operand, and tells me whether the operand is the value itself, or a pointer to the value. Any suggestions? Is there anything that I'm overlooking that you see could cause some problems latter on in the project?
    I'll just copy and paste my documentation out of my source, it's already well formatted:
    Code:
    /*
     * The contol byte will consist of bit fields that will be formatted as follows:
     *
     * 0-3 = Type of operation to be performed
     *   0000 = add
     *   0001 = subtract
     *   0010 = multiply
     *   0011 = divide
     *   0100-1111 = undefined
     *
     * 4 = Type of operand
     *   0 = double
     *   1 = *double
     *
     * 5-7 = undefined
     */

  8. #8
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Post what the operand looks like and also the equation that you're trying to solve programatically.

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    I'm not really seeing what you're gaining here. Shuffling around an array of operands isn't any better than shuffling around an array of characters.

    Quzah.
    Hope is the first step on the road to disappointment.

  10. #10
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,236
    I think byte codes are overkill. Just construct an expression tree and evaluate it. Here's the basics:

    Code:
    enum op { add, sub, mul, div, constant, X };
    
    struct expression_node
    {
        enum op operator;
        double value;
        struct expression_node *lhs;
        struct expression_node *rhs;
    };
    
    double eval( struct expression_node *node, double Xvalue )
    {
        if( node->operator == add )
            return eval( node->lhs, Xvalue ) + eval( node->rhs, Xvalue );
        if( node->operator == sub )
            return eval( node->lhs, Xvalue ) - eval( node->rhs, Xvalue );
        if( node->operator == mul )
            return eval( node->lhs, Xvalue ) * eval( node->rhs, Xvalue );
        if( node->operator == div )
            return eval( node->lhs, Xvalue ) / eval( node->rhs, Xvalue );
        if( node->operator == constant )
            return node->value;
        if( node->operator == X )
            return Xvalue;
        assert( ( "Operator is not recognized", 0 ) );
    }
    Then in your parser, build up this tree, then call eval() on it. To fiddle the X value, just pass in what you want it to be.
    Last edited by brewbuck; 06-16-2010 at 04:51 PM.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  11. #11
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    brewbuck, that it awesome! Thank you. I'm working on it now. I'm thinking about turning this into a cpp project though, how cool would it be to have a whole equation class, it could be inited with a string but return an int.

  12. #12
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    If the only part of C++ I want is classes con/destructors and operators, would it be better to use Objective C? What is Objective C?

  13. #13
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    Objective C is just another language, that like C++ adds OOP to C. I believe you can intermix pure C more freely in it though, but unless you already know it I don't see it adding any specific benefits in this case.

    http://en.wikipedia.org/wiki/Objecti...f_the_language
    Last edited by Subsonics; 06-16-2010 at 06:11 PM.

  14. #14
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,295
    Another advantage of building and keeping the expression tree around rather than spitting out bytecode is that you can probably more easily optimise the tree first, such as removing multiplications by 1 or addition of zero etc.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 04-29-2010, 08:02 PM
  2. need sth about parsing
    By Masterx in forum C++ Programming
    Replies: 6
    Last Post: 11-06-2008, 11:55 PM
  3. draw tree graph of yacc parsing
    By talz13 in forum C Programming
    Replies: 2
    Last Post: 07-23-2006, 01:33 AM
  4. Parsing for Dummies
    By MisterWonderful in forum C++ Programming
    Replies: 4
    Last Post: 03-08-2004, 04:31 PM
  5. I hate string parsing with a passion
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 03-19-2002, 06:30 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21