Inefficient/Repetitious Parsing

**User Name:** · 06-14-2010

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.

**Bayint Naung** · 06-14-2010

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

**itCbitC** · 06-14-2010

Can you post the equation and a sample of the input 'n output.

**User Name:** · 06-14-2010

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]

**Adak** · 06-14-2010

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.

**User Name:** · 06-14-2010

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.

**User Name:** · 06-16-2010

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
 */

**itCbitC** · 06-16-2010

Post what the operand looks like and also the equation that you're trying to solve programatically.

**quzah** · 06-16-2010

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.

**brewbuck** · 06-16-2010

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.

**User Name:** · 06-16-2010

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.

**User Name:** · 06-16-2010

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?

**Subsonics** · 06-16-2010

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

**iMalc** · 06-17-2010

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.

Thread: Inefficient/Repetitious Parsing

Thread Tools

Search Thread

Display

Inefficient/Repetitious Parsing

Similar Threads

Parsing text file works in windows compiler but not linux

need sth about parsing

draw tree graph of yacc parsing

Parsing for Dummies

I hate string parsing with a passion