Skip to content

Instantly share code, notes, and snippets.

@navin-mohan
Created January 21, 2017 13:37
Show Gist options
  • Save navin-mohan/e0a0f71f8569fa595333e44e146454ad to your computer and use it in GitHub Desktop.
Save navin-mohan/e0a0f71f8569fa595333e44e146454ad to your computer and use it in GitHub Desktop.
Bracket Matching C++ code
#include <iostream>
#include <stack>
using namespace std;
class bracket_matcher: public stack<char>{
public:
bracket_matcher(): stack<char>() { matching = 1;}
void push_bracket(const char &arg){
if(isOpeningBracket(arg) && isBracket(arg)){
stack<char>::push(arg);
}else if(isBracket(arg)){
matching = (!stack<char>::empty()) && stack<char>::top()==reverseBracket(arg);
if(matching)
stack<char>::pop();
}
}
bool isMatching() const { return matching; }
private:
bool matching;
bool isBracket(const char &c);
bool isOpeningBracket(const char &c);
char reverseBracket(const char &c);
};
char bracket_matcher::reverseBracket(const char &c){
switch(c){
case '}':return '{';
case ')':return '(';
case ']':return '[';
case '{':return '}';
case '(':return ')';
case '[':return ']';
default: return 0;
}
}
bool bracket_matcher::isOpeningBracket(const char &c){
switch(c){
case '{':
case '(':
case '[':return 1;
default:return 0;
}
}
bool bracket_matcher::isBracket(const char &c){
switch(c){
case '}':
case ')':
case ']':
case '{':
case '(':
case '[':return 1;
default:return 0;
}
}
int main(){
int t,i;
cin >> t;
for(int a0 = 0; a0 < t; a0++){
string s;
bracket_matcher b;
cin >> s;
for(i=0;i<s.length() && b.isMatching();++i){
b.push_bracket(s[i]);
}
cout << (b.isMatching() && b.empty()?"YES":"NO") << endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment