2

Добрый день, совсем недавно начал изучать рекурсивные алгоритмы и вот уже наткнулся на первые проблемы... Нашел задачку: Напишите рекурсивную функцию, проверяющую правильность расстановки скобок в строке. Получить написать рекурсивный алгоритм для проверки соответствия закрывающихся и открывающихся скобок, но не их порядка, к примеру в программе у меня выдает:
(()) - true
)( - true
())( - true
(())( - false

Вот листинг программы:

int check(const char* str, int i = 0) {
   switch (str[i]) {
      case '\0': return 0;
      case '(':  return check(str, i + 1) + 1;
      case ')':  return check(str, i + 1) - 1;
      default:   return check(str, i + 1) + 0;
   }
}
4
  • 1
    Это странная задача для рекурсии. рекурсия как раз была бы нужна, если бы требовалось определить и сбалансированность скобок, т.е. что бы закрывающие шли после открывающихся. А в этой задаче достаточно посчитать количество тех и других и сравнить его.
    – Mike
    4 ноя 2017 в 10:25
  • Я это и считал здесь, мне нужно проверить правильную вложенность скобок друг в друга
    – QuickDzen
    4 ноя 2017 в 10:30
  • вы как то сложно сформулировали вопрос, по нему как раз выходит что порядок вам не важен. по крайней мере из этой фразу "соответствия закрывающихся и открывающихся скобок, но не их порядка" выходит именно так
    – Mike
    4 ноя 2017 в 10:33
  • А если хотите проверить баланс, то пусть функция идет по строке, когда встречает открывающуюся скобку вызывает себя с остатком строки. если обнаруживает закрывающуюся скобку или конец строки то завершается и возвращает указатель (или позицию) на чем она остановилась. в случае если мы себя вызывали из за открывающейся скобки, а вызов вернул конец строки - то скобки не сбалансированы (закрывающая не найдена). Если вернулся не конец строки, просто продолжаем ее обход до конца со следующей позицией. по крайней мере это единственно приходит на ум, что тут можно делать именно рекурсией
    – Mike
    4 ноя 2017 в 10:39

1 ответ 1

4

Идем по строке со счетчиком, изначально равным 0. Встретив (, увеличиваем на 1. Для ) - уменьшаем. Если по дороге счетчик становится меньше 0 - значит, неверная вложенность, если на выходе не 0 - вся строка несбалансирована.

Если нужна именно рекурсия - но, в конце концов, можно и просто передавать в рекурсивный вызов значение счетчика :)

Что-то вроде:

bool checker(const char * s, int counter = 0)
{
    if (counter < 0) return false;

    for(;*s;++s)
        switch(*s)
        {
            case '(': return checker(s+1,counter+1);
            case ')': return checker(s+1,counter-1);
        }
    return (counter == 0);
}

int main(int argc, const char * argv[])
{
    cout << checker("(())") << endl;
    cout << checker(")(") << endl;
    cout << checker("())(") << endl;
    cout << checker("(())(") << endl;
}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.