Задача с фигурными скобками, скобками и скобками

Question

Задача состоит в том, чтобы проверить, содержит ли данная строка сбалансированные наборы {}, [] и ().

Например, check("{[}]") должен вернуть false и check("{[]()}") должны вернуть true и т.д.

Решение:

bool check(const std::string & s) 
{ 
    constexpr auto brackets1 = "()"; 
    constexpr auto brackets2 = "[]"; 
    constexpr auto brackets3 = "{}"; 
    constexpr size_t brackets_pair_size = 2; 
    constexpr auto brackets = "()[]{}"; 

    std::string s2; 

    for (auto & c : s) 
    { 
     if (strchr(brackets, c) != nullptr) 
     { 
      s2 += c; 
     } 
    } 

    auto brackets1_pos{ std::string::npos }; 
    auto brackets2_pos{ std::string::npos }; 
    auto brackets3_pos{ std::string::npos }; 

    while ((brackets1_pos = s2.find(brackets1)) != std::string::npos || 
      (brackets2_pos = s2.find(brackets2)) != std::string::npos || 
      (brackets3_pos = s2.find(brackets3)) != std::string::npos 
      ) 
    { 
     if (brackets1_pos != std::string::npos) { 
      s2.erase(brackets1_pos, brackets_pair_size); 
      continue; 
     } 

     if (brackets2_pos != std::string::npos) { 
      s2.erase(brackets2_pos, brackets_pair_size); 
      continue; 
     } 

     if (brackets3_pos != std::string::npos) { 
      s2.erase(brackets3_pos, brackets_pair_size); 
      continue; 
     } 
    } 

    return s2.empty(); 
} 

Идея такова: - скопировать все Парс, скобки и фигурные скобки на другую строку, - удалите пары скобок из второй строки, - проверьте, нет ли второй строки.

Есть ли способ улучшить алгоритм?

Может быть какое-то универсальное регулярное выражение?

Answer 1

Проверка на Вложенные брекеты выглядят как натуральный футляр для std::stack. Нажимайте скобки на стек, когда вы перебираете вход и проверяете правильные совпадения, когда вы видите закрывающую фигуру.

bool check(const std::string &expression) // balanced and nested? 
{ 
    std::stack<char> stack; 

    for (auto ch : expression) { 
     switch (ch) { 
     case '(': // open parenthesis 
     case '<': // open angle 
     case '[': // open bracket 
     case '{': // open brace 
      stack.push(ch); 
      break; 
     case ')': // close parenthesis 
      if (stack.empty() || stack.top() != '(') return false; 
      stack.pop(); 
      break; 
     case '>': // close angle 
      if (stack.empty() || stack.top() != '<') return false; 
      stack.pop(); 
      break; 
     case ']': // close bracket 
      if (stack.empty() || stack.top() != '[') return false; 
      stack.pop(); 
      break; 
     case '}': // close brace 
      if (stack.empty() || stack.top() != '{') return false; 
      stack.pop(); 
      break; 
     } 
    } 
    return stack.empty(); // no unmatched braces left? 
} 

Answer 2

Эта задача не справляется с регулярным выражением, потому что у них нет памяти и невозможно запомнить глубину скобок.

Для выполнения задачи необходимо использовать синтаксический анализатор, возможно, recursive descent parser.

Грамматика будет выглядеть следующим образом (не проверено):

input: /* empty */ 
    | expr input 

expr: paren-expr 
    | bracket-expr 
    | curly-bracket-expr 

paren-expr: '(' input ')' 

bracket-expr: '[' input ']' 

curly-bracket-expr: '{' input '}' 

Пример кода:

#include <iostream> 
#include <iterator> 
#include <string> 


class parenthesis_checker { 

    template <class It> 
    It parse_open_close(It first, It last, char op, char cl) const { 
    if(op != *first) return first; 

    It r = parse_input(first+1, last); 
    if(last == r) return first; 
    if(cl != *r) return first; 

    return r+1; 
    } 

