Изменения
Нет описания правки
===Псевдокод===
check(s):
counter = 0
for (i = 1; i <= length(s); i++):
counter = (s[i] == '(')? counter++ : counter--
if (counter < 0)
return false
if (counter == 0)
return true
else
Пусть нам известна строка $s$, представляющая собой правильную скобочную последовательность. Нам необходимо вывести следующую скобочную последовательность, а если ее нет, то {{---}} "No solution". Чтобы получить следующую скобочную последовательность надо найти последнюю открывающуюся скобку, которую можно заменить, заменить ее на закрывающуюся, а оставшиеся в конце скобки (если они есть) заменить на минимально возможную последовательность скобок:
next(s):
counter_close = 0
counter_open = 0
for (i = length(s); i > 0; i--)
if (s[i] == '('):
counter_open++
if (counter_close > counter_open)
break
else
counter_close++
delete(s, length(s) - counter_open - counter_close + 1, counter_close + l)
if (s == ""):
return false
s = s +')'
for (j = 1; j <= counter_open; j++):
s = s + '('
for (j = 1; j < counter_close; j++):
s = s + ')'
return true
Пусть нам известно число $n$. Надо вывести все правильные скобочные последовательности в лексикографическом порядке с $n$ открывающимися скобками:
order (n) s = ""; if (n == 0):
result(s)
else
for (j = 1; j <= n; i++)
s = s + '(';
for (j = 1; j <= n; i++)
s = s + ')'; result(s); t = next(s); while (t <> false) result(s); t = next(s);
return
