从前缀顺序表达式构造二叉树

Question

如何构造以下"前缀"顺序表达式的二叉树?

(- */8 + 5 1 4 + 3 - 5/18 6)

画这棵树有什么规则可循吗?

Answer 1

伪代码如下:

function MakeBinaryTree(expr):
  element = next element in expr
  if element is a number:
    return a leaf node of that number
  else: // element is an operator
    left = MakeBinaryTree(expr)
    right = MakeBinaryTree(expr)
    return a binary tree with subtrees left and right and with operator element

这里expr保留了一个内部指针，指向下一个元素的位置。