Check whether a set of brackets consisting of parenthesis, square brackets, and Curly brackets are valid or not?

Question

I have a small problem here: Our teacher asked us to write a program that checks whether parenthesis, square brackets, and Curly brackets are valid. eg: [[{{{(())}}}]] is a valid usage but ())), [[((]])) (the latter are interleaved here) are invalid.

Here is my try:

int main(){
    string input;
    cout << "Enter a text: "
    cin >> input;

    int nSquareBracketRight = count(s.begin(), s.end(), '[');

    int nSquareBracketLeftt = count(s.begin(), s.end(), ']');

    if(nSquareBracketRight != nSquareBracketLeft)
        cout << "Invalid!" << endl;
    else
        cout << "Valid Usage!" << endl;

    return 0;
}

It looks ok above but if the occurrences are equal but if a "Closing" one is in the smaller index then it is considered invalid eg: {}}{ Invalid.

Please help and thank you, guys!

Answer 1

It is really easy to achieve: Let's say you have an input like this: ([{}]) it is considered correct isn't it? but ([)] is invalid.

In the correct one you can see in some point that element i is an opening bracket and element i + 1 is a closing bracket of the same family of brackets. Which is considered valid So the trick is to remove this subset brackets until the stack/vector is empty. If so then the whole input is correct otherwise is invalid.

• Tip: inside a loop erase element i and element i + 1 if only and if element i is opening and element i + 1 is closing and element i and element i + 1 are of the same family eg: {}, [], ().

  #include <iostream>
  #include <string>
  #include <vector>
  
  
  int main(){
  
      std::string str = "[({}{})]"; // valid
  //  std::string str = "["; // invalid
  //  std::string str = "[(])"; // invalid
  //  std::string str = "[({}{})]]"; // invalid
  //  std::string str = "[({}{}])"; // invalid
  //  std::string str = "{{}[{}]{(())}}"; // valid
  //  std::string str = "][(){}"; // invalid
      std::vector<char> vecStr;
      bool isDone = false;
  
  
      for(auto i(0); i != str.length(); ++i)
          vecStr.push_back(str[i]);
  
      for(auto i(0); i != vecStr.size(); ++i)
          std::cout << vecStr[i];
      std::cout << std::endl;
  
      for(auto i(0); i < str.length() / 2 && !isDone; ++i){
          for(auto j(0) ; j < vecStr.size() - 1; ++j){
              if(!vecStr.size()){
                  isDone = true;
                  break;
              }
              switch(vecStr[j]){
                  case '{':
                      if(vecStr[j + 1] == '}'){
                          vecStr.erase(&vecStr[j]);
                          vecStr.erase(&vecStr[j]);
                      }
                  break;
                  case '(':
                      if(vecStr[j + 1] == ')'){
                          vecStr.erase(&vecStr[j]);
                          vecStr.erase(&vecStr[j]);
                      }
                  break;
                  case '[':
                      if(vecStr[j + 1] == ']'){
                          vecStr.erase(&vecStr[j]);
                          vecStr.erase(&vecStr[j]);
                      }
                  break;
              }
          }
      }
  
      std::cout << "size: " << vecStr.size() << std::endl;
  
      if(vecStr.size())
          std::cout << "Invalid Input!" << std::endl;
      else
          std::cout << "valid Input!" << std::endl;
  
      std::cout << std::endl;
      return 0;
  }
  

• just switch uncommenting the input lines above and see the result. Or input it using std::cin.

Answer 2

This is the kind of situation that a stack is good for, such as std::stack, eg:

#include <iostream>
#include <string>
#include <stack>
using namespace std;

bool areBracketsValid(const string &input)
{
    stack<char> stk;

    for(string::size_type i = 0; i < input.size(); ++i)
    {
        char ch = input[i];
        switch (ch)
        {
            case '(':
            case '[':
            case '{':
            {
                stk.push(ch);
                break;
            }

            case ')':
            case ']':
            case '}':
            {
                if (stk.empty())
                    return false;
                char openingCh = (ch == ')') ? '(' : (ch == ']') ? '[' : '{';
                if (stk.top() != openingCh)
                    return false;
                stk.pop();
                break;
            }
        }
    }

    return stk.empty();
}

int main()
{
    string input;
    cout << "Enter a text: ";
    cin >> input;

    if (areBracketsValid(input))
        cout << "Valid Usage!" << endl;
    else
        cout << "Invalid!" << endl;

    return 0;
}

Live Demo

Answer 3

• Using std::count is good but that is not what you need here in your program; You need something that is interested in the indexes moreover.

  You can declare for each type of brackets a variable that holds the number of its occurrences and inside a loop increment the target variable if it matches the tested character.

  And right inside the loop after increment check whether the opening bracket number is smaller than the closing, if so it is considered an invalid one eg: (()))( As you can see above the number of opening and closing is OK but it is considered an invalid usage as the fact that a never a parenthesis begins with a closing one!

  So break the loop signaling the invalid usage.

  finally compare the number of opening and closing ones outside the loop, that is it because inside a loop we can open n parenthesis so the checking is only after the loop ends to get the number of closing ones. eg: (([[[{{{ cannot be checked inside the loop.

  #include <iostream>
  #include <string>
  
  int main(){
  
      std::string str;
      std::cin >> str;
  
      int nParR = 0, nParL = 0, nBrackR = 0, 
      nBrackL = 0, nCurlR = 0, nCurlL = 0;
  
      for(auto i(0); i != str.length(); ++i){
          switch(str[i]){
              case '(':
                  nParR++;
              break;
              case ')':
                  nParL++;
              break;
              case '[':
                  nBrackR++;
              break;
              case ']':
                  nBrackL++;
              break;
              case '{':
                  nCurlR++;
              break;
              case '}':
                  nCurlL++;
              break;
          }
  
          if(nParR < nParL || nBrackR < nBrackL || 
          nCurlR < nCurlL){
              std::cout << "Invalid usage!" << std::endl;
              break;
          }
      }
  
      if(nParR == nParL && nBrackR == nBrackL && nCurlR == nCurlL)
          std::cout << "Valid usage!" << std::endl;
      else
          std::cout << "Invalid Usage!";
  
  
  
      std::cout << std::endl;
      return 0;
  }