• ### Announcements

#### Archived

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

# Evaluate nested statements

## Recommended Posts

ISOPimp    122
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 on other sites
Krylloan    142
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]