Задачка о скобках

Тема в разделе "WASM.BEGINNERS", создана пользователем Portman, 8 дек 2010.

  1. Portman

    Portman New Member

    Публикаций:
    0
    Регистрация:
    18 окт 2008
    Сообщения:
    49
    Дана случайная последовательность открывающих и закрывающих скобок. Требуется определить, сколько открывающих скобок нужно дописать перед последовательностью, и сколько закрывающих скобок - после, чтобы получилось правильное скобочное выражение. Результат работы программы может выглядеть так:
    Код (Text):
    1. }}{}{{{
    2. 2 3
     
  2. Rockphorr

    Rockphorr Well-Known Member

    Публикаций:
    0
    Регистрация:
    9 июн 2004
    Сообщения:
    2.615
    Адрес:
    Russia
    Portman
    задачки про конечные автоматы ??? это в бегинерс в топик для студентов
     
  3. sysexit

    sysexit New Member

    Публикаций:
    0
    Регистрация:
    27 авг 2010
    Сообщения:
    176
    Зачем математику сюда, задача элементарная, если я ее правильно понял.
     
  4. Clerk

    Clerk Забанен

    Публикаций:
    0
    Регистрация:
    4 янв 2008
    Сообщения:
    6.689
    Адрес:
    РБ, Могилёв
    Это нужно граф(дерево) обойти. Выполняется множество проходов и на каждом сокращаются "()" элементы, это если без таблиц, например:
    ((()())())((()())(()()))())())()))
    (())(()())))))
    ()()))))
    )))) << Фейл!
     
  5. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    Clerk
    Я прошу прощения, но Вы зациклились на графах. Это задача уровня первых трёх пар информатики: один цикл прохода по строке/массиву с условием.
    +1 к Rockphorr.
     
  6. TermoSINteZ

    TermoSINteZ Синоби даоса Команда форума

    Публикаций:
    2
    Регистрация:
    11 июн 2004
    Сообщения:
    3.546
    Адрес:
    Russia
    l_inc
    и мало того. задача решается обычным принципом стека. ... Эх... Строить танк, чтобы вспахать огород, это сильно.
     
  7. Clerk

    Clerk Забанен

    Публикаций:
    0
    Регистрация:
    4 янв 2008
    Сообщения:
    6.689
    Адрес:
    РБ, Могилёв
    l_inc
    И как вы за один цикл определите валидность расположения всех скобок, по мойму это не возможно, если конечно не запоминать их гдето в буфере ?
    Можно либо выполнить множество проходов про массиву(уже боюсь сказать графу..) либо удалять скобки от так скажем затравки с обеих сторон.
     
  8. FLASH300

    FLASH300 New Member

    Публикаций:
    0
    Регистрация:
    30 окт 2008
    Сообщения:
    72
    Код (Text):
    1. esi - указатель на массив скобок
    2.         xor ecx,ecx
    3.         xor edx,edx
    4.         jmp start
    5. M2:
    6.         inc edx
    7. start:
    8.         lodsb
    9.         cmp al,0
    10.         je exit
    11.         cmp al,'}'
    12.         je M1
    13.         cmp al,'{'
    14.         jne start
    15.         inc ecx
    16.         jmp start
    17. M1:
    18.         jecxz M2
    19.         dec ecx
    20.         jmp start
    21. exit:
    22.  ecx - с права
    23.  edx - с лева
     
  9. Com[e]r

    Com[e]r Com[e]r

    Публикаций:
    0
    Регистрация:
    20 апр 2007
    Сообщения:
    2.624
    Адрес:
    ого..
    графы, стёки, "не возможно", гы!
    Код (Text):
    1. do c+=(*x=='{')-(*x=='}'); while(*++x);
    2. printf("%d unmatched brackets left",c);
    нет ты!
     
  10. FLASH300

    FLASH300 New Member

    Публикаций:
    0
    Регистрация:
    30 окт 2008
    Сообщения:
    72
    не че не забыл ? а я то думал ответ должен быть в 2ух переменных
     
  11. Clerk

    Clerk Забанен

    Публикаций:
    0
    Регистрация:
    4 янв 2008
    Сообщения:
    6.689
    Адрес:
    РБ, Могилёв
    Ну разложите это к примеру ()))))((((((())).
     
  12. Com[e]r

    Com[e]r Com[e]r

    Публикаций:
    0
    Регистрация:
    20 апр 2007
    Сообщения:
    2.624
    Адрес:
    ого..
    мм, комер как обычно нифига не прочитал, но уже ответил - моя киса на эту тему вечно стебётся)
    но ничего страшного, остаётся всего лишь проверку на отрицательное c воткнуть в цикл.
     
  13. Clerk

    Clerk Забанен

    Публикаций:
    0
    Регистрация:
    4 янв 2008
    Сообщения:
    6.689
    Адрес:
    РБ, Могилёв
    Хм точна. Когдато я трахался с интерпретатором васика и там было великогеморно выполнить такой анализ выражений. Тут просто выражение не смысловое и любая закрывающаяся кавычка завершает выражение. Наверно я схожу с ума %.
     
  14. Com[e]r

    Com[e]r Com[e]r

    Публикаций:
    0
    Регистрация:
    20 апр 2007
    Сообщения:
    2.624
    Адрес:
    ого..
    проверка, при том, даже с нуля начинается:
    Код (Text):
    1.   char*x=")((()())())((()())(()()))())())()))";
    2.   int c[2]={0};
    3.   do{
    4.     if(*x=='(') c[0]++;
    5.     if(*x==')') c[(!c[0])]--;
    6.   }while(*++x);
    7.   printf("pew-pew!1 %d:%d",+c[0],-c[1]);
     
  15. Portman

    Portman New Member

    Публикаций:
    0
    Регистрация:
    18 окт 2008
    Сообщения:
    49
    FLASH300
    работает

    Com[e]r
    работает, особенно понравилось c[(!c[0])]--;

    Clerk
    задача решается одним проходом по строке, но вариант с деревьями интересный
     
  16. Portman

    Portman New Member

    Публикаций:
    0
    Регистрация:
    18 окт 2008
    Сообщения:
    49
    а вот и вариант с деревьями (C#):
    Код (Text):
    1.             string s = Console.ReadLine();
    2.             string s2;
    3.             do
    4.             {
    5.                 s2 = s;
    6.                 s = s.Replace("{}", "");
    7.             }
    8.             while (s.Length != s2.Length);
    9.             Console.WriteLine("{0} {1}",
    10.                 s.Count<char>(c => c == '}'),
    11.                 s.Count<char>(c => c == '{')
    12.                 );
     
  17. Portman

    Portman New Member

    Публикаций:
    0
    Регистрация:
    18 окт 2008
    Сообщения:
    49
    Я тут заметил, что последняя программа выполняется не очень быстро. Для случайной последовательности скобок длиной 10 млн время выполнения составляет около 1 сек. Поэтому я написал параллельную версию:
    Код (Text):
    1.             string s = random_brackets(10000000);
    2.  
    3.             int N = Environment.ProcessorCount;
    4.             string[] Q = new string[N];
    5.  
    6.             int L = s.Length / N;
    7.             int Rem = s.Length % N;
    8.             for (int i = 0; i < N; i++)
    9.                 Q[i] = s.Substring(i * L, (i == N - 1) ? L+Rem : L);
    10.  
    11.             Action<int> A = new Action<int>((i) =>
    12.                 {
    13.                     string ss;
    14.                     do
    15.                     {
    16.                         ss = Q[i];
    17.                         Q[i] = Q[i].Replace("{}", "");
    18.                     }
    19.                     while (ss.Length != Q[i].Length);
    20.                 }
    21.             );
    22.  
    23.             Parallel.For(0, N, A);
    24.  
    25.             Q[0] = Q.Aggregate((string a, string b) => a + b);
    26.             A(0);
    27.  
    28.             Console.WriteLine("{0} {1}",
    29.                 Q[0].Count<char>(c => c == '}'),
    30.                 Q[0].Count<char>(c => c == '{')
    31.                 );
    У меня на машине с двухъядерным процессором время выполнения 500-550 мсек.
     
  18. Portman

    Portman New Member

    Публикаций:
    0
    Регистрация:
    18 окт 2008
    Сообщения:
    49
    А вот интересный вопрос: можно ли распараллелить однопроходной алгоритм? То есть мы разбиваем исходную строку на N подстрок, для каждой подстроки вычисляем пару (L1,R1) и... что дальше? Можно ли из полученных пар рассчитать суммарную пару? Например:
    }}{{ + }{{{
    получаем
    2 2
    1 3
    итоговая пара должна быть
    2 4
     
  19. n0name

    n0name New Member

    Публикаций:
    0
    Регистрация:
    5 июн 2004
    Сообщения:
    4.336
    Адрес:
    Russia
    что за глупый вопрос, конечно можно)
    a0 b0 a1 b1 ... an bn
    первое число - a0 + (a1 - b0) + ... + (an - b(n-1))
    второе аналогично
     
  20. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    n0name
    Это не совсем верно. Нужно различать, является
    [​IMG]
    положительным или отрицательным. В случае отрицательного прибавлять абсолютное значение к bn для второго числа, а не к a0 для первого.
    Второе аналогично. :)