Return number of expressions

I got this string

let reg = "(((T . (A . G)) + (T . C)) . (A + (C + (G* . T)))*)";;

For the given string I want to recursively count how many expressions in the form (expr simbol expr)->(A + C) exist in the string "reg". All possible values

(A . G);
(T . (A . G));
(T . C);
((T . (A . G)) + (T . C));
(G* . T);
(C + (G* . T));
(A + (C + (G* . T)));
(((T . (A . G)) + (T . C)) . (A + (C + (G* . T)))*)

and in end return 8;

I am not able to establish a stop condition for the recursive function. Any suggestion?

Solution

I can't really answer because (IMHO) your question isn't specific enough. To get a good answer you need to describe the possible inputs and the desired results very carefully.

It's not even clear whether the desired result is just a number (8 in your example), or if it should include an enumeration of all the subexpressions.

As I pointed out in the comments, if all the expressions are parenthesized then you don't need to work very hard to count them. You can simply count the number of left parentheses. You can check that this works for your example.

 let count_lpar s =
     let rec icount accum index =
         if index >= String.length s then
             accum
         else
             let accum' = if s.[index] = '(' then accum + 1 else accum in
             icount accum' (index + 1)
     in
     icount 0 0

Here's how it works on your example string:

val count_lpar : string -> int = <fun>
# count_lpar "(((T . (A . G)) + (T . C)) . (A + (C + (G* . T)))*)";;
- : int = 8

The helper function icount is, indeed, a recursive function. The stop condition is that it reaches the end of the string.

If you need to enumerate the expressions, again assuming that the expressions are always parenthesized, then you can do this by locating the matching right parenthesis of every left parenthesis. You can do this by counting +1 for every left parenthesis and -1 for every right parenthesis and scanning until the count reaches 0.

If your input has a more general form, you need to describe it more carefully if you want to get help from StackOverflow. A careful description can't be something like "here's an example". It would have to be something like "here's a context free grammar that generates all the possible inputs".