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

最后 return 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 来完成此操作。

如果您的输入具有更一般的形式，如果您想从 Whosebug 获得帮助，则需要更仔细地描述它。仔细的描述不能像 "here's an example" 这样的东西。它必须类似于 "here's a context free grammar that generates all the possible inputs".

Ocaml - return 个表达式

Ocaml - return number of expressions

count