去掉多余的括号。

Question

问题：

从字符串中删除多余的括号。
例如：

    ((a+b))*c       => (a+b)*c  
    (a+b)+c         => (a+b)+c  
    ((a+b)/(c+d))   => ((a+b)/(c+d))   
    (a+(((b-c)))*d) => (a+(b-c)*d)  and so on.

我想到了以下解决方案：
方法：我扫描字符串并使用一个映射记录开括号的索引以及它是否多余（默认情况下是多余的）。如果我找到了一个闭括号，我会检查映射中对应的开括号，如果它是多余的，则删除两个括号。

void removeExtraParentheses(string& S){
  map<int, bool> pmap;
  for(int i = 0; i < S.size(); i++){
    map<int, bool>::iterator it;
    if(S.at(i) == '('){
        pmap[i] = true;
    }
    else if(S.at(i) == ')'){
        it = pmap.end();
        it--;
        if(!(*it).second){
            pmap.erase(it);
        }
        else{
            S.erase(S.begin() + i);
            S.erase(S.begin() + (*it).first);
            pmap.erase(it);
            i = i - 2;
        }
    }
    else{
        if(!pmap.empty()){
            it = pmap.end();
            it--;
            (*it).second= false;
        }
    }
  }
}  

时间复杂度：O(n2) 空间复杂度：O(n) 我对我的解决方案不太满意，因为我使用了额外的存储空间，并且需要平方级别的时间。

能否在O(n)时间和O(1)空间内完成？如果不能，那么最好的解决方案是什么？

- NGambit

---

