title: Removal of unbalanced parentheses in the string
body: <p>I have tried a code to remove unbalanced parentheses in a string. There is a string S with parantheses <code>(</code> and <code>)</code> along with some alphabets is passed as input to the program. The program must remove the unbalanced (<em>not matched</em>) parantheses and then print the string value as the output. So the following code can do this successfully:</p>
  
  <pre><code>#include&lt;cstring&gt;
  #include&lt;iostream&gt;
  #include&lt;vector&gt;
  
  using namespace std;
  #define mfor(i,n) for(int i=0;i&lt;n;i++)
  
  /*-----------------------------------------------*/
  
  void remove_paranthesis(char *s)
  {
   int length= strlen(s);
   int pos[100]={ 0 };
   vector&lt;int&gt; left, right;    // for storing the indexes of the 
      // invalid left and right paranthesis
      mfor(i,length)
         {
          if(s[i]=='(')
           {
            left.push_back(i);
           }
          else if(s[i]==')')
           {
            if(!left.empty())
              {
               left.pop_back();
              }
            else
              {
               right.push_back(i);
              }
           } 
         }
  
   if(!left.empty()||!right.empty())
    {
     cout&lt;&lt;"paranthesis to be removed are at the following index :"&lt;&lt;endl;
     if(!left.empty()) 
       for (std::vector&lt;int&gt;::iterator it = left.begin() ; it != left.end(); 
       ++it)
       {
         cout&lt;&lt;*it&lt;&lt;endl;
         pos[*it]=1;
       }
     if(!right.empty()) 
     for (std::vector&lt;int&gt;::iterator it = right.begin() ; it != right.end(); 
     ++it)
       {
         cout&lt;&lt;*it&lt;&lt;endl;
         pos[*it]=1;
       }
    } 
    cout&lt;&lt;"endl"&lt;&lt;"MODIFIED STRING IS:-"&lt;&lt;endl;
    mfor(i,length)
    {
       if(!pos[i]) cout&lt;&lt;s[i];
    }
    cout&lt;&lt;endl;
  }
  
  int main()
  {
   char s[1000];
   cout&lt;&lt;"enter a string of paranthesis "&lt;&lt;endl;
   cin&gt;&gt;s;
   remove_paranthesis(s);
  }
  </code></pre>
  
  <p>So this code works fine for this type of cases:</p>
  
  <p><strong>Input</strong>: <code>((((abc))</code> </p>
  
  <p><strong>Output</strong>: <code>((abc))</code></p>
  
  <p>Incase several options are possible when the parantheses are contiguous, then match a closing parantheses ) to the opening parantheses ( which is as far as possible. Also the number of matches must be maximised. So consider this case:</p>
  
  <p><strong>Input:</strong> <code>((xyz)((mno))</code> </p>
  
  <p><strong>Output:</strong> <code>((xyz)(mno))</code> </p>
  
  <p><strong>Explanation:</strong> Here two options are possible - <code>((xyz)(mno))</code> and 
  <code>(xyz)((mno))</code>. But as <code>)</code> must be matched to a <code>(</code> which is as far as possible, so  <code>((xyz)(mno))</code> is printed as the output. </p>
  
  <p>But my code is printing <code>(xyz)((mno))</code> as the output. How can I modify this code to get the result?</p>