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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
SanAlex
0 / 0 / 0
Регистрация: 05.04.2013
Сообщений: 28
#1

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

06.10.2013, 16:16. Просмотров 411. Ответов 7
Метки нет (Все метки)

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

Спасибо!

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

Реализовать вывод чисел в диапазоне от 10 до 25 через рекурсию - C++
Парни, нужно реализовать такое задание , но я сам нуб в этом а нужно очень. Помогите . Задание: Реализовать вывод чисел в диапазоне от...

Реализовать программу на рекурсию про шахматную доску - C++
Магараджа - шахматная фигура, сочетающая возможности ферзя и коня. Найти число способов расставить на доске с заданной размерностью NxN...

Реализовать код данной функции, но через рекурсию - C++
Добрый вечер. Прошу помочь реализовать функцию Mult с помощью рекурсии. Там формируется матрица произведений. Вот сделть, чтобы она...

Задача на рекурсию - C++
Нашел одну задачу, она по моему на рекурсию, но не могу реализовать это. Сколько существует чисел от 1 до n, таких, что цифры числа...

Задачка на рекурсию... - C++
в общем нужно сделать прогу чтоб выводила дерево файлов и папок указанной директории.... Сделать это надо с помощью рекурсии... ...

Вставить рекурсию - C++
Есть программа, она записывает число задом на перед, её нужно записать при помощи рекурсии #include "stdafx.h" #include <iostream> ...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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++
Всем доброго времени суток. Прошу подсказать мне условие задачи на рекурсию(нам дали задание самим придумать себе задание и выполнить...

Задача на рекурсию - 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     Реализовать рекурсию
Ответ Создать тему
Опции темы

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