从数学表达式中删除多余的括号

Question

我想编写一个程序，接受后缀表达式并将其转换为中缀表达式，并且应从中缀表达式中删除所有多余的括号。

我已经编写了一个将后缀转换为中缀的程序，但问题是我不知道如何删除所有多余的括号。

例如，

((a*b)+(c*d))

和

a*b+c*d

之间没有区别，第一个中的括号是多余的。

我的想法是从最里面的括号开始，将括号内优先级最低的运算符与括号前后运算符的优先级进行比较，然后决定是否删除括号。

但问题是这个算法应该运行多远，另一个问题是我正在寻找一种时间复杂度较低的算法。

我已经阅读了 stackoverflow 上的一些相关帖子，但尚未找到任何解决方案。

Answer 1

我终于找到这个问题的答案了

precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
operators = ['-','+','*','/','^']

def leftNeedParenthesis(current: str, leftOperator: str):
    if(leftOperator == None):
        return False
    return precedence[current] > precedence[leftOperator]


def rightNeedParenthesis(current :str, rightOperator: str):
    if(rightOperator == None):
        return False
    if(precedence[current]>precedence[rightOperator]):
        return True
    elif(precedence[current]<precedence[rightOperator]):
        return False
    else:
        if(current == "-" and rightOperator == "-"):
            return True
        elif(current == "/" and rightOperator == "/"):
            return True
        elif(current == "^" and rightOperator == "^"):
            return True
        return False


def postfix_to_infix( postfix: str) -> str:
    stack = []
    for c in postfix:
        if c.isalnum():
            stack.append((c, None))
        else:
            (operand2, lastUsedOperator2) = stack.pop()
            (operand1, lastUsedOperator1) = stack.pop()

            if(leftNeedParenthesis(c,lastUsedOperator1)):
                operand1 = "("+operand1+")"

            if(rightNeedParenthesis(c, lastUsedOperator2)):
                operand2 = "("+operand2+")"

            stack.append((operand1+c+operand2, c))
    (result, _) = stack.pop()
    return result


postfix = input().replace(" ", "")
print(postfix_to_infix(postfix))