这是一个面试问题，我在stackoverflow上或外部都没有找到任何令人满意的答案。问题陈述：
给定一个算术表达式，删除多余的括号。例如 ((a*b)+c) 应该变成 a*b+c
我可以想到一种将中缀表达式转换为后缀并将其转换回中缀的明显方法 - 但有更好的方法吗？
问问题
36672 次
7 回答
41
一对括号是必要的，当且仅当它们包含 X % X % ... % X 形式的无括号表达式，其中 X 是带括号的表达式或原子，并且 % 是二元运算符，并且如果至少有一个运算符% 的优先级低于直接附加到其任一侧括号表达式的运算符；或者如果它是整个表达式。所以例如在
q * (a * b * c * d) + c
周围的运算符是 {+, *} 并且括号内的最低优先级运算符是 *，因此括号是不必要的。另一方面，在
q * (a * b + c * d) + c
括号内的运算符 + 的优先级低于周围的运算符 *，因此它们是必要的。然而，在
z * q + (a * b + c * d) + c
括号不是必需的，因为外部 * 未附加到带括号的表达式。
为什么这是真的，如果表达式中的所有运算符 (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)
于 2013-08-23T12:52:47.700 回答
3
我刚刚想出了一个答案：
场地是：
1. the expression has been tokenized
2. no syntax error
3. there are only binary operators
输入：
list of the tokens, for example:
(, (, a, *, b, ), +, c, )
输出：
set of the redundant parentheses pairs (the orders of the pairs are not important),
for example,
0, 8
1, 5
请注意：集合不是唯一的，例如 ((a+b))*c，我们可以去掉外括号或内括号，但最终表达式是唯一的
数据结构：
a stack, each item records information in each parenthese pair
the struct is:
left_pa: records the position of the left parenthese
min_op: records the operator in the parentheses with minimum priority
left_op: records current operator
算法
1.push one empty item in the stack
2.scan the token list
2.1 if the token is operand, ignore
2.2 if the token is operator, records the operator in the left_op,
if min_op is nil, set the min_op = this operator, if the min_op
is not nil, compare the min_op with this operator, set min_op as
one of the two operators with less priority
2.3 if the token is left parenthese, push one item in the stack,
with left_pa = position of the parenthese
2.4 if the token is right parenthese,
2.4.1 we have the pair of the parentheses(left_pa and the
right parenthese)
2.4.2 pop the item
2.4.3 pre-read next token, if it is an operator, set it
as right operator
2.4.4 compare min_op of the item with left_op and right operator
(if any of them exists), we can easily get to know if the pair
of the parentheses is redundant, and output it(if the min_op
< any of left_op and right operator, the parentheses are necessary,
if min_op = left_op, the parentheses are necessary, otherwise
redundant)
2.4.5 if there is no left_op and no right operator(which also means
min_op = nil) and the stack is not empty, set the min_op of top
item as the min_op of the popped-up item
例子
示例一
((a*b)+c)
扫描到 b 后，我们有堆栈：
index left_pa min_op left_op
0
1 0
2 1 * * <-stack top
现在我们遇到第一个')'（在位置 5），我们弹出该项目
left_pa = 1
min_op = *
left_op = *
和预读运算符'+'，因为min_op优先级'*'>'+'，所以pair(1,5)是多余的，所以输出。然后扫描直到我们遇到最后一个'）'，此刻，我们有堆栈
index left_pa min_op left_op
0
1 0 + +
我们弹出这个项目（因为我们在 pos 8 处遇到 ')'），并预读下一个运算符，因为没有运算符并且在索引 0 处，没有 left_op，所以输出 pair(0, 8)
示例二
a*(b+c)
当我们遇到')'时，堆栈就像：
index left_pa min_op left_op
0 * *
1 2 + +
现在，我们在 index = 1 处弹出 item，将 min_op '+' 与 index 0 处的 left_op '*' 进行比较，我们可以发现 '(',')' 是必要的
于 2013-08-28T05:19:35.517 回答
1
如果表达式有效，则此解决方案有效。我们需要将运算符映射到优先级值。
一个。从数组的两端遍历，找出两端匹配的括号。令索引分别为 i 和 j。
湾。现在从 i 遍历到 j 并找出不包含在任何括号内的最低优先级运算符。
C。将此运算符的优先级与左括号左侧和右括号右侧的运算符进行比较。如果不存在这样的运算符，则将其优先级视为-1。如果运算符的优先级高于这两个，则去掉 i 和 j 处的括号。
d。继续步骤 a 到 c，直到 i<=j。
于 2014-05-06T18:25:18.460 回答
1
- 将一个空项压入堆栈
扫描令牌列表
2.1 如果token是操作数，忽略。
2.2 如果token是operator，将operator记录在left_op中，如果min_op为nil，设置min_op=this算子，如果min_op不是nil，将min_op与this算子比较，设置min_op为less的两个算子之一优先。
2.3 如果token是左括号，则压栈一项，left_pa=括号的位置。
2.4 如果token是右括号：
2.4.1 我们有一对括号（left_pa 和右括号）
2.4.2 弹出项目
2.4.3 预读下一个token，如果是算子，设置为右算子
2.4.4 比较item的min_op和left_op和right运算符（如果有的话），我们可以很容易的知道这对括号是否多余，并输出（如果min_op <left_op和right运算符中的任何一个） , 括号是必需的，如果 min_op = left_op，括号是必需的，否则多余）
2.4.5 如果没有left_op也没有right operator(也就是min_op = nil)且栈不为空，设置top item的min_op为弹出item示例的min_op
于 2016-06-25T08:48:41.333 回答
0
下面的代码实现了一个简单的解决方案。它仅限于+、-、*和/，但如果需要，它可以扩展以处理其他运算符。
#include <iostream>
#include <set>
#include <stack>
int loc;
std::string parser(std::string input, int _loc) {
std::set<char> support = {'+', '-', '*', '/'};
std::string expi;
std::set<char> op;
loc = _loc;
while (true) {
if (input[loc] == '(') {
expi += parser(input, loc + 1);
} else if (input[loc] == ')') {
if ((input[loc + 1] != '*') && (input[loc + 1] != '/')) {
return expi;
} else {
if ((op.find('+') == op.end()) && (op.find('-') == op.end())) {
return expi;
} else {
return '(' + expi + ')';
}
}
} else {
char temp = input[loc];
expi = expi + temp;
if (support.find(temp) != support.end()) {
op.insert(temp);
}
}
loc++;
if (loc >= input.size()) {
break;
}
}
return expi;
}
int main() {
std::string input("(((a)+((b*c)))+(d*(f*g)))");
std::cout << parser(input, 0);
return 0;
}
于 2017-06-12T04:55:53.803 回答
0
以防万一有人在寻找快速简便的解决方案时发现此问题：如果您的表达式已清理并且您的语言（或库）eval为您的表达式提供了函数，您可以尝试删除一对括号是否会改变值你的表情。如果是这样，您将不得不保留括号。如果没有，您可以删除它们。
但是，请记住，这当然不是一个有效的解决方案，而是“蛮力”路径。
这是 Python 中的一个示例性实现，适用于整数和内置eval：
def remove_brackets(term):
a = 0
while True:
# Find opening bracket
try:
a = term.index("(", a)
except ValueError:
# No (more) opening brackets found
break
# Find corresponding closing bracket
b = a
while True:
b = term.index(")", b + 1)
if term[a + 1:b].count("(") == term[a + 1:b].count(")"):
break
# Assemble new term by removing current pair of brackets
new_term = term[:a] + term[a + 1:b] + term[b + 1:]
# If new term produces a different value, keep term as it is and try with the next pair of brackets
if eval(term) != eval(new_term):
a += 1
continue
# Adopt new term
term = new_term
return term
示例调用：
>>> remove_brackets("1 + (2 * 3)")
'1 + 2 * 3'
>>> remove_brackets("1 + (2 * 3) / 4")
'1 + 2 * 3 / 4'
>>> remove_brackets("1 + (2 * 3) / 4 / (5 * 6)")
'1 + 2 * 3 / 4 / (5 * 6)'
于 2019-12-22T16:32:16.843 回答
-5
我认为您正在寻找如下图所示的算法。
这个算法“几乎”准备好了，因为一旦它变得越复杂，就会出现很多错误，它变得越复杂。我在这件事上的工作方式是“即时构建和编写代码”，这意味着对于最多 4 个括号，事情很容易。但是在表达变得更复杂之后，在纸上写下想法时，有些事情我无法预测。编译器会告诉我要纠正什么。如果我说不是我编写算法，而是（C#）编译器，那将不是谎言！到目前为止，我花了 1400 行。并不是说这些命令很难写。真正令人困惑的是他们的安排。您正在寻找的这个程序的特点是非常复杂。好吧，如果您需要任何主要想法，请告诉我，我会回复。
于 2018-02-01T17:32:02.040 回答