python - 用递归求解完全括号表达式

Question

我在想出一个可以求解完全括号方程的递归方法时遇到了麻烦......例如 ((3+2)/(1+4))。我能够想出一个递归解决方案来使用递归来解决像 +*+3421 这样的中缀表达式，但是对于像 ((3+2)/(1+4)) 我有点卡住了。

def evalPrefix(exp):
    it = iter(exp)
    return evalPrefixInner(it)

def evalPrefixInner(it):
    item = it.next()
    if isInt(item):
        return int(item)
    else: 
        operand1 = evalPrefixInner(it)
        operand2 = evalPrefixInner(it)
        return execute(item, operand1, operand2)

Answer 1

你的语法是:

expr ::= int | ( expr op expr )

正确吗？

所以，忽略错误检查，比如...

def evalExpr(it):
    item = it.next()
    if isInt(item):
        return int(item)
    else: 
        //item should = lparen
        operand1 = evalExpr(it)
        op = it.next()        
        operand2 = evalExpr(it)
        rparen = it.next() 
        return execute(op, operand1, operand2)