// Example from
// http://scientopia.org/blogs/goodmath/2011/04/26/the-next-step-in-computation-level-2-languages/#comments

#include <stack>

#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cassert>

using namespace std;

bool parse(const char *input) {
    
    int len = strlen(input);
    
    stack<char> myStack;
    
    for (int i=0; i<len; i++) {
        
        if(input[i] == 'I') { // simply consume I
            
            continue;
        
        } else if(input[i] == '(') {
        
            myStack.push('(');
        
        } else if(input[i] == ')') {
        
            if(myStack.top() == '(') {
            
                myStack.pop();
            
            } else {
            
                printf("No closing bracket found at %i.\n", i);
                return false;
            }
            
        } else {
            
            printf("Character %c not allowed.\n", input[i]);
            return false;
        }
    }
    
    if(myStack.size() == 0) {
        return true;
    } 
    
    return false;
}

int main() {
    
    const char *valid1 = "()";
    const char *valid2 = "((I)(((I)I)(II)))";
    const char *valid3 = "IIII";
    
    assert(parse(valid1));
    assert(parse(valid2));
    assert(parse(valid3));
    
    const char *invalid1 = "(";
    const char *invalid2 = "((I)(((I)I)(II))";
    
    assert(!parse(invalid1));
    assert(!parse(invalid2));
    
    return 0;
}