Given a string S consisting of opening parentheses, closing parentheses and integers, the task is to print Yes if, in this string, the integers correctly indicates its depth. Depth refers to the number of nested sets of parentheses surrounding that integer. Print No otherwise.
Examples:
Input: S = “((2)((3)))”
Output: Yes
Explanation:
No of Opening & Closing Parentheses around 2 = 2
No of Opening & Closing Parentheses around 3 = 3
Input: S = “((35)(2))”
Output: No
Explanation:
No of Opening & Closing Parentheses around 35 = 2
No of Opening & Closing Parentheses around 2 = 2
Approach:
- Iterate the string character by character
- If it is opening or closing parenthesis then append into an array arr[]
- If the character is digit, then iterate till the entire number is read and then append into the arr[]
- Iterate the array arr[] element by element
- If the element is ‘(‘ increment depth and open by 1
- If the element is ‘)’ decrement depth by 1 and increment close by 1
- If the element is an Integer, check if “Integer != depth”, if true
set flag to 0 and break the loop
- After iterating the entire string, check if open not equals to close, if true set flag = 0
Below is the implementation of the above approach
C++
// Function to check if the Depth // of Parentheses is correct // in the given String #include <bits/stdc++.h> using namespace std; bool Formatted(string s) { vector< char > k; int i = 0; while (i < s.size()) { // Appending if the // Character is not integer if (s[i]== ')' or s[i]== '(' ) { k.push_back(s[i]); i += 1; } else { // Iterating till the entire // Digit is read char st; while (s[i]!= ')' and s[i]!= ')' ) { st = s[i]; i = i + 1; } k.push_back(st); } } int depth = 0, flag = 1; int open = 0, close = 0; for ( char i:k) { // Check if character is '(' if (i == '(' ) { // Increment depth by 1 depth += 1; // Increment open by 1 open += 1; // Check if character is ')' } else if (i == ')' ){ // Decrement depth by 1 depth -= 1; // Increment close by 1 close += 1; } else { if (i- '0' != depth){ flag = 0; break ; } } } // Check if open parentheses // NOT equals close parentheses if (open != close) flag = 0; return (flag == 1)? true : false ; } // Driver Code int main() { string s = "((2)((3)))" ; bool k = Formatted(s); if (k == true ) printf ( "Yes" ); else printf ( "No" ); return 0; } // This code is contributed by mohit kumar 29 |
Java
// Function to check if the Depth // of Parentheses is correct // in the given String import java.util.*; class GFG{ static boolean Formatted(String s) { Vector<Character> k = new Vector<Character>(); int i = 0 ; while (i < s.length()) { // Appending if the // Character is not integer if (s.charAt(i)== ')' || s.charAt(i)== '(' ) { k.add(s.charAt(i)); i += 1 ; } else { // Iterating till the entire // Digit is read char st = 0 ; while (s.charAt(i)!= ')' && s.charAt(i)!= ')' ) { st = s.charAt(i); i = i + 1 ; } k.add(st); } } int depth = 0 , flag = 1 ; int open = 0 , close = 0 ; for ( char i2 : k) { // Check if character is '(' if (i2 == '(' ) { // Increment depth by 1 depth += 1 ; // Increment open by 1 open += 1 ; // Check if character is ')' } else if (i2 == ')' ){ // Decrement depth by 1 depth -= 1 ; // Increment close by 1 close += 1 ; } else { if (i2- '0' != depth){ flag = 0 ; break ; } } } // Check if open parentheses // NOT equals close parentheses if (open != close) flag = 0 ; return (flag == 1 )? true : false ; } // Driver Code public static void main(String[] args) { String s = "((2)((3)))" ; boolean k = Formatted(s); if (k == true ) System.out.printf( "Yes" ); else System.out.printf( "No" ); } } // This code is contributed by Rajput-Ji |
Python3
# Function to check if the Depth # of Parentheses is correct # in the given String def Formatted(s): k = [] i = 0 while i < len (s): # Appending if the # Character is not integer if s[i].isdigit() = = False : k.append(s[i]) i + = 1 else : # Iterating till the entire # Digit is read st = "" while s[i].isdigit(): st + = s[i] i = i + 1 k.append( int (st)) depth, flag = 0 , 1 open , close = 0 , 0 for i in k: # Check if character is '(' if i = = '(' : # Increment depth by 1 depth + = 1 # Increment open by 1 open + = 1 # Check if character is ')' elif i = = ')' : # Decrement depth by 1 depth - = 1 # Increment close by 1 close + = 1 else : if i ! = depth: flag = 0 break # Check if open parentheses # NOT equals close parentheses if open ! = close: flag = 0 return True if flag = = 1 else False # Driver Code if __name__ = = '__main__' : s = '((2)((3)))' k = Formatted(s) if k = = True : print ( "Yes" ) else : print ( "No" ) |
C#
// Function to check if the Depth // of Parentheses is correct // in the given String using System; using System.Collections.Generic; class GFG { static bool Formatted(String s) { List< char > k = new List< char >(); int i = 0; while (i < s.Length) { // Appending if the // char is not integer if (s[i]== ')' || s[i]== '(' ) { k.Add(s[i]); i += 1; } else { // Iterating till the entire // Digit is read char st = '\x0000' ; while (s[i] != ')' && s[i] != ')' ) { st = s[i]; i = i + 1; } k.Add(st); } } int depth = 0, flag = 1; int open = 0, close = 0; foreach ( char i2 in k) { // Check if character is '(' if (i2 == '(' ) { // Increment depth by 1 depth += 1; // Increment open by 1 open += 1; // Check if character is ')' } else if (i2 == ')' ){ // Decrement depth by 1 depth -= 1; // Increment close by 1 close += 1; } else { if (i2- '0' != depth){ flag = 0; break ; } } } // Check if open parentheses // NOT equals close parentheses if (open != close) flag = 0; return (flag == 1)? true : false ; } // Driver Code public static void Main(String[] args) { String s = "((2)((3)))" ; bool k = Formatted(s); if (k == true ) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Function to check if the Depth // of Parentheses is correct // in the given String function Formatted(s) { let k = []; let i = 0; while (i < s.length) { // Appending if the // Character is not integer if (s[i]== ')' || s[i]== '(' ) { k.push(s[i]); i += 1; } else { // Iterating till the entire // Digit is read let st = 0; while (s[i]!= ')' && s[i]!= ')' ) { st = s[i]; i = i + 1; } k.push(st); } } let depth = 0, flag = 1; let open = 0, close = 0; for (let i2=0;i2< k.length;i2++) { // Check if character is '(' if (k[i2] == '(' ) { // Increment depth by 1 depth += 1; // Increment open by 1 open += 1; // Check if character is ')' } else if (k[i2] == ')' ){ // Decrement depth by 1 depth -= 1; // Increment close by 1 close += 1; } else { if (k[i2]- '0' != depth){ flag = 0; break ; } } } // Check if open parentheses // NOT equals close parentheses if (open != close) flag = 0; return (flag == 1)? true : false ; } // Driver Code let s = "((2)((3)))" ; let k = Formatted(s); if (k == true ) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by patel2127 </script> |
Yes
Time Complexity: O(n)
Auxiliary Space: O(n), where n is the length of the given string.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!