Минимальные, оптимальные, красивые решения простых задач :)

[Gypsy]

Навеяно соседним топиком "Шедевры". Но здесь пишем только свои задачи и решения

Так вот. Кто-то задает конкретную задачу. Предлагаем и обсуждаем свои решения. Выбираем наилучшее, целуем победителя в лоб, и переходим к следующей задаче.

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

У кого какие предложения? У меня есть одно довольно короткое и быстрое решение, выложу потом после ваших версий.

[Agregat]

проходим по строке и кладем в стэк открывающую скобку, когда встречаем закрывающаю берем элемент со стэка, если его нет или он не соответствует закрывающей - то баланс нарушен.

[Gypsy]

Ну да. А без стека?

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

Хотя конечно задача не супер. Если есть более интересные задачи, милости просим...

[Hans Andersen]

stek eto chereschur,
int cntopenbraces;
++ delaem pri '('
-- pri ')'
isli kogda nit' cnt < 0, to imba, more )
v konze,
esli cnt == 0 ok
otherwise imba, more '('

[Agregat]

Ганс, читаем внимательнее вместе:
реализовать функцию проверки балланса различных скобок (фигурных, круглых, и т.п.) в заданной строке текста
Если скобка одного типа тогда да - как ты сказал - это элементарно. Я дико обрадуюсь если вы найдете решение лучше моего, которое проверит баланс скобок разных типов.

[Hans Andersen]

oh, my bad i am fusking asleep

[Forever Child]

А последовательность учитыается? В смысле, ты считаешь последовательность ошибочной?

abcd(efg{hijk)lmnop}

А эту считаешь верной?

abcd(efg{hijk}lmnop)

Или без разницы?

[knightmare]

По-моему, тут всё упирается в стек LIFO (c)Agregat
Можно и по-другому, но будет далеко не красиво и, в принципе, тот же LIFO + рудименты.
хотя надо подумать...

[knightmare]

Вот еще одна простая задача: случайным образом преремешать символы в строке (доступна только radn()).

[nm]

насчет скобок:
есть быстрое решение, которое предложил агрегат - но оно требует в максимуме столько же память, сколько занимает проверяемая строка (ерсли учитывать, что скобок у нас всего 4 разных типов -- то их можно паковать в 2 бита , что в 4 раза уменьшит используюмую память)

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

[Agregat]

можно красиво спрятать стэк - заменив его на рекурсию.

[AvDav]

красивое compile-time решение перемешивания

template <int iter, typename T> struct Random {
	static void Shuffle(T* ptr) {
			size_t i=iter-1, j=i*rand()/(RAND_MAX+1);
			ptr[i]^=ptr[j]^=ptr[i]^=ptr[j];
			Random<iter-1, T>::Shuffle(ptr);
	}
};
template <typename T> struct Random<1, T>{static void Shuffle(T*) {}};
.
.
char s[]="abcdefg";
Random<7, char>::Shuffle(&s[0]);

[knightmare]

ООП и скорость компиляции/выполнения по-моему имеют мало общего...

[Gypsy]

Originally Posted by Gypsy

Можно ставить ограничения на строку (скажем определить максимальную глубину скобок).

Originally Posted by Agregat

можно красиво спрятать стэк

Короче у меня такое решение. Тоже разновидность идеи стека, но используется всего (N+5) int-ов, где N - количество видов скобок. То есть используемая память не зависит от длины строки.

Если считать количество видов скобок постоянной величиной, то решение линейное. Всего один проход по строке, и для каждого символа N тестов плюс немного арифметики.

Есть ограничения:
- максимальная глубина (вложенность) < 16.
- максимальная глубина отдельно взятого типа скобок <= 8

Создаем массив из N int-ov, изначально все нулевые.
Сканируем строку слева направо.

- При каждой открытой скобке вносим текущий уровень глубины в соответсвующий элемент массива (с помощью побитового сдвига). Увеличиваем уровень глубины.

Скажем встретили '(' на нулевой глубине, в первом элементе пишем 1, потом встретили '{', во втором элементе пишем 2, потом опять '(', в первом элементе уже получается (1 3).

- При каждой закрытой скобке, проверяем какое число было внесено последним в элемент соответствующий текущему типу скобок. Если там текущий уровень глубины, то все в порядке (закрылась та же скобка что открывалась последней), а если нет, значит получили дисбаланс.

Код я постарался сделать как можно короче, просто ради интереса

Допустим даны следующие определения.
Типов скобок может быть сколько угодно (но >1), алгоритм от этого не пострадает. В принципе это и есть основное преимущество данного решения.

char pOC[] = "{([})]";
#define NUM_BRACKETS (sizeof(pOC)>>1)

Функция проверки баланса:

int CheckBalance(char* p)
{
	int i, c, b = 1, m = 0, n[NUM_BRACKETS], s = NUM_BRACKETS;
	while (i=0, (c=*p++) && b)
	    while ((pOC[i]==c) && ((n[i]<<=4)|=++m),
	           (pOC[s+i]==c) && (b=((n[i]&0xF)==m--), n[i]>>=4), ++i-s);

	return b && (m==0);
}

Такие дела. Я думаю можно найти и более интересные решения...

[Gypsy]

Originally Posted by knightmare

Вот еще одна простая задача: случайным образом преремешать символы в строке.

Можно просто пройтись по строке делая случайные swap-ы (как уже предлагалось). Пусть будет не compile-time если не хочешь, эффект тот же

Просто тут дело в том, что зная random seed перед генерацией случайной строки, можно ее собрать обратно (применив те же swap-ы в обратном порядке).

Если ты хочешь чтоб перемешивание было односторонней функцией, тут одним только rand-ом вряд ли обойдешься.