从后缀表达式到无冗余括号的中缀表达式转换指南

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

def leftNeedParenthesis(current: str, leftOperator: str):
    # 如果左操作数没有关联的运算符（即它本身是一个操作数，或整个表达式的左边界），则不需要括号。
    if leftOperator is None:
        return False
    # 如果当前运算符的优先级高于左操作数的最外层运算符，则左操作数需要括号。
    # 例如：(a+b)*c，当处理*时，左操作数是a+b，其最外层运算符是+。*的优先级高于+，所以a+b需要括号。
    return precedence[current] > precedence[leftOperator]

def rightNeedParenthesis(current: str, rightOperator: str):
    # 如果右操作数没有关联的运算符（即它本身是一个操作数，或整个表达式的右边界），则不需要括号。
    if rightOperator is None:
        return False

    # 情况一：当前运算符优先级高于右操作数的最外层运算符。
    # 例如：a*(b+c)，当处理*时，右操作数是b+c，其最外层运算符是+。*的优先级高于+，所以b+c需要括号。
    if precedence[current] > precedence[rightOperator]:
        return True
    # 情况二：当前运算符优先级低于右操作数的最外层运算符。
    # 例如：a+b*c，当处理+时，右操作数是b*c，其最外层运算符是*。+的优先级低于*，所以b*c不需要括号。
    elif precedence[current] < precedence[rightOperator]:
        return False
    # 情况三：当前运算符与右操作数的最外层运算符优先级相等。
    # 此时需要考虑结合性。
    else:
        # 减法是左结合的：a - b - c 等价于 (a - b) - c。
        # 当处理第一个-时，左操作数是a，右操作数是b-c。b-c需要括号。
        if current == "-" and rightOperator == "-":
            return True
        # 除法是左结合的：a / b / c 等价于 (a / b) / c。
        # 当处理第一个/时，左操作数是a，右操作数是b/c。b/c需要括号。
        elif current == "/" and rightOperator == "/":
            return True
        # 幂运算是右结合的：a ^ b ^ c 等价于 a ^ (b ^ c)。
        # 当处理第一个^时，左操作数是a，右操作数是b^c。b^c需要括号。
        elif current == "^" and rightOperator == "^":
            return True
        # 对于其他相同优先级的运算符（如加法+和+，乘法*和*），不需要额外括号。
        # 例如：a+b+c 等价于 (a+b)+c。当处理第一个+时，右操作数是b+c，不需要括号。
        # 例如：a*b*c 等价于 (a*b)*c。当处理第一个*时，右操作数是b*c，不需要括号。
        return False

def postfix_to_infix(postfix: str) -> str:
    stack = [] # 栈用于存储 (中缀表达式字符串, 最外层运算符)
    for c in postfix:
        if c.isalnum(): # 如果是操作数（字母或数字）
            stack.append((c, None)) # 操作数本身没有运算符，用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

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

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

def rightNeedParenthesis(current :str, rightOperator: str):
    if rightOperator is 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_expression = input("请输入后缀表达式 (无空格): ").replace(" ", "")
# print(f"转换后的中缀表达式: {postfix_to_infix(postfix_expression)}")

# 示例测试
print(f"ab*cd*+ -> {postfix_to_infix('ab*cd*+')}") # 预期: a*b+c*d
print(f"abc++ -> {postfix_to_infix('abc++')}")     # 预期: a+b+c
print(f"ab-c- -> {postfix_to_infix('ab-c-')}")     # 预期: (a-b)-c
print(f"abc^- -> {postfix_to_infix('abc^-')}")     # 预期: a-b^c
print(f"ab^c^ -> {postfix_to_infix('ab^c^')}")     # 预期: a^(b^c)
print(f"a bc+*d- -> {postfix_to_infix('abc+*d-'.replace(' ', ''))}") # 预期: a*(b+c)-d