Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
hardyaw
1 / 1 / 2
Регистрация: 10.09.2015
Сообщений: 99
1

Используя рекурсию, определить правильность размещения скобок

03.12.2016, 12:11. Просмотров 632. Ответов 24
Метки нет (Все метки)

Написать программу, что определяет правильность размещения трьох видов скобок ( ), [ ], { }. Использовать рекурсию
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.12.2016, 12:11
Ответы с готовыми решениями:

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

Написать парсер текста, проверяющий правильность расстановки скобок, используя стек и файловый ввод/вывод
Дан текстовый файл INPUT.TXT. Проверить в тексте файла правильности расстановки открывающих и...

В файле находится текст программы на Паскале. Используя стек, проверить правильность вложений операторных скобок (begin - end) в этой программе
В файле находится текст программы на Паскале. Используя стек, проверить правильность вложений...

Определить сумму элементов массива, используя рекурсию
Определить сумму элементов массива. используя рекурсию функции #include <stdio.h> #include...

Определить правильность даты, введенной с клавиатуры, не используя циклы
Условие задачи: Определить правильность даты, введенной с клавиатуры, не используя циклы. ...

24
amaralikyr
70 / 67 / 67
Регистрация: 18.09.2015
Сообщений: 234
Завершенные тесты: 1
03.12.2016, 12:36 2
Что есть "правильное размещение"?
0
hardyaw
1 / 1 / 2
Регистрация: 10.09.2015
Сообщений: 99
03.12.2016, 12:44  [ТС] 3
amaralikyr, что они являються закрытыми, () - правильное, (() - неправильное
0
IchimaruGin
79 / 79 / 44
Регистрация: 14.07.2013
Сообщений: 401
Завершенные тесты: 1
03.12.2016, 12:48 4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <string>
 
using namespace std;
 
bool braces_ok(string a, int idx){
    static int braces_count[3] = {0};
    if(idx == a.size()){
        for(int i = 0; i < 3; i++)
            if(braces_count[i] != 0)
                return false;
        return true;
    }
    switch(a[idx]) {
        case '(':
            braces_count[0]++;
            break;
        case ')':
            if(braces_count[0] == 0)
                return false;
            braces_count[0]--;
            break;
        case '[':
            braces_count[1]++;
            break;
        case ']':
            if(braces_count[1] == 0)
                return false;
            braces_count[1]--;
        case '{':
            braces_count[2]++;
            break;
        case '}':
            if(braces_count[2] == 0)
                return false;
            braces_count[2]--;
        braces_ok(a,idx + 1);
    }
}
 
int main() {
    string a = "(({{{[[[[]]]]}}}))";
    cout << boolalpha << braces_ok(a,0);
}
Добавлено через 2 минуты
на всякий случай напишу: true правильно , falseне правильное размещение скобок)
0
03.12.2016, 12:48
hardyaw
1 / 1 / 2
Регистрация: 10.09.2015
Сообщений: 99
03.12.2016, 12:54  [ТС] 5
IchimaruGin, ну это же итерационное решение, я так знаю как решить
0
IchimaruGin
79 / 79 / 44
Регистрация: 14.07.2013
Сообщений: 401
Завершенные тесты: 1
03.12.2016, 12:55 6
hardyaw, ты знаешь что такое рекурсия?
0
hardyaw
1 / 1 / 2
Регистрация: 10.09.2015
Сообщений: 99
03.12.2016, 13:06  [ТС] 7
IchimaruGin, функция, вызывающая саму себя
0
IchimaruGin
79 / 79 / 44
Регистрация: 14.07.2013
Сообщений: 401
Завершенные тесты: 1
03.12.2016, 13:12 8
hardyaw, рекурсивная функция это та что вызывает саму себя.
Цитата Сообщение от IchimaruGin Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
bool braces_ok(string a, int idx)
{
    static int braces_count[3] = { 0 };
    if (idx == a.size()) {
        for (int i = 0; i < 3; i++)
            if (braces_count[i] != 0)
                return false;
        return true;
    }
    switch (a[idx]) {
    case '(':
        braces_count[0]++;
        break;
    case ')':
        if (braces_count[0] == 0)
            return false;
        braces_count[0]--;
        break;
    case '[':
        braces_count[1]++;
        break;
    case ']':
        if (braces_count[1] == 0)
            return false;
        braces_count[1]--;
    case '{':
        braces_count[2]++;
        break;
    case '}':
        if (braces_count[2] == 0)
            return false;
        braces_count[2]--;
        braces_ok(a, idx + 1); // вот вызов функции braces_ok из braces_ok
    }
}
что не так?

Добавлено через 4 минуты
блин только надо вынести ее за пределы switch'a

Добавлено через 37 секунд
и добавить break
0
hardyaw
1 / 1 / 2
Регистрация: 10.09.2015
Сообщений: 99
03.12.2016, 13:12  [ТС] 9
IchimaruGin, ну это понятно, а можно как то сделать не свитчем? например 3 функции которые отвечают за каждую из скобок, но я не могу додуматься что в них написать
0
IchimaruGin
79 / 79 / 44
Регистрация: 14.07.2013
Сообщений: 401
Завершенные тесты: 1
03.12.2016, 13:25 10
но ведь всё равно придется проверять какая скобка

