1

我有一个类似于 Scheme 的树形图结构。我想使用 C 将它解析为一些内存表示并遍历它。

是否有任何库或解析器前端可以做到这一点？

编辑：

我已经解析了以下表达式

true && (false || true) ;
true ;
false || false

跟随（这是我的类似方案的树转储）

(PROG [(AndExp TVal(OrExp FValTVal)), TVal, (OrExp FValFVal)])

我想用 C 遍历它（我必须把它交给只使用 C 的其他人）。PROG 是一个标签；AndExp、OrExp 等是 &&、|| 的标记 ETC ..

4

2 回答 2

1

看起来这是S-Expression的一种形式。也许这个 S-Expression Parser可以根据您的需要进行修改。

于 2011-09-07T16:39:32.637 回答
1

我想我已经了解您的要求，但不太确定。

你有前缀表示法的表达式，因此这基本上是加载你在二叉树转储文件中的前缀表达式。

这是一个伪代码，描述了将表达式加载到树中的过程。

tree_node make_tree（字符串转储）
{
  tok1 = get_tok（转储）；
  tok2 = get_tok（转储）；
  tok3 = get_tok（转储）；

  if (tok1 == 操作数)
  {
    节点 = make_new_node_with (tok1);
    返回节点；
  }

  节点 = make_new_node_with (tok1);
  node->left = make_tree (tok2);
  node->right = make_tree (tok3);
  返回节点；
}

  • 递归调用1(AndExp TVal(OrExp FValTVal))

    tok1 =AndExp 创建一个新的 node1

    托克2 =TVal

    tok3 =(OrExp FValTVal)

  • 递归调用 2将TValnode2 返回到调用 1，调用 1 将其与 node1 的左指针链接。

  • 从调用 1递归调用 3。(OrExp FValTVal)

    tok1 =ORExp创建一个新的 node3

    托克2 =FVal

    tok3 =TVal

  • 递归调用 3 withFVal和call 4 withTVal分别返回 node4 和 node5 的操作数值，它们从调用 3 链接到 node3 的左右链接。

不再考虑子表达式，递归返回起点。你有树的根。

                         ( node1 )
                         |AndExp |
                         +---+---+
                             |
                +------------+------------+
                |                         |
            ( node2 )                ( node3 )
            | TVal  |                | ORExp |
            +---+---+                +---+---+
                                         |
                             +-----------+-----------+
                             |                       |
                         ( node4 )               ( node5 )
                         |  FVal |               |  TVal |
                         +---+---+               +---+---+

如果有两个以上的操作数，则可以通过向树节点添加附加链接来类似地进行处理。

对于转储文件中的每个表达式，用逗号分隔将有单独的树，创建后可以遍历这些树。

于 2011-09-07T16:26:31.833 回答