Find maximum depth of nested parenthesis in a string

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;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro