删除多余的括号

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

Answer 1

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

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

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

编辑：

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