algorithmmathevaluationvb5

Expression evaluation


I'm doing an expression valuation program, just like this. My problem is that I can't figure out how to handle operation precedences. I used recursion to find the innermost couple of parenthesis and, when found, solve the expression inside them, like this:

Evaluate("2 + (3 * 5)")

will re-call itself this way:

Evaluate("3 * 5")

now, since there aren't parenthesis, it calculates the result and calls itself another time:

Evaluate("2 + 15")

Ok, the return value is 17, as expected. But if I call Evaluate("2 + 3 * 5") the result is:

Evaluate("2 + 3 * 5")
Evaluate("5 * 5")

Which is clearly wrong.
Basically I'm solving operations from left to right. How can I chose the operations that must be performed first? I was thinking to add a couple of parenthesis surrounding every operation, but it doesn't look so good.
So, do I need to parse the whole expression first o there's another way?


Solution

  • Search for your highest-precedence operator and do that first, then move on. So if you have only + and *, search for instances of * and replace the substring aaaa * bbbb with the value of aaaa * bbbb. Once no such instances remain, work on +.

    If order within a given operator matters (for example, if you include ^) you'll have to decide where to start with those operators.