[Codility] Lesson7 - Stacks and Queues: Brackets

app.codility.com/programmers/lessons/7-stacks_and_queues/brackets/

Brackets coding task - Learn to Code - Codility

Problem

A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:

• S is empty;
• S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;
• S has the form "VW" where V and W are properly nested strings.

For example, the string "{[()()]}" is properly nested but "([)()]" is not.

Write a function:

class Solution { public int solution(String S); }

that, given a string S consisting of N characters, returns 1 if S is properly nested and 0 otherwise.

For example, given S = "{[()()]}", the function should return 1 and given S = "([)()]", the function should return 0, as explained above.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [0..200,000];
• string S consists only of the following characters: "(", "{", "[", "]", "}" and/or ")".

  Copyright 2009–2020 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

Solution(c++)

// you can use includes, for example:
#include <bits/stdc++.h>

using namespace std;

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(string &S) {
    // write your code in C++14 (g++ 6.2.0)
    int res;
    stack<char> st;

    for(int i=0; i<S.size(); i++){
        if(S[i]=='(' || S[i]=='[' || S[i]=='{'){
            st.push(S[i]);
        }else{
            if(st.empty()){
                return 0;
            }
            char char_last = st.top();
            st.pop();

            if(S[i] == ')' && char_last !='('){
                return 0;
            }else if(S[i] == '}' && char_last !='{'){
                return 0;
            }else if(S[i] == ']' && char_last !='['){
                return 0;
            }
        }
    }
    if(st.empty()){
        res = 1;
    }else{
        res = 0;
    }
    return res;
}

Test Result

app.codility.com/demo/results/trainingU9Y8GN-M34/

Test results - Codility