# Using STL to verify brackets or parentheses combination in an expression

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.

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;
}

```

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Scroll to Top