In this we will see how to check if a given string take valid combination of open and close brackets i.e.
(4+{8-[22+8]*}] contains valid order of open and close brackets.
({5+8]) contains invalid combination of open and close brackets.
[showads ad=inside_post]
Bracket combinations to be used,
- { , }
- [,]
- (,)
Algo Used:
- Create a empty stack of characters
- Traverse characters in string one by one.
- If any open bracket is encountered, then push that in stack
- If any type of close bracket is encountered then match it’s open bracket counterpart with top of stack.
- If match is successful then pop character from stack.
- If match is unsuccessful then RETURN FALSE.
- If stack is empty RETURN TRUE;
- If stack is not empty RETURN FALSE;
Code is as follows,
#include <iostream> #include <string> #include <stack> #include <map> #include <iterator> using namespace std; bool isOpenBracket(char val, map<char, char> mapOfBrackets) { map<char, char>::iterator it = mapOfBrackets.begin(); while(it != mapOfBrackets.end()) { if(it->second == val) { return true; } it++; } return false; } bool testBracket(string s) { stack<char> bracketStack; map<char, char> bracketMap; bracketMap['}'] = '{'; bracketMap[')'] = '('; bracketMap[']'] = '['; for(int i = 0; i < s.size(); i++) { if(isOpenBracket(s[i], bracketMap)) bracketStack.push(s[i]); if(bracketMap.find(s[i]) != bracketMap.end()) { if(bracketStack.empty()) return false; if(bracketStack.top() != bracketMap[s[i]]) { return false; } else bracketStack.pop(); } } if(bracketStack.size() > 0) return false; else return true; } int main() { cout<<testBracket("([(2+11)]+)")<<endl; return 0; }