#include <iostream>
#include <stack>
using namespace std;
bool isValidParenthesis(string str){
stack<char>s;
for(int i=0;i < str.size();i++){
char ch=str[i];
if(ch=='(' || ch=='{' || ch=='[')
s.push(ch);
else{ // closing bracket
if(!s.empty()){
char top=s.top();
if((ch==')' && top=='(')||(ch=='}' && top=='{')||(ch==']' && top=='['))
s.pop();
else
return false;
}
else{//stack is empty
return false;
}
}
}
if(s.empty())
return true;
else
return false;
}
int main() {
string str1="{()}";
string str2="({(})";
cout<<isValidParenthesis(str1)<<endl;
cout<<isValidParenthesis(str2)<<endl;
return 0;
}