Identificar y marcar paréntesis no coincidentes en una expresión

Dada una expresión, encuentre y marque paréntesis coincidentes y no coincidentes en ella. Necesitamos reemplazar todos los paréntesis de apertura equilibrados con 0, los paréntesis de cierre equilibrados con 1 y todos los desequilibrados con -1.
Ejemplos:  

Input : ((a) 
Output : -10a1

Input : (a))
Output : 0a1-1

Input  : (((abc))((d)))))
Output : 000abc1100d111-1-1

La idea se basa en una pila . Ejecutamos un bucle desde el principio de la string hasta el final y por cada ‘(‘, lo empujamos a una pila. Si la pila está vacía y encontramos un corchete de cierre ‘)’, reemplazamos -1 en ese índice de la cuerda. De lo contrario, reemplazamos todos los corchetes de apertura ‘(‘ con 0 y los corchetes de cierre con 1. Luego, saltamos de la pila. 
 

// CPP program to mark balanced and unbalanced
// parenthesis.
#include <bits/stdc++.h>
using namespace std;
 
void identifyParenthesis(string a)
{
    stack<int> st;
 
    // run the loop upto end of the string
    for (int i = 0; i < a.length(); i++) {
 
        // if a[i] is opening bracket then push
        // into stack
        if (a[i] == '(')
            st.push(i);
         
        // if a[i] is closing bracket ')'
        else if (a[i] == ')') {
 
            // If this closing bracket is unmatched
            if (st.empty())
                a.replace(i, 1, "-1");
             
            else {
 
                // replace all opening brackets with 0
                // and closing brackets with 1
                a.replace(i, 1, "1");
                a.replace(st.top(), 1, "0");
                st.pop();
            }
        }
    }
 
    // if stack is not empty then pop out all
    // elements from it and replace -1 at that
    // index of the string
    while (!st.empty()) {
        a.replace(st.top(), 1, "-1");
        st.pop();
    }
 
    // print final string
    cout << a << endl;
}
 
// Driver code
int main()
{
    string str = "(a))";
    identifyParenthesis(str);
    return 0;
}

// Java program to mark balanced and
// unbalanced parenthesis.
import java.util.*;
 
class GFG
{
static void identifyParenthesis(StringBuffer a)
{
    Stack<Integer> st = new Stack<Integer>();
 
    // run the loop upto end of the string
    for (int i = 0; i < a.length(); i++)
    {
 
        // if a[i] is opening bracket then push
        // into stack
        if (a.charAt(i) == '(')
            st.push(i);
         
        // if a[i] is closing bracket ')'
        else if (a.charAt(i) == ')')
        {
 
            // If this closing bracket is unmatched
            if (st.empty())
                a.replace(i, i + 1, "-1");
             
            else
            {
 
                // replace all opening brackets with 0
                // and closing brackets with 1
                a.replace(i, i + 1, "1");
                a.replace(st.peek(), st.peek() + 1, "0");
                st.pop();
            }
        }
    }
 
    // if stack is not empty then pop out all
    // elements from it and replace -1 at that
    // index of the string
    while (!st.empty())
    {
        a.replace(st.peek(), 1, "-1");
        st.pop();
    }
 
    // print final string
    System.out.println(a);
}
 
// Driver code
public static void main(String[] args)
{
    StringBuffer str = new StringBuffer("(a))");
    identifyParenthesis(str);
}
}
 
// This code is contributed by Princi Singh

# Python3 program to
# mark balanced and
# unbalanced parenthesis.
def identifyParenthesis(a):
    st = []
 
    # run the loop upto
    # end of the string
    for i in range (len(a)):
 
        # if a[i] is opening
        # bracket then push
        # into stack
        if (a[i] == '('):
            st.append(a[i])
         
        # if a[i] is closing bracket ')'
        elif (a[i] == ')'):
 
            # If this closing bracket
            # is unmatched
            if (len(st) == 0):
                a = a.replace(a[i], "-1", 1)
             
            else:
 
                # replace all opening brackets with 0
                # and closing brackets with 1
                a = a.replace(a[i], "1", 1)
                a = a.replace(st[-1], "0", 1)
                st.pop()
           
    # if stack is not empty
    # then pop out all
    # elements from it and
    # replace -1 at that
    # index of the string
    while (len(st) != 0):
        a = a.replace(st[-1], 1, "-1");
        st.pop()
 
    # print final string
    print(a)
 
# Driver code
if __name__ == "__main__":
 
    st = "(a))"
    identifyParenthesis(st)
     
# This code is contributed by Chitranayal

// C# program to mark balanced and
// unbalanced parenthesis.
using System;
using System.Collections.Generic;
class GFG {
     
    static void identifyParenthesis(string a)
    {
        Stack<int> st = new Stack<int>();
  
        // run the loop upto end of the string
        for (int i = 0; i < a.Length; i++)
        {
  
            // if a[i] is opening bracket then push
            // into stack
            if (a[i] == '(')
                st.Push(i);
  
            // if a[i] is closing bracket ')'
            else if (a[i] == ')')
            {
  
                // If this closing bracket is unmatched
                if (st.Count == 0)
                {
                    a = a.Substring(0, i) + "-1" + a.Substring(i + 1);
                }
                else
                {
  
                    // replace all opening brackets with 0
                    // and closing brackets with 1
                    a = a.Substring(0, i) + "1" + a.Substring(i + 1);
                    a = a.Substring(0, st.Peek()) + "0" + a.Substring(st.Peek() + 1);
                    st.Pop();
                }
            }
        }
  
        // if stack is not empty then pop out all
        // elements from it and replace -1 at that
        // index of the string
        while (st.Count > 0)
        {
            a = a.Substring(0, st.Peek()) + "-1" + a.Substring(st.Peek() + 1);
            st.Pop();
        }
  
        // print final string
        Console.Write(new string(a));
    }
     
  static void Main() {
    string str = "(a))";
    identifyParenthesis(str);
  }
}
 
// This code is contributed by divyesh072019.

<script>
    // Javascript program to mark balanced and
    // unbalanced parenthesis.
     
    function identifyParenthesis(a)
    {
        let st = [];
 
        // run the loop upto end of the string
        for (let i = 0; i < a.length; i++)
        {
 
            // if a[i] is opening bracket then push
            // into stack
            if (a[i] == '(')
                st.push(i);
 
            // if a[i] is closing bracket ')'
            else if (a[i] == ')')
            {
 
                // If this closing bracket is unmatched
                if (st.length == 0)
                {
                    a[i] = "-1";
                }
                else
                {
 
                    // replace all opening brackets with 0
                    // and closing brackets with 1
                    a[i] = "1";
                    a[st[st.length - 1]] = "0";
                    st.pop();
                }
            }
        }
 
        // if stack is not empty then pop out all
        // elements from it and replace -1 at that
        // index of the string
        while (st.length > 0)
        {
            a[st[st.length - 1]] = "-1";
            st.pop();
        }
 
        // print final string
        document.write(a.join(""));
    }
     
    let str = "(a))";
    identifyParenthesis(str.split(''));
 
// This code is contributed by suresh07.
</script>

Producción: 
 

0a1-1

Complejidad temporal: O(n)
Espacio auxiliar: O(n)