Given a string str consisting of parenthesis from [ “(” , “)” , “{” , “}” , “[” , “]” ].
If the String is perfectly balanced return 0 else return the index(starting from 1)at which the nesting is found to be wrong.
Examples:
Input : str = “{[()]}[]”
Output : 0
Input : str = “[{]()}”
Output : 3
Input : str = “}[{}]”
Output : 1
Input : str = “{([]){”
Output : 7
Approach:
- First we are creating the lst1 and lst2 that will have the opening and closing brackets respectively
- Now we will create another list lst that will work as a Stack means if any closing brackets will appear in the string then the respective opening brackets present in the lst will be deleted
- If any closing brackets will appear in the string and no respective opening brackets is present in the lst then this will be the bad index we will return it
- If we reach at the end of the string while traversing and the size of the lst is not equals to 0 we will return the len(String)+1
Below is the implementation of the above approach
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;int main(){ // Defining the string string String = "{[()]}[]"; // Storing opening braces in list lst1 vector<char> lst1 ={'{', '(', '['}; // Storing closing braces in list lst2 vector<char> lst2 ={'}', ')', ']'}; // Creating an empty list lst vector<char> lst; int k; // Creating dictionary to map // closing braces to opening ones map<char,char> Dict; Dict.insert(pair<int, int>(')', '(')); Dict.insert(pair<int, int>('}', '{')); Dict.insert(pair<int, int>(']', '[')); int a = 0, b = 0, c = 0; // If first position of string contain // any closing braces return 1 if(count(lst2.begin(), lst2.end(), String[0])) { cout << 1 << endl; } else { // If characters of string are opening // braces then append them in a list for(int i = 0; i < String.size(); i++) { if(count(lst1.begin(), lst1.end(), String[i])) { lst.push_back(String[i]); k = i + 2; } else { // When size of list is 0 and new closing // braces is encountered then print its // index starting from 1 if(lst.size()== 0 && (count(lst2.begin(), lst2.end(), String[i]))) { cout << (i + 1) << endl; c = 1; break; } else { // As we encounter closing braces we map // them with theircorresponding opening // braces using dictionary and check // if it is same as last opened braces //(last element in list) if yes then we // delete that element from list if(Dict[String[i]]== lst[lst.size()-1]) { lst.pop_back(); } else { // Otherwise we return the index // (starting from 1) at which // nesting is found wrong break; cout << (i + 1) << endl; a = 1; } } } } // At end if the list is empty it // means the string is perfectly nested if(lst.size() == 0 && c == 0) { cout << 0 << endl; b = 1; } if(a == 0 && b == 0 && c == 0) { cout << k << endl; } } return 0;}// This code is contributed by decode2207. |
Java
// Java implementation of the approachimport java.util.*;public class Main{ public static void main(String[] args) { // Defining the string String string = "{[()]}[]"; // Storing opening braces in list lst1 char[] lst1 = {'{', '(', '['}; // Storing closing braces in list lst2 char[] lst2 = {'}', ')', ']'}; // Creating an empty list lst Vector<Character> lst = new Vector<Character>(); // Creating dictionary to map // closing braces to opening ones HashMap<Character, Character> Dict = new HashMap<>(); Dict.put(')', '('); Dict.put('}', '{'); Dict.put(']', '['); int a = 0, b = 0, c = 0; // If first position of string contain // any closing braces return 1 if(Arrays.asList(lst2).contains(string.charAt(0))) { System.out.println(1); } else { int k = 0; // If characters of string are opening // braces then append them in a list for(int i = 0; i < string.length(); i++) { if(Arrays.asList(lst1).contains(string.charAt(i))) { lst.add(string.charAt(i)); k = i + 2; } else { // When size of list is 0 and new closing // braces is encountered then print its // index starting from 1 if(lst.size()== 0 && Arrays.asList(lst2).contains(string.charAt(i))) { System.out.println((i + 1)); c = 1; break; } else { // As we encounter closing braces we map // them with theircorresponding opening // braces using dictionary and check // if it is same as last opened braces //(last element in list) if yes then we // delete that element from list if(lst.size() > 0 && Dict.get(string.charAt(i))== lst.get(lst.size() - 1)) { lst.remove(lst.size() - 1); } else { // Otherwise we return the index // (starting from 1) at which // nesting is found wrong a = 1; break; } } } } // At end if the list is empty it // means the string is perfectly nested if(lst.size() == 0 && c == 0) { System.out.println(0); b = 1; } if(a == 0 && b == 0 && c == 0) { System.out.println(k); } } }}// This code is contributed by divyesh072019. |
Python3
# Write Python3 code here# Defining the stringstring = "{[()]}[]"# Storing opening braces in list lst1lst1 =['{', '(', '[']# Storing closing braces in list lst2lst2 =['}', ')', ']']# Creating an empty list lstlst =[]# Creating dictionary to map # closing braces to opening onesDict ={ ')':'(', '}':'{', ']':'['}a = b = c = 0# If first position of string contain # any closing braces return 1if string[0] in lst2: print(1) else: # If characters of string are opening # braces then append them in a list for i in range(0, len(string)): if string[i] in lst1: lst.append(string[i]) k = i + 2 else: # When size of list is 0 and new closing # braces is encountered then print its # index starting from 1 if len(lst)== 0 and (string[i] in lst2): print(i + 1) c = 1 break else: # As we encounter closing braces we map # them with theircorresponding opening # braces using dictionary and check # if it is same as last opened braces #(last element in list) if yes then we # delete that element from list if Dict[string[i]]== lst[len(lst)-1]: lst.pop() else: # Otherwise we return the index # (starting from 1) at which # nesting is found wrong print(i + 1) a = 1 break # At end if the list is empty it # means the string is perfectly nested if len(lst)== 0 and c == 0: print(0) b = 1 if a == 0 and b == 0 and c == 0: print(k) |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG { static void Main() { // Defining the string string String = "{[()]}[]"; // Storing opening braces in list lst1 char[] lst1 = {'{', '(', '['}; // Storing closing braces in list lst2 char[] lst2 = {'}', ')', ']'}; // Creating an empty list lst List<char> lst = new List<char>(); // Creating dictionary to map // closing braces to opening ones Dictionary<char, char> Dict = new Dictionary<char, char>(); Dict[')'] = '('; Dict['}'] = '{'; Dict[']'] = '['; int a = 0, b = 0, c = 0; // If first position of string contain // any closing braces return 1 if(Array.Exists(lst2, element => element == String[0])) { Console.WriteLine(1); } else { int k = 0; // If characters of string are opening // braces then append them in a list for(int i = 0; i < String.Length; i++) { if(Array.Exists(lst1, element => element == String[i])) { lst.Add(String[i]); k = i + 2; } else { // When size of list is 0 and new closing // braces is encountered then print its // index starting from 1 if(lst.Count== 0 && Array.Exists(lst2, element => element == String[i])) { Console.WriteLine((i + 1)); c = 1; break; } else { // As we encounter closing braces we map // them with theircorresponding opening // braces using dictionary and check // if it is same as last opened braces //(last element in list) if yes then we // delete that element from list if(lst.Count > 0 && Dict[String[i]]== lst[lst.Count - 1]) { lst.RemoveAt(lst.Count - 1); } else { // Otherwise we return the index // (starting from 1) at which // nesting is found wrong a = 1; break; } } } } // At end if the list is empty it // means the string is perfectly nested if(lst.Count == 0 && c == 0) { Console.WriteLine(0); b = 1; } if(a == 0 && b == 0 && c == 0) { Console.WriteLine(k); } } }}// This code is contributed by divyeshrabadiya07. |
Javascript
<script> // Javascript implementation of the approach // Defining the string let string = "{[()]}[]"; // Storing opening braces in list lst1 let lst1 =['{', '(', '[']; // Storing closing braces in list lst2 let lst2 =['}', ')', ']']; // Creating an empty list lst let lst =[]; // Creating dictionary to map // closing braces to opening ones let Dict ={ ')':'(', '}':'{', ']':'['} let a = 0, b = 0, c = 0; // If first position of string contain // any closing braces return 1 if(string[0] in lst2) { document.write(1 + "</br>"); } else { // If characters of string are opening // braces then append them in a list for(let i = 0; i < string.length; i++) { if(string[i] in lst1) { lst.push(string[i]); k = i + 2; } else { // When size of list is 0 and new closing // braces is encountered then print its // index starting from 1 if(lst.length== 0 && (string[i] in lst2)) { document.write((i + 1) + "</br>"); c = 1; break; } else { // As we encounter closing braces we map // them with theircorresponding opening // braces using dictionary and check // if it is same as last opened braces //(last element in list) if yes then we // delete that element from list if(Dict[string[i]]== lst[lst.length-1]) { lst.pop(); } else { // Otherwise we return the index // (starting from 1) at which // nesting is found wrong break; document.write((i + 1) + "</br>"); a = 1; } } } } // At end if the list is empty it // means the string is perfectly nested if(lst.length == 0 && c == 0) { document.write(0 + "</br>"); b = 1; } if(a == 0 && b == 0 && c == 0) { document.write(k + "</br>"); } } // This code is contributed by rameshtravel07.</script> |
Output:
0
