• Advertisement

Archived

This topic is now archived and is closed to further replies.

Evaluate nested statements

This topic is 5276 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am trying to write an expression parser that can handle nested (? style if statements in C#. I have a library that can handle the bracket counting, evalution, etc that I downloaded, but it does not handle the if statements so I have to make my own parser for that. Now I have an idea of putting the nested statements into a tree type system where I break my original statement down into branches then solve it from the ends first. Its kinda hard to explain so here is an example. Here is the original expression
5 - ((6 > 2) ? 2 : 0) + 5 - 6 ( (8 + 2) - ( 8 > 2 ? (5 < 6 ? 1 : 0) : 2)) + 2  
here is the tree, and the tree after a first pass of the evalution: My problem is finding a way to organize the original statement into a tree of this sort is a fast and accurate manner. So if anyone can give me some suggestions or some examples, I would be extremely thankful. Thank you. [edited by - ISOPimp on August 14, 2003 6:10:46 PM]

Share this post


Link to post
Share on other sites
Advertisement
Are yu just trying to evaluate the expression, or are you needing it to be stored in a tree (eg for multiple evaluations with variable values).

If you only want to evaluate the expression, you probably don't need to use a tree, you'd be better off just with a recursive function.

I'm assuming there's only one type of value, the integer, and that all sub-expressions and bracketed expressions return an integer.

If all the above is true, you could just use a function like the following (pseudo-code).


int evaluate(string expression) {
scan(expression) for the highest-order operator.

if(operator == "?") {
int res = evaluate(expression before operator)
scan(expression after operator) for ":"
if(res) return evaluate(expression after "?" before ":")
return evaluate(expression after ":")
// this has the added bonus of not having to calculate the result that won't be returned.

}

if(operator == "(") {
scan_reverse(expression) for ")"
return evaluate(expression after "(" before ")".
}
if(operator == none) return string_to_num(expression)

return func(operator, evaluate(expression before operator, expression after operator).
}

int func(operator, int v1, int v2) {
switch(operator)
case "+": return v1 + v2.
case ">": return v1 > v2.
etc...
}
}


and have a list of operators according to BEDMAS priority, where brackets are the lowest priority.

or, faster, have each entry in the operator list contain a function pointer

if you need the speed, it you probably don't want to copy the string every time, so simply replace the operator with a null character to break the string into two pieces.

This isn't that pretty (especially the special case for ?), but it should work.
If you want a prettier solution, you might want to consider using a pre-made parser.

(edit) - forgot source tags.

[edited by - Krylloan on August 14, 2003 7:10:32 PM]

Share this post


Link to post
Share on other sites

  • Advertisement