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.
C++
// 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
// 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
# 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#
// 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.
Javascript
<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)
Publicación traducida automáticamente
Artículo escrito por smarakchopdar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA