Как проверить правильность вложенности скобок в строке, например, "((([])){})"? 

Как определить правильность вложенности символов `()`, `[]`, `{}` в строке, как в примерах с переменными `str`, `str2`, `str3` и `str4`? Мне удается решить все случаи, кроме строки `((([])){})`. Как можно эффективно выполнить поиск и проверку такой вложенной структуры в строке? Можно ли улучшить решение, избегая рекурсивного использования `replace`? Ссылка на текущее решение помогла, но в поисках оптимального способа.
  • 27 апреля 2024 г. 16:00
Ответы на вопрос 2 
Для проверки правильности вложенности скобок можно использовать следующий подход:
1. Создать стек, в который будем помещать открывающие скобки.
2. Пройти по каждому символу в строке.
3. Если символ - открывающая скобка (`(`, `[`, `{`), поместить её в стек.
4. Если символ - закрывающая скобка (`)`, `]`, `}`), проверить, что она соответствует последней открывающей скобке в стеке. Если да, удалить последнюю открывающую скобку из стека и продолжить проверку. Если нет, значит скобки в строке расставлены неправильно.
5. После проверки всех символов в строке, проверить, что стек пуст. Если да, то вложенность скобок верна.

Пример кода на Python:

```python
def check_brackets(input_string):
    stack = []
    brackets_map = {
        '(': ')',
        '[': ']',
        '{': '}'
    }
    
    for char in input_string:
        if char in brackets_map:
            stack.append(char)
        elif char in brackets_map.values():
            if not stack or brackets_map[stack.pop()] != char:
                return False
    
    return not stack

str = "((([])){}"
print(check_brackets(str))  # Выведет False
str2 = "([])"
print(check_brackets(str2))  # Выведет True
str3 = "({[]})"
print(check_brackets(str3))  # Выведет True
str4 = "({[})"
print(check_brackets(str4))  # Выведет False
```

Этот код эффективно проверяет правильность вложенности скобок в строке, используя стек для отслеживания открывающих скобок. Улучшить его можно, например, добавив дополнительную проверку на конец строки, чтобы исключить случаи, когда в строке больше открывающих, чем закрывающих скобок.
<pre><code class="javascript">/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
    //hash function for partheses
    let map = { "}": "{", "]": "[", ")": "(" };
    let temp = [];



    //Iterates
    for(i in s){
        //if a index that matches a closing bracket - continue
        if(s[i] in map){
            //if the temp isn't empty, and the top of the stack is that closing bracket - pop it
            if(temp.length &gt; 0 &amp;&amp; temp[temp.length-1] === map[s[i]]){
                temp.pop();
            }
            //else we break it - return false
            else{
                return false;
            }
        }
        //else we push the opening bracket onto the stack
        else{
            temp.push(s[i]);
        }
    }
    //else we return true if the temp is empty
    return temp.length === 0;
};</code></pre> <br/> <br/> Прямо в литкоде есть решения, можно открыть Solutions, отфильтровать по языку и читать с описанием, можно перейти к all submissions и выбрать самое быстрое решение.
Похожие вопросы
    Показать ещё