RPN转中缀最少括号：优先级与右孩子非结合运算

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• token为有符号十进制整数或二元+−*/；乘除同优先且左结合，除法为数学有理除，非整除/浮点。
• 要求删除语法不必要括号但不重排/改写算子；除零表达式无定义。负整数按数学或Python类语法解释，不产生C/C++源码。

解题路线

1. 扫描RPN遇整数入栈，运算符弹right再left，保存生成文本与根运算优先级。必须两操作数，最终恰一表达式。
2. child优先级低于parent必括；left同级默认左结合可不括。right同级时减法/除法需括以保留分组；加法/乘法在精确有理数语义下可安全展平同级运算。
3. 若要求完全保留AST而非数值语义，a+(b+c)也要括；若是整数截断除法或浮点，a*(b/c)≠a*b/c一般不成立，必须重新定义规则。

手动走一遍

2,1,+,3,*→(2+1)*3；4,13,5,+,/→4/(13+5)。a−(b−c)右孩子同级不能去括；(a−b)−c可写a−b−c。不通过代数改成a−b+c绕过合同。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def infix(tokens):
    precedence={'+':1,'-':1,'*':2,'/':2};stack=[]
    for token in tokens:
        if token not in precedence:
            int(token)  # Training grammar uses signed integer atoms.
            stack.append((token,3))
            continue
        if len(stack)<2:raise ValueError("missing operand")
        right,rp=stack.pop();left,lp=stack.pop();level=precedence[token]
        if lp<level:left='('+left+')'
        if rp<level or rp==level and token in ('-','/'):right='('+right+')'
        stack.append((left+token+right,level))
    if len(stack)!=1:raise ValueError("invalid RPN")
    return stack[0][0]

复杂度

栈深O(tokens)。当前Python字符串每次拼接可能复制整个子表达式，长偏链最坏O(L²)时间/空间峰值O(L)常见；用AST后一次渲染可降至O(L)，L输出字符数。

易错点与追问

容易失分的边界

• 弹栈顺序相反会颠倒减除操作。
• 只看低优先级而忽略右同级减/除会改变结果。

继续深挖

• 如果使用向零截断整数除法，哪些安全去括规则必须收紧？
• 用AST生成token stream如何避免反复复制？