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

Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.72
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
11.09.2011, 16:25     Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок #1
Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок.



Технические условия
Входные данные

В первой строке находится единственное число N (1  ≤  N  ≤  14, N – чётное).

Выходные данные

Каждое выражение выводится в отдельной строке.

Пример входных данных
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
45
46
47
48
49
50
51
#include <iostream>
#include <cstring>
using namespace std;
 
int N;
 
void vokrug(char vir[], int type);
void right(char vir[], int type);
int main()
{
 char str[20];
 cin >> N;
 str[0]='\0';
 if (N==2) cout << "()" << endl << "[]" << endl;
 else
  {
   right(str,0);
   right(str,1);
  }
 return 0;
}
 
void vokrug(char vir[], int type)
{
 char str[20];
 int n=strlen(vir),i;
 if (n==N) return;
 for (i=0; i<n; i++) str[i+1]=vir[i];
 if (!type) str[0]='(',str[n+1]=')',str[n+2]='\0';
 else str[0]='[',str[n+1]=']',str[n+2]='\0';
 if (n==N-2) cout << str << endl;
 vokrug(str,0);
 vokrug(str,1);
 right(str,0);
 right(str,1);
}
 
void right(char vir[], int type)
{
 char str[20];
 int n=strlen(vir),i;
 if (n==N) return;
 for (i=0; i<n; i++) str[i]=vir[i];
 if (!type) str[n]='(',str[n+1]=')',str[n+2]='\0';
 else str[n]='[',str[n+1]=']',str[n+2]='\0';
 if (n==N-2) cout << str << endl;
 vokrug(str,0);
 vokrug(str,1);
 right(str,0);
 right(str,1);
}
Вроде всё выдавать должно. Но проходит все лишь 2 теста. Помогите в чём ошибка.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.09.2011, 16:25     Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок
Посмотрите здесь:

Баланс круглых скобок C++
C++ Дана строка символов проверить правильность расстановки круглых и квадратных скобок в выражениях
Что означает const после круглых скобок функции C++
C++ Строки. Проверить правильность задания круглых скобок
C++ Перегрузка круглых скобок как ravalue
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.09.2011, 16:41     Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок #2
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Вроде всё выдавать должно.
Я проверил Ваш код. Например, при N==6 не увидел в ответе:
()([])
не до конца проработанный код.
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
11.09.2011, 16:50  [ТС]     Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок #3
valeriikozlov, а как это можно исправить?

Добавлено через 5 минут
Исправил так:
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
#include <iostream>
#include <cstring>
using namespace std;
 
int N;
 
void vokrug(char vir[], int type);
void right(char vir[], int type);
void left(char vir[], int type);
int main()
{
 char str[20];
 cin >> N;
 str[0]='\0';
 if (N==2) cout << "()" << endl << "[]" << endl;
 else
  {
   right(str,0);
   right(str,1);
  }
 return 0;
}
 
void vokrug(char vir[], int type)
{
 char str[20];
 int n=strlen(vir),i;
 if (n==N) return;
 for (i=0; i<n; i++) str[i+1]=vir[i];
 if (!type) str[0]='(',str[n+1]=')',str[n+2]='\0';
 else str[0]='[',str[n+1]=']',str[n+2]='\0';
 if (n==N-2) cout << str << endl;
 vokrug(str,0);
 vokrug(str,1);
 right(str,0);
 right(str,1);
 left(str,0);
 left(str,1);
}
 
void right(char vir[], int type)
{
 char str[20];
 int n=strlen(vir),i;
 if (n==N) return;
 for (i=0; i<n; i++) str[i]=vir[i];
 if (!type) str[n]='(',str[n+1]=')',str[n+2]='\0';
 else str[n]='[',str[n+1]=']',str[n+2]='\0';
 if (n==N-2) cout << str << endl;
 vokrug(str,0);
 vokrug(str,1);
 right(str,0);
 right(str,1);
}
 
void left(char vir[], int type)
{
 char str[20];
 int n=strlen(vir),i;
 if (n==N) return;
 for (i=0; i<n; i++) str[i+2]=vir[i];
 if (!type) str[0]='(',str[1]=')',str[n+2]='\0';
 else str[0]='[',str[1]=']',str[n+2]='\0';
 if (n==N-2) cout << str << endl;
 vokrug(str,0);
 vokrug(str,1);
 right(str,0);
 right(str,1);
}
Прошло 3 теста, 2 не проходит.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.09.2011, 17:11     Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок #4
Цитата Сообщение от AvengerAlive Посмотреть сообщение
а как это можно исправить?
я бы обошелся одной функцией. Например так:
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
void func(int col_krug, int col_right, int col)
{
    if(col==N)
    {
        // вывод строки str[] на экран
        return;
    }
    if(col+(col_krug+col_right)<N)
    {
        str[col]='(';
        func(col_krug+1, col_right, col+1);
        str[col]='[';
        func(col_krug, col_right+1, col+1);
    }
    if(col_krug>0 && str[col-1]!='[')
    {
        str[col]=')';
        func(col_krug-1, col_right, col+1);
    }
    if(col_right>0 && str[col-1]!='(')
    {
        str[col]=']';
        func(col_krug, col_right-1, col+1);
    }
}
Первый вызов:
func(0, 0, 0);

