c - 在 "in-order tree traversal"中查找特定节点

Question

我正在努力创建自己的 shell。

我已经为用户输入创建了一个词法分析器和一个解析器(它们创建了一个二叉树)。所以对于这样的命令:cat main.c | ls |厕所.

我得到了这棵树:

           "|"
           / \
          /   \
         /     \
 "cat main.c"   "|"
                / \
               /   \
             "ls"  "wc"

所以我的树遍历函数(按顺序)是这样的:

inorder(root)
{
   inorder(root->left);
   //exec cmd and do redirection

   inorder(root->right);
}

我的问题是当我在节点“ls”或“wc”上时，我不知道如何检查命令前后是否有管道。

有什么想法吗？

Answer 1

在你的解析树中，管道是节点，命令是叶子。管道必须有左分支和右分支。当您从管道向左走时，您现在所在的管道就是您要执行的命令的导出管道。当你向右走时，你所在的管道就是目标命令的 in 管道。

所以传入和传出管道作为参数。如果该命令没有重定向或指向 | 节点之一，它们将指向 NULL。

inorder(root, in, out)
{
    if (root is cmd) {
        execute(root, in, out);
    } else {
        // root is pipe
        inorder(root->left, in, root);
        redirect(in, out);
        inorder(root->right, root, out);
    }
}

使用 inorder(root, NULL, NULL) 从树的根开始。