remove extra parenthesis

Question

Question:

Remove extra parentheses from the string.
e.g.

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

I have come up with the following solution:
Approach: I scan through the string and remember (using a map) the index of a opening parenthesis and whether it's extra or not (by default it's extra). If I find a closing parenthesis I check the corresponding opening parenthesis from map and if it's extra then delete both.

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;
        }
    }
  }
}  

Time complexity: O(n2)
Space: O(n)
I'm not too happy with my solution because I'm using extra storage and doing it in quadratic time.

Could we do this in O(n) time and O(1) space? If not what is the best one can do?

Answer 1

Build an expression tree, then regenerate the expression with minimum parentheses. Any parentheses in the original which aren't in the generates are unnecessary.

A simple, almost correct solution would be to assign a precedence to each operator. You then need parentheses any time a node directly under the node you are working on is an operator which has a lower precedence than that of the node; e.g if you are at a * (multiplication) node, and one of the two child nodes has is a + (addition) node. Plus some logic to handle left or right binding: if you're at a + node, and the right hand node is also a + node, you need parentheses.

This is only partially correct, because there are a few constructs in C++ which can't really be mapped to a precedence grammar: some of the type casting constructs, or the ternary operator, come to mind. At least in the case of the ternary operator, however, the special handling isn't that difficult.

EDIT:

With regards to your big-O questions: this obviously isn't O(1) in space, since you need to construct the entire expression in memory. I don't think an O(1) for memory is possible, since potentially, you can have unlimited nesting, and you can't tell whether the parentheses are necessary or not until an indeterminate time later. I've not actually analysed it, but I think it is O(n) in time. The upper bound on the number of nodes is n (the length of the string), and you need to visit each node exactly once.

Answer 2

More or less found on the web...

Given input: ((A+B)*C) Expected output: (A+B)*C

Assumptions:

• Peek (queue) just tells the element in front end of queue without deleting it.
• precedence( ) is a function which looks a precedence table of operators

Pseudo code below:

1. Convert infix expression to RPN (e.g. Shunting-yard algo O(n))

   AB+C*

2. Insert only operators in queue Q

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

3. Parse postfix expression
4. If operand, push to stack 'S'
5. If operator
   • y=Delete(Q)
   • If precedence(y) > precedence(peek(Q)), then Push (S, "Pop(S) y Pop(S)")
   • If precedence(y) < precedence(peek(Q)), then Push (S, "( Pop(S) y Pop(S) )")
6. Final result on top of S

All should be O(n).