Добавлено через 1 минуту
сейчас по другому сделаю, думаю тебе понравится, но вс'равно со свичом

Добавлено через 9 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
bool braces_ok(string a, int idx, int square, int round, int braces){// square - '['']' round - '('')' braces - '{''}'
    if(idx == a.size()){
        if(square == 0 && round == 0 && braces == 0)
            return true;
        return false;
    }
    switch(a[idx]) {
        case '(':
            braces_ok(a, idx + 1, square, round + 1, braces);
            break;
        case ')':
            if(round == 0)
                return false;
            braces_ok(a, idx + 1, square, round - 1, braces);
            break;
        case '[':
            braces_ok(a, idx + 1, square + 1, round, braces);
            break;
        case ']':
            if(square == 0)
                return false;
            braces_ok(a, idx + 1, square - 1, round, braces);
        case '{':
            braces_ok(a, idx + 1, square, round, braces + 1);
            break;
        case '}':
            if(braces == 0)
                return false;
            braces_ok(a, idx + 1, square, round, braces - 1);
    }
}
0
amaralikyr
70 / 67 / 67
Регистрация: 18.09.2015
Сообщений: 234
Завершенные тесты: 1
03.12.2016, 13:25 11
IchimaruGin, Не совсем понятно, к примеру string a = "[]]"; результат true, так и должно быть по условию задачи?
0
IchimaruGin
79 / 79 / 44
Регистрация: 14.07.2013
Сообщений: 401
Завершенные тесты: 1
03.12.2016, 13:28 12
amaralikyr, сейчас пересмотрю
0
hardyaw
1 / 1 / 2
Регистрация: 10.09.2015
Сообщений: 99
03.12.2016, 13:42  [ТС] 13
IchimaruGin, окей, а можешь сделать полный код?
0
IchimaruGin
79 / 79 / 44
Регистрация: 14.07.2013
Сообщений: 401
Завершенные тесты: 1
03.12.2016, 13:44 14
hardyaw, в каком смысле?
0
hardyaw
1 / 1 / 2
Регистрация: 10.09.2015
Сообщений: 99
03.12.2016, 13:59  [ТС] 15
IchimaruGin, ну с мейном библиотеками и т.д
0
IchimaruGin
79 / 79 / 44
Регистрация: 14.07.2013
Сообщений: 401
Завершенные тесты: 1
03.12.2016, 14:00 16
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <string>
 
using namespace std;
 
bool braces_ok(string a, int idx, int square, int round, int braces){
    cout << square << " " << round << " " << braces << endl;
    if(idx == a.size())
        return true;
    if(square < 0 || round < 0 || braces < 0)
        return false;
    else {
        switch(a[idx]) {
            case '(':
                return braces_ok(a, idx + 1, square, round + 1, braces);
                break;
            case ')':
                return braces_ok(a, idx + 1, square, round - 1, braces);
                break;
            case '[':
                return braces_ok(a, idx + 1, square + 1, round, braces);
                break;
            case ']':
                return braces_ok(a, idx + 1, square - 1, round, braces);
                break;
            case '{':
                return braces_ok(a, idx + 1, square, round, braces + 1);
                break;
            case '}':
                return braces_ok(a, idx + 1, square, round, braces - 1);
                break;
            default:
                return braces_ok(a, idx + 1, square, round, braces);
                break;
        }
    }
}
 
int main() {
    string a = "{}[][]][";
    cout << boolalpha << braces_ok(a,0,0,0,0);
}
0
amaralikyr
70 / 67 / 67
Регистрация: 18.09.2015
Сообщений: 234
Завершенные тесты: 1
03.12.2016, 14:00 17
Вообще не понимаю зачем использовать рекурсию для этого задания, это все равно что прикрутить 5 колесо к машине.
0
hardyaw
1 / 1 / 2
Регистрация: 10.09.2015
Сообщений: 99
03.12.2016, 14:04  [ТС] 18
amaralikyr, я тоже не понимаю, ибо в 100 раз проще решить так, и затрат ПК меньше будет нужно, но преподам нужна рекурсия...
0
IchimaruGin
79 / 79 / 44
Регистрация: 14.07.2013
Сообщений: 401
Завершенные тесты: 1
03.12.2016, 14:05 19
так предыдущая функция тоже рекурсивная но с меньшим уровнем рекурсии
0
hardyaw
1 / 1 / 2
Регистрация: 10.09.2015
Сообщений: 99
03.12.2016, 14:08  [ТС] 20
IchimaruGin, а можно ли как то сделать в этом коде, что бы оно в ответ выдавало по отдельным скобкам результат?
0
03.12.2016, 14:08
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.12.2016, 14:08

Правильность Скобок
Суть задачи такова:Дана строка,состоящая только из скобок и латинских символов. Правильные строки:...

Правильность расстановки скобок
Всё обыскал но никак не могу найти именно то, что мне нужно, а именно: Со всем в принципе...

Проверить правильность расстановки скобок
Помогите написать программу на c++. Дана строка, содержащая латинские буквы и скобки трех видов:...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.