从算术表达式中删除多余的括号

Question

这是一个面试问题,我没有在stackoverflow或外部找到任何令人满意的答案.问题陈述:

给定算术表达式,删除多余的括号.例如((a*b)+ c)应该变成a*b + c

我可以想到一种将中缀表达式转换为后置修复并将其转换回中缀的明显方法 - 但是有更好的方法吗？

Answer 1

当且仅当它们包含X%X%...%X形式的未表示的表达式时,必须使用一对括号,其中X是带括号的表达式或原子,%是二元运算符,并且如果至少有一个运算符%的优先级低于直接附加到其两侧的括号表达式的运算符; 或者如果它是整个表达.所以例如在

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

周围的运算符是{+,*},括号内的最低优先级运算符是*,所以括号是不必要的.另一方面,在

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

括号内的优先级运算符+低于周围的运算符*,因此它们是必需的.但是,在

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

括号不是必需的,因为outer*没有附加到带括号的表达式.

为什么这是真的如果表达式中的所有运算符(X%X%...%X)具有比周围运算符更高的优先级,那么即使删除了括号,也无论如何都要先计算出内部运算符.

因此,您可以通过此算法直接检查任何一对匹配的括号以获得冗余:

Let L be operator immediately left of the left parenthesis, or nil
Let R be operator immediately right of the right parenthesis, or nil
If L is nil and R is nil:
  Redundant
Else:
  Scan the unparenthesized operators between the parentheses
  Let X be the lowest priority operator
  If X has lower priority than L or R:
    Not redundant
  Else:
    Redundant

您可以对此进行迭代,删除冗余对,直到所有剩余对都是非冗余的.

例:

((a * b) + c * (e + f))

(从左到右处理对):

((a * b) + c * (e + f))   L = nil R = nil --> Redundant
^                     ^   
 (a * b) + c * (e + f)    L = nil R = nil --> Redundant
 ^     ^                  L = nil R = + X = * --> Redundant
  a * b  + c * (e + f)    L = * R = nil X = + --> Not redundant
               ^     ^

最后结果:

a * b + c * (e + f)