当你说“额外的括号”时，你是指只有 (( 的地方，还是指数学不需要它们的地方？例如 (a+b)+c 也会得到 a+b+c，因为加法是可交换的。如果不是这样，请使用字符串替换将“((（”替换为“（”，将“）））”和“））”替换为“）”。 - Frank Thomas

我认为我给出的第二个示例输入可以消除您的疑虑。我不确定“只需使用字符串替换将“((（”替换为“（”，将“）））”和“））”替换为“）”是否有效。 - NGambit

@FrankThomas 首先，这些示例表明数学并不是关键因素，只有双括号被替换。其次，这种方法会失败。想一想它会对 ((a + b) + (c + d)) 做什么。 - Jasper

@jasper，我相信它会返回（a+b）+（c+d）。很好的观点，这些也可以被删除。 - Frank Thomas

@FrankThomas 您提出了一个有趣的问题。对于浮点类型（以及可能也适用于有符号整数类型，但在任何通常的架构上都不是这种情况），加法是 不 结合的，并且 (a + b) + c 和 a + b + c 是相同的，但对于 a + (b + c) 的情况，您需要使用括号。或者他的问题可能说明不充分：在 Windows 机器或大多数 Unix 上，在最后一种情况下，您不需要 int 的括号，但是在某些奇特的机器上，您可能需要。 - James Kanze

Answer 1

构建表达式树，然后用最少的括号重新生成表达式。原始表达式中不需要的括号可以省略。

一个简单但几乎正确的解决方案是为每个运算符分配优先级。当你正在处理的节点下面有一个运算符，其优先级低于该节点时，您需要添加括号；例如，如果您在一个*（乘法）节点处，并且两个子节点中的一个是+（加法）节点。此外，还需要一些逻辑来处理左结合或右结合：如果您在一个+节点处，并且右侧节点也是一个+节点，则需要添加括号。

这只能部分正确，因为C++中有一些构造体无法映射到优先级语法：其中一些类型转换结构或三元运算符就是其中之一。但至少对于三元运算符而言，特殊处理并不难。

编辑：

关于您的大O问题：由于您需要在内存中构造整个表达式，因此显然不能实现O（1）空间复杂度。我认为时间复杂度应该是O（n），对于节点数的上限是n（字符串长度），您需要刚好访问每个节点。

- James Kanze

---

根据提交的代码，提问者可能不熟悉运算符优先级解析，所以这可能超出了他/她的能力范围，但这仍然是正确的答案。我不会担心C++的转换构造等问题；提问者的问题似乎只涉及id和二元表达式（id本身是一元表达式，但我不确定他们是否理解）。此外，我没有看到任何一元负号，希望他们不要被隐含的内容所迷惑。 - WhozCraig

@WhozCraig 我认为你对OP可能知道的内容是正确的。但这看起来非常像一项家庭作业，目标可能是让他实现一个简单的解析器来解决它。如果他不知道运算符优先级解析作为一种技术或术语，他可能已经（如果他一直在跟进课程）至少有一个关于优先级的直觉，并知道如何编写一个简单的解析器来考虑它。 - James Kanze

@WhozCraig，顺便说一下，我从未提到运算符优先级解析；我只是说“构建表达式树”（这可以通过递归下降非常容易地完成）。pokey909没有谈论解析，但他的伪代码是真正的优先级解析。尽管它无法正确处理像?:操作符这样的情况，但我真的很喜欢它。 - James Kanze

我不确定在没有优先级决策的情况下如何简化表达式树。我肯定需要一个。在这一点上，我认为你们两个都是正确的。当我发表原始评论时，pokeys的回答还没有出现，但现在我看到了它，我同意你的观点。 - WhozCraig

@WhozCraig C++没有优先级文法，而且有一些奇怪的角落（可能在这里不相关），在那里它无法用优先级文法表示。在C++中没有优先级（但如果不忘记奇怪的角落，使用优先级来展示可能会有帮助）。 - James Kanze

Answer 2

在网上找到以下内容...

给定输入: ((A+B)*C)
期望输出: (A+B)*C

假设:

• Peek (queue) 只是告诉队列前端的元素而不删除它。
• precedence( ) 是一个查找运算符优先级表的函数

下面是伪代码:

1. 将中缀表达式转换为逆波兰表达式（例如Shunting-yard algo O(n)）

   AB+C*

2. 只在队列Q中插入运算符

   (front)+ -------- *(rear)

3. 解析后缀表达式
4. 如果是操作数，则将其推入堆栈'S'
5. 如果是运算符
   • y=Delete(Q)
   • 如果precedence(y) > precedence(peek(Q))，则Push(S, "Pop(S) y Pop(S)")
   • 如果precedence(y) < precedence(peek(Q))，则Push(S, "( Pop(S) y Pop(S) )")
6. 最终结果在堆栈S的顶部

所有操作应该是O(n)的。

- pokey909

Answer 3

我想试着解决这个问题。这是我想到的解决方案。请注意，这只是伪代码，不能直接运行。

（实际上，它更像C++，但我已经有一段时间没有写过真正的C++了，而且我不想花费精力来确保一切都正确，因为我的意图是传达一个算法。）

queue<tuple<int, bool> > q = new queue<tuple<int, bool> >();

for (int i = 0; i < str.length; i++)
{
    char a = str.charAt(i);

    if (a == '(')
    {
        q.push(new tuple<int, bool>(i, false));
    }
    else if (a == ')')
    {
        if (q.top().bool)
        {
            // remove top.int and i from string
        }

        q.pop();
        q.top().bool = true;
    }
    else
    {
        q.top().bool = false;
    }
}

它的时间复杂度为O(n)，空间复杂度为O(n)（实际上，所使用的空间量基于字符串中最深层次的嵌套级别，但保证低于n）

（请注意，// remove top.int and i from string实际上无法以O(1)的时间复杂度完成。但是，如果你足够聪明，可以用类似的方式在O(1)内完成操作。例如，您可以实际上建立一个字符列表作为输出，并存储一个迭代器而不是整数，然后您可以以O(1)删除这两个字符。在最后，您可以通过在O(n)的时间复杂度内遍历该列表来构建最终的字符串。另一种解决方案是实际上在一个DummyOrCharacters的数组（或向量）上进行操作，它们可以是一个虚拟对象，不包含任何内容，或者包含一个字符。同样，您可以以O(1)替换一个字符为虚拟对象。同样，您将遍历结构并在O(n)的时间复杂度内构建输出字符串）

- Jasper