Как проверить сбалансированность открывающих и закрывающих символов?

Question

[campus1]

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

Решил я так => Code

Но недостатком есть то, что я никак не использую второй параметр (точнее не знаю, как его можно задействовать). Где и как его можно заюзать?

Answer 1

[Wataru]

Правильное решение такой обощенной задачи - использовать стек.

Надо первую строку обработать последовательно, символ за символом. При получении открывающего символа в строке надо его положить в стек. При получении закрывающего символа - надо проверить, что на вершине стека лежит правильный открывающий символ и удалить его из стека. В конце надо проверить, что стек пуст. Если стек не пуст в конце, или где-то в процессе работы в стеке был не тот символ - строка не сбалансированна.

Для удобства реализации из второго параметра нужно выделить "открывающие" и "закрывающие" символы. Удобно в массиве из 256 элементов пометить все открывающие как-то (например, -1), Все закрывающие надо пометить номером соответствующего открывающиего символа. Т.е. для второго параметра "()[]". Для всех символов в массиве будет 0, но для '(' и '[' - будет -1. Для ')' будет в массиве хранится '(', а для ']' - '['.

Тогда, при обработке символа из первой строки, если в массиве для него 0, то просто пропускаем. Если -1 - то кладем в стек. Если что-то другое, то проверяем, что это значение лежит в стеке на вершине.

Ваше решение по ссылке на работает на тесте "())("

Answer 2

[Евгений]

я на codewars решал так) ессесно можно расширить под любые скобки

function validBraces(b){
  let reg = /\(\)/g;
  b = b.replace(/[^\(\)]/g,'')
  
  return b.match(reg) != null ? validBraces(b.replace(reg,'')) : b === "" ? true : false;
}

console.log(validBraces("(Sensei saysno) (sd) (sdfsf"));

Comments

[Wataru]

Только одна проблема - ваше решение для сколько-нибудь длинных строк будет работать очень медленно. Удалять скобки по одной паре слишком долго. Плюс еще накладные расходы от регекспов.

[Евгений]

wataru, хехе - проблема программистов - пытаются решить все гипотетические проблемы))) не надо так делать... надо решать задачу ;) если задача изменится, то и алгоритм будет другой...

[Wataru]

В смысле? Не меняя задачу, просто подав вашей функции на вход что-то длиннее нескольких символов оно будет работать в десятки раз медленнее, чем оптимальное решение. Из-за таких "программистов без проблемы" , которые не решают никаких "гипотетических проблем)))" мы и имеем тормозящие программы, даже на топовом железе, каким бы быстрым оно не было.

Кстати, очевидно, что эта задача тестовая или соревновательная. Тут мало просто решить задачу как-то. Тут надо решить ее оптимально.

Answer 3

[Радость моя]

Я так понимаю это задачка на завершенность скобочной последовательности. Решение не напишу, т.к. некогда, но идею подскажу.
Вам нужно завести 2 переменные для каждого типа скобок (квадратные,круглые)
var _square, _circle = 0;
после чего пробежаться циклом по каждому символу в строке, и если встречается:

[ то _square++
] то _square--
( то _circle++
) то _circle--

соотвественно если после цикла у вас _square и _circle равны нулю - то скобки закрыты правильно, что собственно и проверяете:
return !(_square || _circle);

Comments

[campus1]

Радость моя Спасибо за подсказку. Идею я понял, но как мне применить второй параметр, то есть эту самую завершенную последовательность.

[campus1]

Радость моя
Правильно я вас понимаю?

function isBalanced(str, condition) {
    let square, cirle = 0;
    for (let i = 0; i < str.length; i++) {
        let char = str[i];
        switch (char) {
            case "(":
                cirle++;
                break;
            case ")":
                cirle--;
                break;
            case "[":
                square++;
                break;
            case "]":
                square--;
                break;
        }
    }
    return !(square || cirle);
}

[Радость моя]

@campus1

1. объявить переменную стоимости (cost = 0)
как вариант разобрать условие в объект, и назначить каждому виду скобок свою стоимость, и в цикле перебора строки проверять если символ совпадает с ключом из объекта условий, то плюсовать/минусовать cost на значение ключа который совпадает с этим символом.
только стоимость каждой скобки нужно наверно сделать по степени двойки (1, 2, 4, 8, 16..) чтобы не было так что [ у которой стоимость например 2 не заменила собой две (( у которых стоимость 1.
или я хрень несу и можно сделать все проще.

[campus1]

Радость моя, Попробую как вариант, спасибо!

[Владимир Олохтонов]

(][), )][(, ([)] - используй стек, Люк!
PS: это - неправильные скобочные последовательности.