BracketsInclusion.cpp

#include <iostream>
#include <string>

using namespace std;

bool BracketsInclusion(string str){
	int length = str.length();
	// Remove everything besides brackets
	string bstr ="";
	for(int i = 0; i<length; i++){
		if(str[i]=='{'||str[i]=='}'||str[i]=='['||str[i]==']'||str[i]=='('||str[i]==')')
			bstr = bstr+str[i];
	}
	if(bstr.length()==0)
		return true;
	
	if(bstr.length()%2==1)
		return false;
		
	str = bstr;
	while(true){
		if(str.length()==0)
			break;
		int pos;
		pos = str.find("()");
		if(-1 != pos){
			str.erase(pos,2);
			continue;
		}
		pos = str.find("{}");
		if(-1 != pos){
			str.erase(pos,2);
			continue;
		}
		pos = str.find("[]");
		if(-1 != pos){
			str.erase(pos,2);
			continue;
		}
		return false;
	}
	
	
	// Priority
	str = bstr;
	
	if(str.find("[{")!=-1)
		return false;
	if(str.find("}]")!=-1)
		return false;
	if(str.find("({")!=-1)
		return false;
	if(str.find("})")!=-1)
		return false;
	if(str.find("([")!=-1)
		return false;
	if(str.find("])")!=-1)
		return false;
	
	
	if(str.find("((")!=-1)
		return false;
	if(str.find("))")!=-1)
		return false;
	if(str.find("{{")!=-1)
		return false;
	if(str.find("}}")!=-1)
		return false;
	if(str.find("[[")!=-1)
		return false;
	if(str.find("]]")!=-1)
		return false;
		
	return true;
	
}

int main(){

	string legal1="2*(5+4)/6";
	string legal2="48 / [2*(1+2) * (3+4)]";
	string legal3="26* {2 + [34 * (6-2)]/3 }";
	
	string nlegal1="2 * (5+(5+4) / 6)";
	string nlegal2="2 * (5+4 / 6";
	string nlegal3="48 / (2*[1+2] )";
	string nlegal4="26* {2 + [34 * (6-2)/3 } }";
	
	cout << legal1 << " - " << (BracketsInclusion(legal1)?"true":"false") << endl;
	cout << legal2 << " - " << (BracketsInclusion(legal2)?"true":"false") << endl;
	cout << legal3 << " - " << (BracketsInclusion(legal3)?"true":"false") << endl;
	
	cout << nlegal1 << " - " << (BracketsInclusion(nlegal1)?"true":"false") << endl;
	cout << nlegal2 << " - " << (BracketsInclusion(nlegal2)?"true":"false") << endl;
	cout << nlegal3 << " - " << (BracketsInclusion(nlegal3)?"true":"false") << endl;
	cout << nlegal4 << " - " << (BracketsInclusion(nlegal4)?"true":"false") << endl;
	return 0;
}