如何将后缀（逆波兰表示法）表达式转换为带最少括号的中缀表达式

核心算法思路 #

要实现最少括号的转换，关键是根据运算符优先级和结合性来判断是否需要给子表达式加括号，步骤如下：

• 初始化一个栈，用于存储操作数或已处理好的子表达式（每个元素要记录表达式内容和对应的运算符）
• 遍历后缀表达式的每个符号：
  1. 如果是操作数，直接压入栈
  2. 如果是运算符，从栈中弹出两个元素：先弹出的是右操作数，后弹出的是左操作数
  3. 判断左、右操作数是否需要加括号：
     • 左操作数需要加括号：左操作数是表达式（非单纯数字），且其运算符优先级低于当前运算符，或优先级相同但当前运算符是右结合（比如幂运算）
     • 右操作数需要加括号：右操作数是表达式（非单纯数字），且其运算符优先级低于当前运算符，或优先级相同且当前运算符是左结合（比如减法、除法）
  4. 将拼接好的带必要括号的表达式压入栈
• 遍历结束后，栈顶元素就是最终的中缀表达式

JavaScript 实现 #

function postfixToInfix(rpn) {
    // 定义运算符优先级（数值越高优先级越高）和结合性
    const ops = {
        '+': { precedence: 1, associativity: 'left' },
        '-': { precedence: 1, associativity: 'left' },
        '*': { precedence: 2, associativity: 'left' },
        '/': { precedence: 2, associativity: 'left' },
        '^': { precedence: 3, associativity: 'right' },
        '**': { precedence: 3, associativity: 'right' } // 兼容两种幂运算写法
    };

    // 预处理：替换^为**，分割符号并过滤空值
    const tokens = rpn.replace(/\^/g, '**').split(/\s+/).filter(token => token.trim() !== '');
    const stack = [];

    for (const token of tokens) {
        if (!isNaN(parseFloat(token)) && isFinite(token)) {
            // 操作数入栈，保存表达式和对应的运算符（null表示是纯数字）
            stack.push({ expr: token, op: null });
        } else if (ops.hasOwnProperty(token)) {
            if (stack.length < 2) {
                throw new Error(`无效的后缀表达式：${rpn}`);
            }
            // 弹出右、左操作数
            const right = stack.pop();
            const left = stack.pop();
            const currentOp = ops[token];

            // 判断左操作数是否需要加括号
            let leftExpr = left.expr;
            if (left.op !== null) {
                const leftOp = ops[left.op];
                if (leftOp.precedence < currentOp.precedence || 
                    (leftOp.precedence === currentOp.precedence && currentOp.associativity === 'right')) {
                    leftExpr = `(${leftExpr})`;
                }
            }

            // 判断右操作数是否需要加括号
            let rightExpr = right.expr;
            if (right.op !== null) {
                const rightOp = ops[right.op];
                if (rightOp.precedence < currentOp.precedence || 
                    (rightOp.precedence === currentOp.precedence && currentOp.associativity === 'left')) {
                    rightExpr = `(${rightExpr})`;
                }
            }

            // 拼接新表达式并入栈
            const newExpr = `${leftExpr} ${token} ${rightExpr}`;
            stack.push({ expr: newExpr, op: token });
        } else {
            throw new Error(`不识别的符号：${token}`);
        }
    }

    if (stack.length !== 1) {
        throw new Error(`无效的后缀表达式：${rpn}`);
    }
    return stack[0].expr;
}

// 测试示例
console.log(postfixToInfix("3 4 + 2 *")); // 输出 (3 + 4) * 2
console.log(postfixToInfix("3 4 2 ^ +")); // 输出 3 + 4 ^ 2
console.log(postfixToInfix("10 6 9 3 + -11 * / * 17 + 5 +")); // 输出 10 * (6 / ((9 + 3) * -11)) + 17 + 5

Python 实现 #

def postfix_to_infix(rpn):
    # 定义运算符优先级和结合性
    ops = {
        '+': {'precedence': 1, 'associativity': 'left'},
        '-': {'precedence': 1, 'associativity': 'left'},
        '*': {'precedence': 2, 'associativity': 'left'},
        '/': {'precedence': 2, 'associativity': 'left'},
        '^': {'precedence': 3, 'associativity': 'right'},
        '**': {'precedence': 3, 'associativity': 'right'}
    }

    # 预处理分割符号，兼容负数
    tokens = rpn.replace('^', '**').split()
    stack = []

    for token in tokens:
        # 判断是否为数字（包括整数、小数、负数）
        if token.replace('.', '', 1).isdigit() or (token.startswith('-') and token[1:].replace('.', '', 1).isdigit()):
            stack.append({'expr': token, 'op': None})
        elif token in ops:
            if len(stack) < 2:
                raise ValueError(f"无效的后缀表达式：{rpn}")
            right = stack.pop()
            left = stack.pop()
            current_op = ops[token]

            # 判断左操作数是否需要加括号
            left_expr = left['expr']
            if left['op'] is not None:
                left_op = ops[left['op']]
                if left_op['precedence'] < current_op['precedence'] or \
                   (left_op['precedence'] == current_op['precedence'] and current_op['associativity'] == 'right'):
                    left_expr = f"({left_expr})"

            # 判断右操作数是否需要加括号
            right_expr = right['expr']
            if right['op'] is not None:
                right_op = ops[right['op']]
                if right_op['precedence'] < current_op['precedence'] or \
                   (right_op['precedence'] == current_op['precedence'] and current_op['associativity'] == 'left'):
                    right_expr = f"({right_expr})"

            new_expr = f"{left_expr} {token} {right_expr}"
            stack.append({'expr': new_expr, 'op': token})
        else:
            raise ValueError(f"不识别的符号：{token}")

    if len(stack) != 1:
        raise ValueError(f"无效的后缀表达式：{rpn}")
    return stack[0]['expr']

# 测试示例
print(postfix_to_infix("3 4 + 2 *"))  # 输出 (3 + 4) * 2
print(postfix_to_infix("3 4 2 ^ +"))  # 输出 3 + 4 ^ 2
print(postfix_to_infix("10 6 9 3 + -11 * / * 17 + 5 +"))  # 输出 10 * (6 / ((9 + 3) * -11)) + 17 + 5

你原有代码的问题分析 #

你的代码存在几个关键逻辑漏洞：

1. 错误使用result数组而非栈结构：应该用栈保存每个阶段的子表达式并关联对应的运算符，才能准确判断括号需求，而不是直接拼接字符串
2. 括号判断规则不完善：friends对象的规则没有覆盖优先级和结合性的所有场景，比如幂运算的右结合性、减法/除法的左结合性都没考虑到
3. 栈的使用逻辑混乱：你用stack存储运算符，但没有关联到对应的子表达式，无法正确回溯判断括号是否必要

内容的提问来源于stack exchange，提问作者Chief VOLDEMORT