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

Дана случайная последовательность открывающих и закрывающих скобок. Требуется определить, сколько открывающих скобок нужно дописать перед последовательностью, и сколько закрывающих скобок - после, чтобы получилось правильное скобочное выражение. Результат работы программы может выглядеть так:

Код (Text):

1. }}{}{{{
2. 2 3

 

Portman
задачки про конечные автоматы ??? это в бегинерс в топик для студентов

 

Зачем математику сюда, задача элементарная, если я ее правильно понял.

 

Это нужно граф(дерево) обойти. Выполняется множество проходов и на каждом сокращаются "()" элементы, это если без таблиц, например:
((()())())((()())(()()))())())()))
(())(()())))))
()()))))
)))) << Фейл!

 

Clerk
Я прошу прощения, но Вы зациклились на графах. Это задача уровня первых трёх пар информатики: один цикл прохода по строке/массиву с условием.
+1 к Rockphorr.

 

l_inc
И как вы за один цикл определите валидность расположения всех скобок, по мойму это не возможно, если конечно не запоминать их гдето в буфере ?
Можно либо выполнить множество проходов про массиву(уже боюсь сказать графу..) либо удалять скобки от так скажем затравки с обеих сторон.

 

Код (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 - с лева

 

графы, стёки, "не возможно", гы!

Код (Text):

1. do c+=(*x=='{')-(*x=='}'); while(*++x);
2. printf("%d unmatched brackets left",c);

нет ты!

 

не че не забыл ? а я то думал ответ должен быть в 2ух переменных

 

Ну разложите это к примеру ()))))((((((())).

 

мм, комер как обычно нифига не прочитал, но уже ответил - моя киса на эту тему вечно стебётся)
но ничего страшного, остаётся всего лишь проверку на отрицательное c воткнуть в цикл.

 

Хм точна. Когдато я трахался с интерпретатором васика и там было великогеморно выполнить такой анализ выражений. Тут просто выражение не смысловое и любая закрывающаяся кавычка завершает выражение. Наверно я схожу с ума %.

 

проверка, при том, даже с нуля начинается:

Код (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]);

 

FLASH300
работает

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

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

 

а вот и вариант с деревьями (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.                 );

 

Я тут заметил, что последняя программа выполняется не очень быстро. Для случайной последовательности скобок длиной 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 мсек.

 

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

 

что за глупый вопрос, конечно можно)
a0 b0 a1 b1 ... an bn
первое число - a0 + (a1 - b0) + ... + (an - b(n-1))
второе аналогично

 

n0name
Это не совсем верно. Нужно различать, является

положительным или отрицательным. В случае отрицательного прибавлять абсолютное значение к bn для второго числа, а не к a0 для первого.
Второе аналогично.