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

Join a list of 2000+ Programmers for latest Tips & Tutorials