    template <class It> 
    It parse_expr(It first, It last) const { 
    It r = parse_open_close(first, last, '(', ')'); 
    if(r != first) return r; 

    r = parse_open_close(first, last, '[', ']'); 
    if(r != first) return r; 

    r = parse_open_close(first, last, '{', '}'); 
    if(r != first) return r; 

    return first; 
    } 

    template <class It> 
    It parse_input(It first, It last) const { 
    while(first != last) { 
     It r = parse_expr(first, last); 
     if(r == first) return r; 
     first = r; 
    } 
    return first; 
    } 

public: 
    template <class It> 
    bool operator()(It first, It last) const { 
    return last==parse_input(first, last); 
    } 

    template <class Cont> 
    bool operator()(Cont value) const { 
    return (*this)(value.begin(), value.end()); 
    } 

    bool operator()(const char* str) const { 
    return (*this)(std::string(str)); 
    } 
}; 


int main() { 
    parenthesis_checker check; 

    std::cout << check("{[}]") << std::endl; 
    std::cout << check("{[]()}") << std::endl; 
} 

Answer 3

Ваше решение кажется усложненной, и я должен признать, что я не пытался слишком трудно понять это, но для меня не очевидно, что это даже правильно. Очень простое решение этой проблемы - создать стек и пройти через строку, открыв скобки в стек и выскочить из стека при закрытии круглых скобок (когда вы попсете, вы должны проверить, что совпадающие и открывающиеся круглые скобки совпадают).

К сожалению, решить эту проблему с помощью регулярных выражений невозможно, так как язык хорошо сбалансированных круглых скобок не является regular.

Answer 4

Вы можете проверить соответствующие скобки, выполнив простой код.

int bracketMatcher(string s) 
{ 
    list<int> *countsList = new list<int>(); 
    string expression = s; 
    int correctBrackets = 1; 

    for (int index = 0; index < expression.size(); index++) { 
     char ch = expression[index]; 
     if (ch == '(') 
     { 
      countsList->push_back(index); 
     } 
     else if (ch == ')') 
     { 
      if (countsList->size() == 0) 
      { 
       correctBrackets = 0; 
       break; 
      } 
      countsList->pop_back(); 
     } 
    } 
    if (countsList->size() != 0) 
    { 
     correctBrackets = 0; 
    } 
    return correctBrackets; 
} 

или если вы хотите найти конкретный тип скобок, то также можете использовать следующую функцию.

bool bracketMatcher(string s , char c) 
{ 
    list<int> *countsList = new list<int>(); 
    string expression = s; 
    bool correctBrackets = true; 

    char secondCh =' '; 
    switch (c) { 
     case '(': // open parenthesis 
      secondCh = ')'; 
      break; 
     case '<': // open angle 
      secondCh = '>'; 
      break; 
     case '[': // open bracket 
      secondCh = ']'; 
      break; 
     case '{': // open brace 
      secondCh = '}'; 
      break; 
     default: 

      break; 
    } 
    for (int index = 0; index < expression.size(); index++) { 
     char ch = expression[index]; 
     if (ch == c) 
     { 
      countsList->push_back(index); 
     } 
     else if (ch == secondCh) 
     { 
      if (countsList->size() == 0) 
      { 
       correctBrackets = false; 
       break; 
      } 
      countsList->pop_back(); 
     } 
    } 
    if (countsList->size() != 0) 
    { 
     correctBrackets = false; 
    } 
    return correctBrackets; 
} 
int main() { 

    string s = " ((hello) (()) llll {}word <aaa>(aad))"; 
    //always specify the opening bracket here 

    bool parenthesisMatch = bracketMatcher(s,'('); 
    bool angleBracketsMatch = bracketMatcher(s,'<'); 
    bool bracketMatch = bracketMatcher(s,'['); 
    bool bracesMatch = bracketMatcher(s, '{'); 

    if(parenthesisMatch && angleBracketsMatch && bracketMatch && bracesMatch) { 
     cout << "found all matching brackets" << endl; 
    } 
    else{ 
     cout << "could not find all matching brackets" << endl; 
    } 
    return 0; 
}