C# RegEx for nested function

Question

I am having trouble to evaluate the following expression using RegEx in C#.

add(1, 2, sub(4, add(1, 2)), div(4, 2))

which will be evaluated as below.

=> add(1, 2, sub(4, 3), 2)
=> add(1, 2, 1, 2)
=> 6

Functions are picked up from regex expression and parameters are of any numbers. Thanks in advance.

Here is what I am trying:

class Program
{
    static Regex extractFuncRegex = new Regex(@"(?<func>add|sub|div)\s*\((?<params>.*)\)$", RegexOptions.ExplicitCapture);
    static Regex extractArgsRegex = new Regex(@"([^,]+\(.+?\))|([^,]+)");


    static void Main(string[] args)
    {
        string test = @"add(1, 2, sub(4, add(1, 2)), div(4, 2))";
        Console.WriteLine(ParseFunction(test));
        Console.ReadLine();
    }

    static string ParseFunction(string expr)
    {
        expr = extractFuncRegex.Replace(expr, (m) =>
            {
                string func = m.Groups["func"].Value;
                string param = m.Groups["params"].Value;

                Console.WriteLine("Function: {0}", func);

                MatchCollection paramCollection = extractArgsRegex.Matches(param);
                List<string> pa = new List<string>();

                foreach (Match item in paramCollection)
                {
                    string p = item.Groups[0].Value.Trim();
                    Console.WriteLine("\tParameter: {0}", p);

                    if (extractFuncRegex.IsMatch(p))
                        p = ParseFunction(p);

                    pa.Add(p);
                }

                switch (func)
                {
                    case "add":
                        float a1 = 0;
                        foreach (string item in pa)
                            a1 += float.Parse(item);
                        return a1.ToString();

                    case "sub":
                        return (float.Parse(pa[0]) - float.Parse(pa[1])).ToString();

                    case "div":
                        return (float.Parse(pa[0]) / float.Parse(pa[1])).ToString();

                    default:
                        return expr;
                }
            });

        return expr;
    }
}

If you debug, you can see, there is a problem to parse

sub(4, add(1, 2))

Answer 1

You've clearly done good work on this so far so I'm not going to say "don't use regular expressions, throw it away and use something else" - I'm going to show how you can make your code work with minimal changes.

Firstly, change your extractFuncRegex to

@"(?<func>add|sub|div)\s*\((?<params>[^()]*)\)"

I have replaced the .* in the params group with [^()]*. this means that it will only only match a function call which doesn't contain any other function calls - because that's the only thing we can work on directly. I've also removed the trailing $ to make it work.

The trick now is to call either ParseFunction or extractFuncRegex.Replace until no replacements are made. For example, you could put the call to extractFuncRegex.Replace in a loop like so (untested):

bool doneWork = true;
while (doneWork)
{
    doneWork = false;
    expr = extractFuncRegex.Replace(expr, (m) =>
        {
            doneWork = true;
            ...
        });
}
...

Using this, you get a sequence of gradually-simplified expressions. At each stage, only the deepest function calls are replaced.

add(1, 2, sub(4, add(1, 2)), div(4, 2))
                 |--------   |--------
add(1, 2, sub(4, 3        ), 2        )
          |----------------
add(1, 2, 1                , 2        )
|--------------------------------------
6