大括号，括号和括号的任务 [英] Task with braces, brackets and parenthesis

问题描述

任务是检查给定的字符串是否包含均衡的 {} ， [] 和()组.

Task is to check if given string contains balanced sets of {}, [] and ().

例如， check("{[}]")必须返回 false 和 check("{[]()}")必须返回 true 等.

For example, check("{[}]") must return false, and check("{[]()}") must return true, etc.

解决方案:

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

想法是:-将所有的标准杆，方括号和大括号复制到另一个字符串中，-从第二个字符串中删除成对的括号，-检查第二个字符串是否为空.

Idea is: - copy all pars, brackets and braces to another string, - remove pairs of brackets from second string, - check if second string is empty.

有什么方法可以改善算法吗?

Is there any way to improve the algorithm?

可能是一些通用正则表达式吗?

May be some universal regex?

推荐答案

检查嵌套大括号似乎是 std :: stack 的自然情况.在输入上进行迭代时，将花括号推入堆栈，并在看到闭合花括号时测试是否正确匹配.

Checking for nested braces seems like a natural case for std::stack. Push braces onto the stack as you iterate over the input and test for correct matches when you see a closing brace.

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

这篇关于大括号，括号和括号的任务的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！