6

问题：

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

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

我想出了以下解决方案：
方法：我扫描字符串并记住（使用映射）左括号的索引以及它是否是额外的（默认情况下是额外的）。如果我找到一个右括号，我会从 map 中检查相应的左括号，如果它是多余的，则将两者都删除。

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) 空间内做到这一点吗？如果不是，最好的方法是什么？

4

3 回答 3

3

构建一个表达式树，然后用最少的括号重新生成表达式。原始文件中没有在生成中的任何括号都是不必要的。

一个简单且几乎正确的解决方案是为每个运算符分配优先级。然后，只要您正在处理的节点正下方的节点是优先级低于该节点的运算符，您就需要括号；例如，如果您位于* （乘法）节点，并且两个子节点之一是+ （加法）节点。加上一些处理左右绑定的逻辑：如果你在一个+节点上，右手节点也是一个+节点，你需要括号。

这只是部分正确，因为 C++ 中有一些构造不能真正映射到优先语法：我想到了一些类型转换构造或三元运算符。然而，至少在三元运算符的情况下，特殊处理并不是那么困难。

编辑：

关于您的大 O 问题：这显然不是空间中的 O(1)，因为您需要在内存中构造整个表达式。我认为内存的 O(1) 是不可能的，因为潜在地，你可以有无限的嵌套，并且在不确定的时间之后你不能判断括号是否是必要的。我没有真正分析过它，但我认为它是 O(n) 的时间。节点数的上限是n（字符串的长度），您需要准确地访问每个节点一次。

于 2012-11-02T23:45:16.553 回答
2

或多或少在网上找到...

给定输入：((A+B)*C) 预期输出：(A+B)*C

假设：

  • Peek（队列）只是告诉队列前端的元素而不删除它。
  • 优先级（）是一个查看运算符优先级表的函数

伪代码如下：

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

    AB+C*

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

    (前)+ -------- *(后)

  3. 解析后缀表达式
  4. 如果是操作数，则压入堆栈'S'
  5. 如果运算符
    • y=删除(Q)
    • 如果优先级(y) > 优先级(peek(Q))，则推送(S, "Pop(S) y Pop(S)")
    • 如果优先级（y）<优先级（peek（Q）），则推送（S，“（Pop（S）y Pop（S））”）
  6. 最终结果在上面S

都应该是 O(n)。

于 2012-11-02T23:58:11.890 回答
0

我以为我会刺伤这个。这是我突然想到的问题的解决方案。请注意，这是伪代码，并不意味着直接运行。

（实际上，它更像是 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 的数组（或向量） , 要么是一个虚拟的，不包含任何内容，要么包含一个字符。再一次，您可以用 dummy 中的虚拟替换字符O(1)。再一次，您将遍历结构并在O(n))中构建输出字符串

于 2012-11-03T00:04:21.157 回答