[Codility] Lesson7 - Brackets

Task discription

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:

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 ")".

Source code

#include <algorithm>
#include <stack>

int solution(string &S) {
    int n = S.size();
    stack<int> s;
    for(int i=0;i<n;i++) {
        if(S[i] == '{' || S[i] == '[' || S[i] == '(') {
            s.push(S[i]);
        }
        else {
            if(s.empty()) return 0;
            if(S[i] == '}' && s.top() == '{') {
                s.pop();
            }
            else if(S[i] == ']' && s.top() == '[') {
                s.pop();
            }
            else if(S[i] == ')' && s.top() == '(') {
                s.pop();
            }
        }
    }

    if(s.empty()) return 1;
    return 0;
}