从算术表达式中删除冗余括号 [英] Remove redundant parentheses from an arithmetic expression

问题描述

这是一个面试问题，在Stackoverflow或者外面我没有找到满意的答案。问题陈述：

给定一个算术表达式，删除冗余括号。例如。
（（a * b）+ c）应该成为一个* b + c

我可以想到一个明显的方式将中缀表达式转换为后期修改并将其转换为中缀 - 但是有没有更好的方法？

解决方案

当且仅当它们包含X％X％...％X形式的未认可表达式时，需要一对括号，其中X是括号表达式或原子，％是二进制运算符，如果至少有一个运算符％的优先级低于直接附加到其任意一侧的括号表达式的运算符;或者如果是整个表达式。例如在

  q *（a * b * c * d）+ c 
  / pre> 
 
 
周围的运算符是{+，*}，括号内的最低优先级运算符是*，所以括号是不必要的。另一方面，在
  q *（a * b + c * d）+ c 
  
圆括号内的优先级较低的运算符+与周围的运算符*相同，因此它们是必需的。但是，在
  z * q +（a * b + c * d）+ c 
  
括号不是必需的，因为外部*未附加到括号中的表达式。
 
 
为什么是这样的：如果一个表达式（X％X％...％X）内的所有运算符都比周围运算符具有更高的优先级，那么内部运算符无论如何先排列，即使括号被删除
 
 
 
所以，您可以通过此算法直接检查任何一对匹配的括号，以实现冗余：
让R为右括号右边的操作符，否则为nil 
如果L为nil且R为nil： 
冗余
否则：
扫描括号之间的未认可的运算符
令X为最低优先级运算符
如果X的优先级低于L或R：
不冗余
否则：
冗余
  

您可以重复此操作，删除冗余对，直到所有剩余的对都是非冗余的。

示例：

 （（a * b）+ c *（e + f ）
  

（从左到右处理对）：

 （（a * b）+ c *（e + f））L = nil R = nil  - >冗余
 ^ ^ 
（a * b）+ c *（e + f）L = nil R = nil  - >冗余
 ^ ^ L = nil R = + X = *  - >冗余
 a * b + c *（e + f）L = * R = nil X = +  - 不冗余
 ^ ^ 
  

最终结果：

  a * b + c *（e + f）
  

This is an interview question, for which I did not find any satisfactory answers on stackoverflow or outside. Problem statement:

Given an arithmetic expression, remove redundant parentheses. E.g. ((a*b)+c) should become a*b+c

I can think of an obvious way of converting the infix expression to post fix and converting it back to infix - but is there a better way to do this?

解决方案

A pair of parentheses is necessary if and only if they enclose an unparenthesized expression of the form X % X % ... % X where X are either parenthesized expressions or atoms, and % are binary operators, and if at least one of the operators % has lower precedence than an operator attached directly to the parenthesized expression on either side of it; or if it is the whole expression. So e.g. in

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

the surrounding operators are {+, *} and the lowest precedence operator inside the parentheses is *, so the parentheses are unnecessary. On the other hand, in

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

there is a lower precedence operator + inside the parentheses than the surrounding operator *, so they are necessary. However, in

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

the parentheses are not necessary because the outer * is not attached to the parenthesized expression.

Why this is true is that if all the operators inside an expression (X % X % ... % X) have higher priority than a surrounding operator, then the inner operators are anyway calculated out first even if the parentheses are removed.

So, you can check any pair of matching parentheses directly for redundancy by this algorithm:

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

You can iterate this, removing redundant pairs until all remaining pairs are non-redundant.

Example:

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

(Processing pairs from left to right):

((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
               ^     ^

Final result:

a * b + c * (e + f)

这篇关于从算术表达式中删除冗余括号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！