使用C中的fork()和管道进行前缀表示法计算，无需递归或堆栈(HW)

Question

我有一项任务，只使用fork（）和pipe（）计算前缀表示法。

不允许递归或使用堆栈。（这个算法很简单）

我花了三天时间运气不好。我知道fork（）和pipes（）是如何工作的，但我不能将它们组合在一起，使其像递归一样运行。

我写了一个递归函数，它很有趣。

  int poss; //global var
  int prefixNotationCalc(char tokens[30][30], int start) {
  char * token;
  poss = start;
  int op1, op2;
  token = tokens[poss];
  if (isOperator(token) == 0) {
      poss++;
      return atoi(token);
  } else {
    poss++;
    int op1 = prefixNotationCalc(tokens, poss);
    int op2 = prefixNotationCalc(tokens, poss);
    if (*token == '*') {
        return op1*op2;
    } else if (*token == '/') {
        return op1/op2;
    } else if (*token == '+') {
        return op1+op2;
    } else {
        return op1-op2;
    }      
  }
}

现在我尝试用fork（）和pipe（）来模拟这个逻辑。我写了非常大的代码，所以我不会在这里发布它。我只是想给你看看我的一些逻辑。

我创建了3个管道，也许还有其他一些，这不是我真正的问题：

int left_res[2]; (like op1 in recursion)
int right_res[2]; (like op2 in recursion)
int global_index[2]; (like op1 in recursion)

然后我遇到了一个问题。因为递归和fork（）之间的区别。递归：当调用递归时，函数从头开始。Fork：在我调用Fork（）的地方，子级和父级继续从它的当前位置工作

所以我想我需要循环进行，但后来我遇到了更多的问题。。

例如，对于该输入：+*+2 4 5--6 7 8

我的逻辑是：

for () {
   main process : + operator -> left_pid = fork(); waitpid(left_pid);
   -left_pid process : * operator -> left_pid = fork(); waitpid(left_pid);
   ----left_pid process : + operator -> left_pid = fork(); waitpid(left_pid);
   -------left_pid process : 2 NOT operator -> wrote [2] to pipe;
   ----parent waited for left_pid, continue and create right_pid = fork(); waitpid(right_pid);
   ----right_pid process : 4 NOT operator -> wrote [4] to pipe;
   ...
   ...
   ...
   when left and right processes closed, I can calculate sum of left_res & right_res in their common parent.
}

我的逻辑正确吗？也许没有办法用叉子做出这种行为？

这是我代码中很小的一部分：

   for (i = 0; i < tokensNumber; i++) {
    if (isOperator(tokens[i]) == 0) {
        /*
    Some code
    */
    } else {
        if ((childLeftId = fork()) == 0 || (childRightId = fork()) == 0) {
       /*
        Some code
        */
        } else {
            // wait for left child
            statusLeft = waitpid(childLeftId, &statusLeft, NULL);
    // wait for right child
            statusRight = waitpid(childRightId, &statusRight, NULL);
            /*
          Some code
    */
            if (*token == '*') {
                result = op1*op2;
            } else if (*token == '/') {
                result = op1/op2;
            } else if (*token == '+') {
                result = op1+op2;
            } else {
                result = op1-op2;
            }                
        }
    }
}    

在同一级别上运行fork（），并为两个子级运行一个公共ELSE部分，这对吗？也许我必须使用这个层次结构？

   for (i = 0; i < tokensNumber; i++) {
    if (isOperator(tokens[i]) == 0) {
        /*
    Some code
    */
    } else {
        if ((childLeftId = fork()) == 0) {
       /*
        Some code
        */
        } else {

            // wait for left child
            statusLeft = waitpid(childLeftId, &statusLeft, NULL);
    if ((childRightId = fork()) == 0) {
               /*
          Some code
       */
    } else {
       // wait for right child
               statusRight = waitpid(childRightId, &statusRight, NULL);
    }
            /*
          Some code
    */
            if (*token == '*') {
                result = op1*op2;
            } else if (*token == '/') {
                result = op1/op2;
            } else if (*token == '+') {
                result = op1+op2;
            } else {
                result = op1-op2;
            }                
        }
    }
}  

我尝试了两种方法，但都没有成功。。。

Answer 1

为了让您习惯伪代码，我将展示几种解决方案，从简单的递归版本到所需的迭代fork+pipe版本。

我假设定义了gettoken()函数，它一次返回一个令牌。波兰语表示法是递归评估的理想选择：

def pn_eval():
    token = gettoken()
    if token in OPERATORS: # token is an operator
        return OPERATORS[token](pn_eval(), pn_eval())
    return int(token) # token is a number