Добавлено через 15 минут
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
void func(int col_krug, int col_right, int col)
{
    if(col==N)
    {
        // вывод строки str[] на экран
        return;
    }
    if(col+(col_krug+col_right)<N)
    {
        str[col]='(';
        func(col_krug+1, col_right, col+1);
        str[col]='[';
        func(col_krug, col_right+1, col+1);
    }
    if(col_krug>0)
    {
        int fl=0;
        int tmp=col-1;
        while(str[tmp]!='(')
        {
            if(str[tmp]=='[')
                fl++;
            if(str[tmp]==']')
                fl--;
            tmp--;
        }
            if(fl==0)
            {
                str[col]=')';
                func(col_krug-1, col_right, col+1);
            }
    }
    if(col_right>0 && str[col-1]!='(')
    {
        int fl=0;
        int tmp=col-1;
        while(str[tmp]!='[')
        {
            if(str[tmp]=='(')
                fl++;
            if(str[tmp]==')')
                fl--;
            tmp--;
        }
            if(fl==0)
            {
                str[col]=']';
                func(col_krug, col_right-1, col+1);
            }
    }
}
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
11.09.2011, 17:35  [ТС]     Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок #5
valeriikozlov, опять прошло 2 теста(
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.09.2011, 17:50     Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок #6
AvengerAlive, Ссылку на задачу можете дать?
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
11.09.2011, 19:05  [ТС]     Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок #7
valeriikozlov, вот http://www.e-olimp.com/problems/855
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.09.2011, 19:06     Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок #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
71
72
73
74
75
76
77
#include <stdio.h>
void pr(char *mas, int N)
{
    for(int i=0; i<N; i++)
    {
        printf("%c", mas[i]);
  
    }
    printf("\n");
}
 
void rec(char *mas, int j, int N, int temp1, int temp2)
{
    if(j==N)
        pr(mas, N);
    else
    {
    int t1=0, t2=0, i, fl=1;
    for(i=j-1;fl && i>=0; i--)
    {
        if(mas[i]=='(') t1--;
        if(mas[i]=='[') t2--;
        if(mas[i]==')') t1++;
        if(mas[i]==']') t2++;
        if(t1<0 || t2<0)
            fl=0;
    }
    if(fl)
    {
        mas[j]='(';
        rec(mas, j+1, N, temp1+1, temp2);
        mas[j]='[';
        rec(mas, j+1, N, temp1, temp2+1);
    }
    else
    {
        if(t1<0)
        {
            mas[j]=')';
            rec(mas, j+1, N, temp1, temp2);
            if(temp1+temp2<N/2)
            {
                mas[j]='(';
                rec(mas, j+1, N, temp1+1, temp2);
                mas[j]='[';
                rec(mas, j+1, N, temp1, temp2+1);
            }
        }
        if(t2<0)
        {
            mas[j]=']';
            rec(mas, j+1, N, temp1, temp2);
            if(temp1+temp2<N/2)
            {
                mas[j]='(';
                rec(mas, j+1, N, temp1+1, temp2);
                mas[j]='[';
                rec(mas, j+1, N, temp1, temp2+1);
            }
        }
    }
    }
}
 
 
 
int main() {
     int N;
    char *mas;
    scanf("%d", &N);
    mas=new char[N];
    mas[0]='(';
    rec(mas, 1, N, 1, 0);
    mas[0]='[';
    rec(mas, 1, N, 0, 1);
    return 0;
}
accept
4837 / 3236 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
12.09.2011, 04:04     Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок #9
Цитата Сообщение от AvengerAlive
Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок.
используй стек
accept
4837 / 3236 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
12.09.2011, 04:04     Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок #10
Цитата Сообщение от AvengerAlive
Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок.
используй стек
accept
4837 / 3236 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
12.09.2011, 04:06     Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок #11
Цитата Сообщение от AvengerAlive
Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок.
используй стек
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
12.09.2011, 21:10     Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок #12
accept, а чем лучше стек, чем простой массив для этой задачи?
accept
4837 / 3236 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
13.09.2011, 01:25     Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок #13
проверка правильности скобок делается через стек
если в конце стек пуст, то скобки правильные

Цитата Сообщение от valeriikozlov
C++
1
2
3
4
        if(mas[i]=='(') t1--;
        if(mas[i]=='[') t2--;
        if(mas[i]==')') t1++;
        if(mas[i]==']') t2++;
([)]
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
13.09.2011, 07:04     Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок #14
Цитата Сообщение от accept Посмотреть сообщение
проверка правильности скобок делается через стек
согласен, но можно так же и через простой массив.

Цитата Сообщение от accept Посмотреть сообщение
если в конце стек пуст, то скобки правильные
если я правильно понимаю, то Ваше предложение - генерировать все возможные комбинации скобок, а в конце проверять каждую комбинацию на правильность. Мне кажется по времени не уложитесь.
Очередной раз ставя скобку ')' или ']' Вам придется проверять уже имеющуюся комбинацию. Я не вижу здесь премущества стека.
accept
4837 / 3236 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
13.09.2011, 07:23     Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок #15
Цитата Сообщение от valeriikozlov
если я правильно понимаю, то Ваше предложение - генерировать все возможные комбинации скобок, а в конце проверять каждую комбинацию на правильность
нет, скобки считываются в стек и снимаются со стека
это классическая задача
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
13.09.2011, 20:01     Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок #16
Цитата Сообщение от accept Посмотреть сообщение
нет, скобки считываются в стек и снимаются со стека
код (или алгоритм) можете полностью написать здесь?
Mr.X
Эксперт С++
 Аватар для Mr.X
2796 / 1572 / 246
Регистрация: 03.05.2010
Сообщений: 3,649
14.09.2011, 00:11     Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок #17
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
71
72
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <iterator>
#include <set>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string                      T_brackets_expression;
typedef std::set<T_brackets_expression>  T_brackets_expressions;
/////////////////////////////////////////////////////////////////////////////////////////
T_brackets_expression  conc
    (
        const T_brackets_expression  A,
        const T_brackets_expression  B,
        const T_brackets_expression  C = T_brackets_expression()
    )
{
    return A + B + C;
}
/////////////////////////////////////////////////////////////////////////////////////////
T_brackets_expressions  make_brackets_expressions(int  len)
{
    T_brackets_expressions  from;
    T_brackets_expressions  to;
    to.insert( T_brackets_expression() );
    for(int  L = 0; L < len / 2; ++L)
    {
        swap(from, to);
        to.clear();
        for(T_brackets_expressions::const_iterator  it = from.begin();
            it != from.end(); ++it)
        {
            to.insert( conc( "(",  *it, ")" ) );
            to.insert( conc( "[",  *it, "]" ) );
 
            to.insert( conc( "()", *it      ) );
            to.insert( conc( *it,  "()"     ) );
 
            to.insert( conc( "[]", *it      ) );
            to.insert( conc( *it,  "[]"     ) );          
        }
    }
    return  to;
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    int  len = 0;
    do
    {
        std::cout << "Введите четную длину скобочного выражения: ";
        std::cin >> len;        
        if(len <= 0) exit(1);
    }while(len % 2);  
    
    T_brackets_expressions  brackets_expressions = make_brackets_expressions(len);
    std::cout << std::endl
              << "Все правильные скобочные выражения длиной "
              << len               
              << ","
              << std::endl
              <<"состоящие из круглых и квадратных скобок:"
              << std::endl;
 
    std::copy
        (
            brackets_expressions.begin(),
            brackets_expressions.end(),
            std::ostream_iterator<T_brackets_expressions::value_type>(std::cout, "\n")
        );
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.09.2011, 02:00     Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок
Еще ссылки по теме:

Проверка записи на соответствие условию: правильная скобочная запись из круглых и квадратных скобок C++
Проверить правильность расстановки в тексте круглых скобок C++
Написать рекурсивную функцию, проверяющую правильность расстановки круглых скобок в строке C++

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

Или воспользуйтесь поиском по форуму:
accept
4837 / 3236 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
14.09.2011, 02:00     Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок #18
Цитата Сообщение от AvengerAlive
Пример входных данных
4

Пример выходных данных
(())
[[]]
[()]
()[]
[]()
()()
([])
[][]
Цитата Сообщение от valeriikozlov
код (или алгоритм) можете полностью написать здесь?
это я перепутал
думал, там надо вывести корректные скобочные выражения из вводимых
Yandex
Объявления
14.09.2011, 02:00     Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок
Ответ Создать тему
Опции темы

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