CODEWITHSUNDEEP
c++
user8622672
user8622672

Reputation:

C++ Matching Brackets Solution

I wrote this code for the problem linked here. https://www.codechef.com/ZCOPRAC/problems/ZCO12001

Even though I ran my code using the sample input they have mentioned,I get a WA when I submit my code on their website.

#include <iostream> 

int main() {
    int n;
    std::cin >> n;
    int arr[n];
    for (int i = 0; i <n ;++i) {
        std::cin >> arr[i];
    }
    int c_depth , max_depth = 0 , max_pos;

    for (int i = 0; i < n; ++i) {
        if (arr[i] == 1) {
            ++c_depth;
            if (c_depth > max_depth) {
                max_depth = c_depth;
                max_pos = i+1;
            }

        }
        else {
            --c_depth;
        }
    }
    int a_long = 0,max_long = 0,max_long_pos = 0,two_count = 0,c_long = 0;
    for (int i = 0;i < n; ++i) {
        if (arr[i] == 1) {
            a_long += 2;
            two_count += 1;
        }
        else if (arr[i] == 2){
            a_long -= 1;
            two_count -= 1;
        }
        if (two_count == 0) {
            c_long = a_long * 2;
            if (c_long > max_long) {
                max_long  = c_long;
                max_long_pos = i+1;
            }
            c_long = 0;
            a_long = 0;
        }
    }
    max_long_pos = (max_long_pos - max_long) + 1;
    std::cout << max_depth << " " << max_pos << " " << max_long << " "<< max_long_pos;
    std::cout << "\n";
    return 0;

}

For the problem , I used every one that was entered as a sort of counter as to how many twos were expected. The code for finding the depth works out fine, but my motive behind finding the longest matching bracket was to sort of divide the input based on the count mentioned earlier.

Edit : Some of my variables were un-initializedn.Initializing all of them to 0 remediated the problem

Upvotes: 1

Views: 597

Answers (1)

chameleon123
chameleon123

Reputation: 63

There is a simple algorithm that solves your problem very easily.Just use stack (C++ has STL library that implemented stack efficiently). For evere open bracket '(' push to stack and for every closed bracket , pop from stack. If at the end stack is empty the sequence is valid and if it was empty and we saw a ) bracket or if it was not empty and we saw nothing, It is not matched. for nesting depth you can simply keep to variables current_nesting depths=0 and total_nesting_depth=0.Keep incrementing current_nesting depths for every '(' you see in a row till you reach ')'.Then update total_nesting_depth=max(total_nesting_depth,current_nesting depths) and refresh current_nesting depths=0 and redo this procedure till end of string. Sorry for answering very quickly. I will take a look at your code later and see if I can find where you went wrong.

Upvotes: 1

Related Questions