c++ - 删除额外的括号

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.

我想出了以下解决方案:
方法:我扫描整个字符串并记住(使用映射)左括号的索引以及它是否是额外的(默认情况下是额外的)。如果我找到一个右括号，我会从 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) 空间内完成此操作？如果不能，最好的办法是什么？

Answer 1

构建表达式树，然后重新生成最小值的表达式 括弧。原文中没有的任何括号 生成是不必要的。

一个简单、几乎正确的解决方案是将优先级分配给 每个运营商。然后，您需要在任何时候直接使用括号 在您正在处理的节点下是一个运算符，它具有较低的 优先于节点的优先级；例如，如果您在 * (multiplication) 节点，并且两个子节点之一有一个 + (加法)节点。加上一些处理左绑定(bind)或右绑定(bind)的逻辑:如果 你在一个 + 节点，右边的节点也是一个 + 节点，你 需要括号。

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

编辑:

关于您的大 O 问题:这显然不是 O(1) 空间，因为您需要在内存中构造整个表达式。我 不要认为 O(1) 的内存是可能的，因为有可能，你可以 无限嵌套，看不出括号是不是 直到不确定的时间之后才需要或不需要。我其实没有 分析了一下，不过我觉得时间上是O(n)。的上界 节点数为n(字符串长度)，需要访问 每个节点恰好一次。