[Codility] Lesson 7 - Nesting

Task discription

A string S consisting of N characters is called properly nested if:

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

For example, string "(()(())())" is properly nested but string "())" isn't.

Write a function:

int solution(string &S);

that, given a string S consisting of N characters, returns 1 if string 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..1,000,000];
• string S consists only of the 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.push(S[i]);
        }
        else {
            if(s.empty()) return 0;
            s.pop();
        }
    }
    if(s.empty()) return 1;
    return 0;
}