BalancedSmiley_Fail

//Balanced Smileys

#include <iostream>
#include <string>
#include <cctype>
#include <exception>

#define DEBUG

using namespace std;

bool isValidChar(char c){
    if(c == '\0')
        return false;

    char *validStr = "abcdefghijklmnopqrstuvwxyz: ";
    return (strchr(validStr, c) != NULL);
}

bool solve(const char *line, unsigned int s, unsigned int e){
#ifdef DEBUG
    cout << "Solve for: ";
    for(unsigned int i = s; i < e; i++){
        cout << line[i] << " ";
    }
    cout << endl;
#endif

    unsigned int len = e - s;
    if(len <= 0){
#ifdef DEBUG
        cout << "YES: zero length" << endl;
#endif
        return true;
    }

    for (unsigned int indx = s; indx < e; indx++) {
        char c = line[indx];
        if(isValidChar(c)){
            continue;
        }

        if(c != '(' && c != ')'){
#ifdef DEBUG
            cout << "NO: some invalid char" << endl;
#endif
            return false;
        }

        //case ( or )

        //no prob: :) or :(
        if(indx > 0 && line[indx-1] == ':'){
            continue;
        }


        if(c == ')'){

#ifdef DEBUG
            cout << "NO: unbalanced )" << endl;
#endif
            return false;
        }else if(c == '('){
            //find index for corresponding ) backwards
            unsigned int rindx = indx+1;
            unsigned int rindxes[2];    //kinda stack
            int rindxes_ptr = 0;
            for(; rindx < e; rindx++){
                if(line[rindx] == ')'){
                    if(rindx > 0 && line[rindx-1]!=':'){
                        break;  //index found
                    }
                }
            }

            if(rindx < e){
                //found. Solve for substr
                if(solve(line, indx+1, rindx)){
                    indx = rindx;
                }else{
#ifdef DEBUG
                    cout << "NO: substr not solvable" << endl;
#endif
                    return false;
                }
            }else{
#ifdef DEBUG
                cout << "NO: unbalanced (" << endl;
#endif
                return false;
            }
        }

    }
#ifdef DEBUG
    cout << "YES: passed all test" << endl;
#endif
    return true;
}

bool solve(string &line){
                                                        cout << "< " <<line << " >      ";
    //empty string
    unsigned int len = line.length();
    if(len == 0){
                                                        cout << "YES: zero length " << endl;
        return true;
    }

    for(unsigned int i = 0; i < len; i++){
        if(line[i] == '('){
            bool balanced = false;
            if((i > 0) && (line[i-1] == ':')){
                balanced = true;                            cout << ":( ";
            }
            for(unsigned int j = i+1; !balanced && j < len; j++){
                if(line[j] == ')'){
                    balanced = true;                        cout << "(..) ";
                    if(j+1<len){
                        i = j+1;
                    }else{                              cout << "eol ";
                        return true;
                    }
                    break;
                }else if(!isValidChar(line[j])){            cout << "invalid char = " << line[j] << " ";
                    return false;
                }
            }
            if(!balanced){                              cout << "unbalanced ( ";
                return false;
            }
        }else if(line[i] == ')'){
            bool balanced = false;
            if((i > 0) && (line[i-1] == ':')){
                balanced = true;                            cout << ":) ";
            }
            if(!balanced){                              cout << "unbalanced ) ";
                return false;
            }
        }else if(!isValidChar(line[i])){                    cout << "invalid char = " << line[i] << " ";
            return false;
        }
    }

    cout << "YES: passed all test";
    return true;

}

class solution : public exception{
public:
    solution(string &m) : msg(m){
    }

private:
    virtual const char *what() const throw(){
        return msg;
    }
    string msg;
};

unsigned int solve_rec(string &line, unsigned int indx_start){
    unsigned int indx = indx_start;

    for (; indx < line.length(); indx++) {
        char c = line[indx];
        if(!isValidChar(c) && (c != '(' || c != ')')){
            throw solution("Invalid char: NO");
        }

        if(c == '('){
            indx = solve_rec(line, indx+1);
        }else if(c == ')'){
            return indx;
        }
    }

    return indx;
}

int main(int argc, char **argv){
    string line;
    getline(cin, line);
    int t_cases = atoi(line.c_str());
    for(int cno = 0; cno < t_cases; cno++){
        getline(cin, line);
        cout << "Case #" << cno+1 << ": " << (solve(line.c_str(), 0, line.length())?"YES":"NO") << endl;
    }
    return 0;
}