1

I am implementing the formula bar in which there can be any operation with two values like:

SUB ( DIV ( ADD (2,5), 4.5 ), AVG (3,4) )

So here I need to first call ADD operation as its most inner operation, then DIV it by some fraction, then calculate the AVG and in last SUB both the values, so there can be any formula user can put on formula bar.

I am trying to write recursive function for that but before that I need to parse it properly. I could not figure out how to write regex for this kind of pattern..

Any ideas please?

nhahtdh
  • 55,989
  • 15
  • 126
  • 162
Subodh
  • 75
  • 1
  • 10
  • 1
    I would bet that if you posted your recursive function you'd get a better suggestion that didnt require regex. – crthompson Jan 03 '14 at 07:00
  • Post sample input and expected output please, so people will better understand what regex you want. – Tafari Jan 03 '14 at 07:49
  • Thanks paqogomez and Tafari for your concern.. actually I have not yet develop any function.. I have only the problem and its up to me to find out the best way.. I thought recursive will be the solution as once I get inner operation result then I will call it again to resolve outer operation..& so on.. here ADD is stands for addition operation, DIV is for division, AVG is for average, SUB is for subtraction.. – Subodh Jan 03 '14 at 08:15
  • output will be like this: ====> SUB ( DIV ( ADD (2,5), 4.5 ), AVG (3,4) ) ====> SUB ( DIV (8 , 4.5 ), AVG (3,4) ) =====> SUB ( 1.77 , AVG (3,4) ) =====> SUB ( 1.77 , 3.5 ) =====> -1.73 – Subodh Jan 03 '14 at 08:20

1 Answers1

2

If what you are trying to do is break the expression into subexpressions and get the contents of a subexpression between parenthesis - you cannot do this with regular expressions. Regular expressions cannot handle the parenthesis matching problem.

You'd need to devise another algorithm to do that - a stack based approach (push on opening parenthesis, pop on closing parenthesis) could be one approach.

Here's a related question about this issue: Regular Expression to match outer brackets

However, you could use a regex to validate/parse leaf expressions (the ones with no nested expressions) in the expression tree, once you've got your expression broken down.

EDIT: while the above is true for regular expressions in general as a language (as taught in CS classes), libraries have made enhancements to the language to allow this. Perl has done this for a long time, and it seems it's possible in .NET as well. Here's a post explaining Balanced Matching in the .NET Regex implementation.

http://blogs.msdn.com/b/bclteam/archive/2005/03/15/396452.aspx

Community
  • 1
  • 1
Ronald Zarīts
  • 11,819
  • 8
  • 39
  • 42