Expert.
Put your skills to the test.

Problem summary

Check four strings of round and square brackets after all other expression symbols have been erased. Round brackets cannot contain any brackets. Square brackets must contain at least one pair of round brackets and cannot be nested in any other pair. Return whether some valid expression can have exactly that bracket string.

Constraints

Each string contains 1..40 characters drawn from ()[].

Worked example

Official statement sample.

()[()][()()]
[()][(])
[([()])]
[()][(())()]

1
0
0
0

Solution analysis

1. The allowed strings are concatenations of units. A unit is either () or a square-bracket block containing one or more () units, namely [()...()]. This follows from the prohibition of round nesting and of any depth beyond two.
2. Parse from left to right. For an opening round bracket require the next character to be its closing bracket. For an opening square bracket consume at least one () pair and then require ]. Any other symbol or unconsumed malformed suffix is invalid.
3. The first sample is a concatenation of (), [()], and [()()], so it is possible. The last sample contains (()) inside a square block, which the parser rejects because a round pair must be immediate.

Why it works

Every valid mathematical bracket arrangement has exactly the unit grammar described above. The parser accepts exactly concatenations of these units. Conversely, put a variable inside every round pair and connect adjacent units by addition; every accepted string then comes from a valid expression.

Watch out. An empty square pair [] is invalid, even though it is balanced. Ordinary balanced-bracket checking alone is insufficient.

An independently written complete program with standard headers.

#include<iostream>
#include<string>
using namespace std;
bool valid(const string&s){
    int i=0;
    int n=s.size();
    while(i<n){
        // Valid top-level units are () and square blocks of one or more ().
        if(s[i]=='('){
            if(i+1>=n||s[i+1]!=')'){
                return false;
            }
            i+=2;
        }
        else if(s[i]=='['){
            ++i;
            int pairs=0;
            while(i+1<n&&s[i]=='('&&s[i+1]==')'){
                i+=2;
                ++pairs;
            }
            if(pairs==0||i>=n||s[i]!=']'){
                return false;
            }
            ++i;
        }
        else{
            return false;
        }
    }
    return true;
}
int main(){
    for(int test=0;test<4;++test){
        string s;
        cin>>s;
        cout<<valid(s)<<'\n';
    }
}