我怀疑如果您从表达式的中缀表达式“树”开始并在您真的想要时将其转换为 RPN 格式，则仅生成有效表达式可能会更容易。

每个节点都可以是二元运算符$O$或一个数字$N$.$O$根据定义，节点不能是叶节点，因为它们恰好需要两个子节点，并且$N$节点必须是叶节点，因为它们不能有任何子节点。

因为我们知道$O$节点永远不是叶子和和$N$节点总是叶子，我们甚至不需要正确地标记它们。在这一点上，我们已经将问题转化为我们需要生成所有可能的完整二叉树的问题$N$叶子（或者，我们想要所有可能的完整二叉树$O+N=2N-1$节点总数）。通过完整的二叉树，我的意思是任何人都不可能$O$节点只有 1 个孩子；每个节点要么恰好有 2 个子节点，要么没有。

有一种递归算法可用于为您生成这些树。这是一个 Python 实现示例。

def gen_full_bst(N):
    # N >= 1 is the number of leaf (number) nodes
    # the string 'N' denotes a leaf node, and a tuple denotes an operator node.
    if N == 1:
        yield 'N'
    
    # allow N-n leaf nodes to belong to the left child, and the remainder belongs to the right child
    for n in range(1, N):
        left_N = N - n
        right_N = N - left_N
        for left_child in gen_full_bst(left_N):
            for right_child in gen_full_bst(right_N):
                yield (left_child, right_child)

要将中缀树树转换为 RPN 格式，只需使用 BST 的后序遍历。当一个节点被“访问”（不仅仅是遍历）时，将该节点添加到 RPN 堆栈的底部。

def bst_to_rpn(tree):
    if tree == 'N':
        return 'N'
    return f'{bst_to_rpn(tree[0])}{bst_to_rpn(tree[1])}O'

测试这个$N=4$：

for tree in gen_full_bst(4):
    print(bst_to_rpn(tree))

生产

NNONONO
NNNOONO
NNONNOO
NNNONOO
NNNNOOO

作为旁注，我实现的方式gen_full_bst没有任何结果的中间缓存。例如，总共gen_full_bst(4)调用gen_full_bst(2)6 次。您可以实现一个查找表，其中存储预先计算的值，然后重新使用以加速计算，但会占用内存空间。从我电脑上的一些基本测试来看，非缓存版本似乎可以达到大约$N=14$.