Archived

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

ISOPimp

Evaluate nested statements

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