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.

[showads ad=inside_post]

Bracket combinations to be used,

Advertisements
  • { , }
  • [,]
  • (,)

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

Do you want to Learn Modern C++ from best?

We have curated a list of Best C++ Courses, that will teach you the cutting edge Modern C++ from the absolute beginning to advanced level. It will also introduce to you the word of Smart Pointers, Move semantics, Rvalue, Lambda function, auto, Variadic template, range based for loops, Multi-threading and many other latest features of C++ i.e. from C++11 to C++20.

Check Detailed Reviews of Best Modern C++ Courses

Remember, C++ requires a lot of patience, persistence, and practice. So, start learning today.

Leave a Comment

Your email address will not be published.

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

Scroll to Top