Nos dan una string que tiene paréntesis como a continuación
«( ((X)) (((Y))) )»
Necesitamos encontrar la profundidad máxima del paréntesis equilibrado, como 4 en el ejemplo anterior. Dado que ‘Y’ está rodeada por 4 paréntesis equilibrados.
Si el paréntesis no está equilibrado, devuelve -1.
Ejemplos:
C++
// A C++ program to find the maximum depth of nested
// parenthesis in a given expression
#include <bits/stdc++.h>
using namespace std;
int maxDepth(string& s)
{
int count = 0;
stack<int> st;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(')
st.push(i); // pushing the bracket in the stack
else if (s[i] == ')') {
if (count < st.size())
count = st.size();
/*keeping track of the parenthesis and storing
it before removing it when it gets balanced*/
st.pop();
}
}
return count;
}
// Driver program
int main()
{
string s = "( ((X)) (((Y))) )";
cout << maxDepth(s);
// This code is contributed by rakeshsahni
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG {
public static int maxDepth(String s) {
int count=0;
Stack<Integer> st = new Stack<>();
for(int i=0;i<s.length();i++)
{
if(s.charAt(i) == '(')
st.push(i);//pushing the bracket in the stack
else if(s.charAt(i) == ')')
{
if(count < st.size())
count = st.size();
/*keeping track of the parenthesis and storing it before removing
it when it gets balanced*/
st.pop();
}
}
return count;
}
public static void main (String[] args) {
System.out.println(maxDepth("( ((X)) (((Y))) )"));
}
}
Python3
# Python code to implement the approach
def maxDepth(s):
count = 0
st = []
for i in range(len(s)):
if (s[i] == '('):
st.append(i) # pushing the bracket in the stack
elif (s[i] == ')'):
if (count < len(st)):
count = len(st)
# keeping track of the parenthesis and storing
# it before removing it when it gets balanced
st.pop()
return count
# Driver program
s = "( ((X)) (((Y))) )"
print(maxDepth(s))
# This code is contributed by shinjanpatra
C#
//C# program to find the maximum depth
//of nested parenthesis in a string
using System;
using System.Collections;
public class GFG{
static int maxDepth(string s){
int count=0;
Stack st = new Stack();
for(int i=0;i<s.Length;i++)
{
if(s[i]=='('){
st.Push(i);//pushing the bracket in the stack
}else{
if(s[i]==')'){
if(count<st.Count){
count=st.Count;
}
/*keeping track of the parenthesis and storing it before removing
it when it gets balanced*/
st.Pop();
}
}
}
return count;
}
//Driver Code
static public void Main (){
Console.Write(maxDepth("( ((X)) (((Y))) )"));//Function call
}
}
//This code is contributed by shruti456rawal
Javascript
<script>
// JavaScript code to implement the approach
function maxDepth(s){
let count = 0
let st = []
for(let i=0;i<s.length;i++){
if (s[i] == '(')
st.push(i) // pushing the bracket in the stack
else if (s[i] == ')'){
if (count < st.length)
count = st.length
// keeping track of the parenthesis and storing
// it before removing it when it gets balanced
st.pop()
}
}
return count
}
// Driver program
let s = "( ((X)) (((Y))) )"
document.write(maxDepth(s),"</br>")
// This code is contributed by shinjanpatra
</script>
C++
// A C++ program to find the maximum depth of nested
// parenthesis in a given expression
#include <iostream>
using namespace std;
// function takes a string and returns the
// maximum depth nested parenthesis
int maxDepth(string S)
{
int current_max = 0; // current count
int max = 0; // overall maximum count
int n = S.length();
// Traverse the input string
for (int i = 0; i < n; i++)
{
if (S[i] == '(')
{
current_max++;
// update max if required
if (current_max > max)
max = current_max;
}
else if (S[i] == ')')
{
if (current_max > 0)
current_max--;
else
return -1;
}
}
// finally check for unbalanced string
if (current_max != 0)
return -1;
return max;
}
// Driver program
int main()
{
string s = "( ((X)) (((Y))) )";
cout << maxDepth(s);
return 0;
}
Java
//Java program to find the maximum depth of nested
// parenthesis in a given expression
class GFG {
// function takes a string and returns the
// maximum depth nested parenthesis
static int maxDepth(String S) {
int current_max = 0; // current count
int max = 0; // overall maximum count
int n = S.length();
// Traverse the input string
for (int i = 0; i < n; i++) {
if (S.charAt(i) == '(') {
current_max++;
// update max if required
if (current_max > max) {
max = current_max;
}
} else if (S.charAt(i) == ')') {
if (current_max > 0) {
current_max--;
} else {
return -1;
}
}
}
// finally check for unbalanced string
if (current_max != 0) {
return -1;
}
return max;
}
// Driver program
public static void main(String[] args) {
String s = "( ((X)) (((Y))) )";
System.out.println(maxDepth(s));
}
}
Python3
# A Python program to find the maximum depth of nested
# parenthesis in a given expression
# function takes a string and returns the
# maximum depth nested parenthesis
def maxDepth(S):
current_max = 0
max = 0
n = len(S)
# Traverse the input string
for i in range(n):
if S[i] == '(':
current_max += 1
if current_max > max:
max = current_max
else if S[i] == ')':
if current_max > 0:
current_max -= 1
else:
return -1
# finally check for unbalanced string
if current_max != 0:
return -1
return max
# Driver program
s = "( ((X)) (((Y))) )"
print (maxDepth(s))
# This code is contributed by BHAVYA JAIN
C#
// C# program to find the
// maximum depth of nested
// parenthesis in a given expression
using System;
class GFG {
// function takes a string
// and returns the maximum
// depth nested parenthesis
static int maxDepth(string S)
{
// current count
int current_max = 0;
// overall maximum count
int max = 0;
int n = S.Length;
// Traverse the input string
for (int i = 0; i < n; i++)
{
if (S[i] == '(')
{
current_max++;
// update max if required
if (current_max > max)
{
max = current_max;
}
}
else if (S[i] == ')')
{
if (current_max > 0)
{
current_max--;
}
else
{
return -1;
}
}
}
// finally check for unbalanced string
if (current_max != 0)
{
return -1;
}
return max;
}
// Driver program
public static void Main()
{
string s = "(((X)) (((Y))))";
Console.Write(maxDepth(s));
}
}
// This code is contributed by Chitranayal
PHP
<?php
// A PHP program to find the
// maximum depth of nested
// parenthesis in a given
// expression
// function takes a string
// and returns the maximum
// depth nested parenthesis
function maxDepth($S)
{
// current count
$current_max = 0;
// overall maximum count
$max = 0;
$n = strlen($S);
// Traverse the input string
for ($i = 0; $i < $n; $i++)
{
if ($S[$i] == '(')
{
$current_max++;
// update max if required
if ($current_max> $max)
$max = $current_max;
}
else if ($S[$i] == ')')
{
if ($current_max>0)
$current_max--;
else
return -1;
}
}
// finally check for
// unbalanced string
if ($current_max != 0)
return -1;
return $max;
}
// Driver Code
$s = "( ((X)) (((Y))) )";
echo maxDepth($s);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to find the
// maximum depth of nested parenthesis
// in a given expression
// Function takes a string and returns the
// maximum depth nested parenthesis
function maxDepth(S)
{
// Current count
let current_max = 0;
// Overall maximum count
let max = 0;
let n = S.length;
// Traverse the input string
for(let i = 0; i < n; i++)
{
if (S[i] == '(')
{
current_max++;
// Update max if required
if (current_max > max)
{
max = current_max;
}
}
else if (S[i] == ')')
{
if (current_max > 0)
{
current_max--;
} else
{
return -1;
}
}
}
// Finally check for unbalanced string
if (current_max != 0)
{
return -1;
}
return max;
}
// Driver code
let s = "( ((X)) (((Y))) )";
document.write(maxDepth(s));
// This code is contributed by avanitrachhadiya2155
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA