带大括号，括号和括号的任务

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