Ocaml-返回表达式数

Question

我有这个字符串

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

对于给定的字符串，我想递归计算字符串“ reg”中以（expr simbol expr）->（A + C）形式存在多少个表达式。所有可能的值

(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)))*) 

最后返回8；

我无法为递归函数建立停止条件。有什么建议吗？

Answer 1

我无法真正回答，因为（恕我直言）您的问题不够具体。为了获得良好的答案，您需要非常仔细地描述可能的输入和期望的结果。

甚至不清楚所需的结果是否只是一个数字（在您的示例中为8），或者是否应包括所有子表达式的枚举。

正如我在评论中指出的那样，如果所有表达式都用括号括起来，那么您无需费劲去计算它们。您可以简单地计算左括号的数量。您可以检查它是否适用于您的示例。

 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

这是您的示例字符串的工作方式：

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

辅助函数icount实际上是一个递归函数。停止条件是它到达字符串的末尾。

如果需要枚举表达式，再次假设表达式始终带有括号，那么可以通过找到每个左括号的匹配右括号来做到这一点。您可以通过为每个左括号计数+1和为每个右括号计数-1并扫描直到计数达到0来执行此操作。

如果您输入的内容具有更一般的形式，则要从StackOverflow获得帮助，需要更仔细地描述它。仔细的描述不会像“这是一个例子”。它必须像“这是一个上下文无关的语法，它会生成所有可能的输入”。