Форум программистов, компьютерный форум CyberForum.ru

Реализовать рекурсию - C++

Восстановить пароль Регистрация
 
SanAlex
0 / 0 / 0
Регистрация: 05.04.2013
Сообщений: 28
06.10.2013, 16:16     Реализовать рекурсию #1
Доброго времени суток!
Никак не пойму как это сделать, хотябы направьте меня, что бы самому додумать
Пусть в алгебраической записи выражения имеется одна операция - умножения, обозначаемая обычным способом(два множителя записаны друг за другом).Выражение состоит их строки символов и скобок "()", "[]","{}". Написать программу(рекурсивную), которая выполняет проверку на соответствие открывающихся и закрывающихся скобок
пример: (a[b]) -правильно (a[b)] - неправильно

Спасибо!

Добавлено через 19 часов 14 минут
апп
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.10.2013, 16:16     Реализовать рекурсию
Посмотрите здесь:

C++ Задача на рекурсию
Постигая рекурсию. C++
C++ Программа на рекурсию
Задачка на рекурсию... C++
понять рекурсию C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
SanAlex
0 / 0 / 0
Регистрация: 05.04.2013
Сообщений: 28
07.10.2013, 19:49  [ТС]     Реализовать рекурсию #2
Люди, помогите пожалуйста!
Fyret
184 / 170 / 13
Регистрация: 30.07.2013
Сообщений: 359
07.10.2013, 21:11     Реализовать рекурсию #3
Есть такая мысль: читаем выражение посимвольно (номер первого символа пусть будет i, последнего - j), считаем открывающие и закрывающие скобки каждого вида отдельно. Как только количество открывающих стало равно количеству закрывающих (номер соответствующего символа - k), вызываем рекурсивно проверку для подстрок [i+1, k-1] и [k+1, j]. Если где-то дошли до конца текущего диапазона, а количества скобок разные - все, выражение неверно составлено.
SanAlex
0 / 0 / 0
Регистрация: 05.04.2013
Сообщений: 28
08.10.2013, 15:51  [ТС]     Реализовать рекурсию #4
Fyret, Спасибо!
с какими тогда параметрами будет рекурсивная функция?
Fyret
184 / 170 / 13
Регистрация: 30.07.2013
Сообщений: 359
08.10.2013, 16:03     Реализовать рекурсию #5
Цитата Сообщение от SanAlex Посмотреть сообщение
с какими тогда параметрами будет рекурсивная функция?
Ну пусть это будет
C++
1
bool isCorrect( const std::string& expression, size_t start, size_t end );
expression - все выражение, start и end - номера первого и последнего символа рассматриваемого диапазона.
SanAlex
0 / 0 / 0
Регистрация: 05.04.2013
Сообщений: 28
08.10.2013, 16:28  [ТС]     Реализовать рекурсию #6
Fyret, сейчас попробую сделать
Вроде всё ясно, спасибо большое!)
Только почему нельзя передать строку вот так?
C++
1
string expression
просто такой вот формат немного не понятен
что оно означает?
C++
1
const std::string& expression
Fyret
184 / 170 / 13
Регистрация: 30.07.2013
Сообщений: 359
08.10.2013, 16:31     Реализовать рекурсию #7
Можно, но это неэффективно. Зачем создавать копию строки для каждого вызова функции? А так отдаем константную ссылку и все прекрасно. Это из раздела "передача аргументов функции по значению, по ссылке, по указателю".
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.10.2013, 11:18     Реализовать рекурсию
Еще ссылки по теме:

Задача на рекурсию C++
C++ Реализовать код данной функции, но через рекурсию
C++ Реализовать программу на рекурсию про шахматную доску

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

Или воспользуйтесь поиском по форуму:
D3fend0r
17 / 17 / 1
Регистрация: 14.09.2013
Сообщений: 37
09.10.2013, 11:18     Реализовать рекурсию #8
Как вариант можно для каждой открывающийся скобки визызывать функцию снова и выходить из функции когда найдена нужная закр. скобка. Откр. скобки храним в стеке (я использовал вектор) и удаляем если находим пару. Если вектор пуст после завершения работы функции значит выражение удовлетваряет условию.
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <vector>
using namespace std;
 
bool Rec_Func(vector<char> &vec,const string& str,int* index)
{
    bool isValid=true;
    while(*index<str.size() && isValid==true)
    {
        switch(str[*index])
        {
        case '(':
            ++*index;
            vec.push_back(')');
            isValid=Rec_Func(vec,str,index);
            break;
        case'{':
            ++*index;
            vec.push_back('}');
            isValid=Rec_Func(vec,str,index);
            break;
        case '[':
            ++*index;
            vec.push_back(']');
            isValid=Rec_Func(vec,str,index);
            break;
        case ')':
            if (str[*index]==vec.back())//if true we found ')' that is the pair to '('
            {
                vec.pop_back();
            }else return false;
            
            break;
        case '}':
            if (str[*index]==vec.back())//if true we found '}' that is the pair to '{'
            {
                vec.pop_back();
            }else return false;
            break;
        case ']':
            if (str[*index]==vec.back())//if true we found ']' that is the pair to '['
            {
                vec.pop_back();
            }else return false;
            break;
        }
        ++*index;
    }
    return isValid;
}
 
bool Func(const string& str)
{
    vector<char>vec; //for sharing open '(' ,'[' ,'{';
    int* t= new int (0);//current position in str
    Rec_Func(vec,str,t);
    delete(t);
    return vec.empty(); 
}
 
 
 
int main()
{
    string str="(2(34[[234]]56({2})))";
    cout<<Func(str);
    
 
system("pause");
}
Добавлено через 9 часов 1 минуту
Обновленный код. В пред. была проблема если выражение начиналось с закр. скобки и проблема если вектор оказывался пустым.
Кликните здесь для просмотра всего текста



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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <vector>
using namespace std;
 
bool Rec_Func(vector<char> &vec,const string& str,int* index)
{
    bool isValid=true;
    while(*index<str.size() && isValid==true)
    {
        switch(str[*index])
        {
        case '(':
            ++*index;
            vec.push_back(')');
            isValid=Rec_Func(vec,str,index);
            break;
        case'{':
            ++*index;
            vec.push_back('}');
            isValid=Rec_Func(vec,str,index);
            break;
        case '[':
            ++*index;
            vec.push_back(']');
            isValid=Rec_Func(vec,str,index);
            break;
        case ')':
            if (!vec.empty() && str[*index]==vec.back())//if true we found ')' that is the pair to '('
            {
                vec.pop_back();
            }else return false;
            
            break;
        case '}':
            if (!vec.empty() && str[*index]==vec.back())//if true we found '}' that is the pair to '{'
            {
                vec.pop_back();
            }else return false;
            break;
        case ']':
            if (!vec.empty() && str[*index]==vec.back())//if true we found ']' that is the pair to '['
            {
                vec.pop_back();
            }else return false;
            break;
        }
        ++*index;
    }
    return isValid;
}
 
bool Func(const string& str)
{
    vector<char>vec; //for sharing open '(' ,'[' ,'{';
    int* t= new int (0);//current position in str
    bool b=Rec_Func(vec,str,t);
    delete(t);
    return vec.empty() && b; 
}
 
 
 
int main()
{
    string str="(2(34[[234]]56({2})))";
    cout<<Func(str);
    
 
system("pause");
}
Yandex
Объявления
09.10.2013, 11:18     Реализовать рекурсию
Ответ Создать тему
Опции темы

Текущее время: 18:27. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru