Python中前缀表示法转换为中缀表示法

Question

我正在写一个小计算器（使用前缀表示法），我想知道如何把前缀表示法转换成中缀表示法。目前我有一个函数，但它的表现有点奇怪，我不知道该怎么修复。所谓奇怪，就是当我输入 ['+', x, y] 时，它会返回 (() + x + () + y)，这让我很困惑。以下是我的代码。

def pre_in(read):
    #print read
    tempOp = read[0]
    body = read[1:]
    expr = []
    for i in range(len(body)-1):
        if not isinstance(body[i], list) and body[i] != " ":
            expr.append(str(body[i]))
            expr.append(tempOp)
        else:
            expr.append(str(pre_in(body[i])))
            expr.append(tempOp)
    try:
        if not isinstance(body[-1], list):
            expr.append(str(body[-1]))
        else:
            expr.append(str(pre_in(body[-1])))
    except:
        pass
    if expr != None: return "("+' '.join(expr)+")"

我哪里做错了呢？

Answer 1

虽然对于这种简单的解析和转换工作来说，可能有点过于复杂，但你可以考虑看看pyparsing这个工具。

Answer 2

如果你不打算自己开发这个算法，可以去这个页面看看。那里有两个链接，分别解释了中缀转后缀和后缀转中缀的算法。（另外，如果你想知道这些算法是怎么用javascript实现的，可以看看这个页面的源代码。）

Answer 3

其实你的代码运行得很好。

print pre_in ( ['+', 8, 9] )

结果是

(8 + 9)

编辑：
正如其他人所说的，或许你可以考虑使用栈。这里有一个简单的示例实现和一些例子（它会产生很多括号，但这些没关系）：

class Calculator:
    def __init__ (self):
        self.stack = []

    def push (self, p):
        if p in ['+', '-', '*', '/']:
            op1 = self.stack.pop ()
            op2 = self.stack.pop ()
            self.stack.append ('(%s %s %s)' % (op1, p, op2) )
        elif p == '!':
            op = self.stack.pop ()
            self.stack.append ('%s!' % (op) )
        elif p in ['sin', 'cos', 'tan']:
            op = self.stack.pop ()
            self.stack.append ('%s(%s)' % (p, op) )
        else:
            self.stack.append (p)

    def convert (self, l):
        l.reverse ()
        for e in l:
            self.push (e)
        return self.stack.pop ()

c = Calculator ()

print c.convert ( ['+', 8, 9] )
print c.convert ( ['!', 42] )
print c.convert ( ['sin', 'pi'] )
print c.convert ( ['+', 'sin', '/', 'x', 2, 'cos', '/', 'x', 3] )