使用fork（）和C中的pipe道进行前缀符号计算，无需recursion或堆栈（HW）

为了让你习惯于伪代码，我将展示几个解决方案，从简单的递归版本到所需的迭代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是散列表：令牌 – > 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()) 

下面是Python中gettoken()的一个示例实现。 它假设输入是通过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程序 。

我不明白你的“逻辑”部分。

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

你需要一个协议来通过管道返回你的int结果和新的int位置。
使用sprintf（“％d％d”）/ write和read / sscanf（“％d％d”）最简单吗？

当你调用这个函数时，你必须提供管道和进程来运行它（一个fork这个函数），并且你通过管道接受你的回答（和新的结束位置）。

不要从编写代码开始。 编写伪代码，让您的算法先行。 写它就好像是递归的，但当你需要递归调用，然后到顶部（或使用循环）。

我认为你只需要一个管道，因为任何时候只有一个进程正在运行。 所有其他人都在等待某人完成。 我不确定在不同的时间管道的多个阅读器/作者可能需要多个管道，但是如果你需要它们，只需在分叉和连接之前按照预期创建一个管道。 （我没有尝试这个;-)

JF塞巴斯蒂安显示了很多代码，但也许理解解决方案，一个小代码会更容易。

重写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