其中OPERATORS是哈希表：token->binop:

from operator import add, floordiv, mul, sub
OPERATORS = {'*': mul,
             '/': floordiv, # keep it integer
             '+': add,
             '-': sub}

用法：

print(pn_eval())

递归调用可以移动到使用管道传递结果的子进程：

from os import _exit, fdopen, fork, pipe
def pn_eval_fork_pipe(result_out, ischild=False):
    def return_(result):
        fdopen(result_out, 'w').write(str(result))
        (exit if not ischild else _exit)(0)
    token = gettoken()
    op = OPERATORS.get(token)
    if op is not None:
        return_(op(eval_subtree(), eval_subtree()))
    return_(int(token)) # number
def eval_subtree():
    result_in, result_out = pipe()
    if fork() == 0: # child process
        close(result_in) # unused
        pn_eval_fork_pipe(result_out, ischild=True)
    # parent process
    close(result_out) # unused
    return int(fdopen(result_in, 'r').read())

用法：

from sys import stdout
pn_eval_fork_pipe(stdout.fileno())

我们可以通过覆盖子进程中的结果输出管道来消除递归：

from os import _exit, close, fdopen, fork, pipe
def pn_eval_fork_pipe_iter(result_out_fd):
    def return_(result, orig_fd=result_out_fd): # earlier binding
        fdopen(result_out_fd, 'w').write(str(result))
        (exit if result_out_fd is orig_fd else _exit)(0) # late binding
    getresult = lambda fd: int(fdopen(fd, 'r').read())
    while True:
        token = gettoken()
        if not token: # EOF
            break
        op = OPERATORS.get(token)
        if op is not None: # token is an operator
            arg1_fd = pipe()
            if fork() == 0: # child
                close(arg1_fd[0]) # unused
                close(result_out_fd)
                result_out_fd = arg1_fd[1] # overwrite in child
            else: # parent
                close(arg1_fd[1]) # unused
                arg1 = getresult(arg1_fd[0])
                arg2_fd = pipe()
                if fork() == 0: # child
                    close(arg2_fd[0]) # unused
                    close(result_out_fd)
                    result_out_fd = arg2_fd[1] # overwrite in child
                else: # parent
                    close(arg2_fd[1])
                    arg2 = getresult(arg2_fd[0])
                    return_(op(arg1, arg2))
        else: # number
            return_(int(token))

用法：

from sys import stdout
pn_eval_fork_pipe_iter(stdout.fileno())

下面是gettoken()在Python中的一个示例实现。它假设输入是通过stdin:提供的

from os import close, read
from sys import stdin
def generate_tokens(r):
    buf = []
    while True:
        b = read(r, 1) # read one byte
        if not b: # EOF
            close(r)
            if buf:
               yield b''.join(buf).decode('ascii') # last token
            return
        elif not b.isspace(): # grow token
            buf.append(b)
        elif buf: # full token read
            yield b''.join(buf).decode('ascii')
            buf = []
tokens = generate_tokens(stdin.fileno())    
gettoken = lambda: next(tokens, None)

完整的C程序。

Answer 2

我不理解你的"逻辑"部分。

重写prefixNotationCalc（）可能为
int prefixNotationCalc（char tokens[30][30]，int start，int fd[2]）

您需要一个协议来通过管道返回您的int结果和新的int位置。
使用sprintf（"%d%d"）/写和读/scanf（"%d/d"）可能最简单？

调用此函数时，必须提供管道以及运行它的进程（用于此函数的fork）然后你通过孩子的管道接受你的答案（以及新的结束位置）。

不要从编写代码开始。编写伪代码以使算法正确第一把它写成递归的，但当你需要递归时调用，然后转到顶部（或使用循环）。

我认为您只需要一个管道，因为任何时候都只有一个进程在运行。所有其他人都在等着有人完成。我不确定多重管道的读取器/写入器在不同的时间可能需要多个管道，但如果您需要它们，只需在分叉和连接之前创建一个即可。（我没有尝试过；-）

Answer 3

J.F.Sebastian展示了很多代码，但也许要理解解决方案，一点代码会更容易。

可能将prefixNotationCalc（）重写为

int prefixNotationCalc(char tokens[30][30], int start, int FD[2])
TOP:
if (isOperator...) {
   if (!fork()) goto TOP; // child does left argument
   // get left  answer and new position via pipe
   if (!fork()) goto TOP; // child does right argument
   // get right answer and new position via pipe
   // combine left and right answers with operator
} else { // not an operator
  // compute answer (non operator is a number)
}
// return answer and position via pipe
// and exit... this is your loop exit and process exit