How to check the validity of a math expression?

[TmX]

I think the most simple way is to check whether the right and left parentheses are balanced or not, using stack.
Unfortunately, you still need more work to do.

For example:
3 + ( 4 * (9 - 7)) --> this is valid, because the right and left parentheses are balanced
3 ( ) - 8 --> this is not valid even though the parentheses are balanced, because 3 () is meaningless

So, is there an easier way to do that, probably without using regex FSMs ?

[dedndave]

sounds like a nice place for a little recursive routine

[TmX]

hmm something like recursive descent parser?

[hutch--]

TmX,

Its been a long time but as long as you can write a parser that gets the inner pair of brackets then converts the content to a number then replace each inner pair of brackets and content5 with the result, you can either iteratively or recursively repeat the operation until there are no brackets left and you have a single result.

You get the inner pair by testing first for an opening bracket "(" and if the next bracket is NOT another "(" but a ")" then you have the inner pair. Replace the complete bracketing and content (x * y) with "result" then keep doing it until there are no brackets left.

[Mark Jones]

What about RPN, could that be implemented in a way? i.e. push all the operands to the stack, including the brackets, and handle them recursively?

[dedndave]

that is how i would do it i think
dunno if it is rpn or not, but write the recursive so the self-call is early in the routine
that way, it parses into the deepest parens first (as Hutch suggested) in recursion
then works the math on the way out of recursion

[Slugsnack]

i've done something like this in haskell in the past, it's really easy there but that's cause of pattern matching. if you can reproduce something similar, it's very simple

what you wanna do is take the arity of each operator you have. then start from the outside and keep evaluating. so if you had :

( a + b ) * c

then the outermost operator would be * with an arity of 2. so your parser would split it to :

( a + b )                                                    and                                        c

then you work recursively on each side. the basecase is when the thing you are evaluating is an atom. in this case, c is an atom. a + b would be broken down into a and b which are atoms..

for your problem that is in your evaluating procedure. your procedure would not recognise 3 () as either an atom or a valid procedure for further recursive processing and would return false

[fearless]

I had a look at RPN stuff recently for a project of mine, and came across this algo: Shunting Yard Algo at Wiki (http://en.wikipedia.org/wiki/Shunting-yard_algorithm) breaks down an example and accounts for if there are too many brackets or too little. Could be useful for you.