QUESTION
We are given a string having parenthesis like below\n ( ((X)) (((Y))) )\nWe need to find the maximum depth of balanced parenthesis, like 4 in above example. Since Y is surrounded by 4 balanced parenthesis.\n\nIf parenthesis are unbalanced then return -1.
“TESTCASE_1”: “( a(b) (c) (d(e(f)g)h) I (j(k)l)m)\n###—###SEPERATOR—###—\n4”, “TESTCASE_2”: “( p((q)) ((s)t) )\n###—###SEPERATOR—###—\n3”, “TESTCASE_3”: “b) (c) ()\n###—###SEPERATOR—###—\n-1”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0
ANSWER
#include <iostream>
#include <stdio.h>
using namespace std;
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()
{
char s[50];
scanf("%[^\n]s",s);
//string s = "( ((X)) (((Y))) )";
cout << maxDepth(s);
return 0;
}