Find specific node in "in-order tree traversal"

Question

I'm working to create my own shell.

I've created a lexer and a parser (which create a binary tree) for the user input. So for a command like this : cat main.c | ls | wc.

I got this tree :

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

So my tree traversal function (in Order) is like this:

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

   inorder(root->right);
}

My problem is when I'm on node "ls" or "wc", I don't know how to check if there is a pipe after and before the command.

Any idea ?

Answer 1

In your parse tree, pipes are nodes and commands are leaves. Pipes must have both left and right branches. When you go left from a pipe, the pipe you're at now is the out-pipe for the command you're going to. When you go right, the pipe you're at is the in pipe for the destination command.

So pass the in and out pipes as parameters. They point to NULL if there's no redirection for that command or to one of the | nodes.

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);
    }
}

Start at the root of the tree with inorder(root, NULL, NULL).