Helyes zárójel sorrend

A helyes zárójelsorozat ( PRS ) egy ábécé szerint összeállított karaktersorozat, amely rendezett párokba csoportosított karakterekből áll (a zárójelek típusai, grafikusan "(" és ")", "[" és "]", "/*" és " */", stb.), amely megfelel bizonyos szabályoknak, amelyek biztosítják az azonos típusú nyitott és zárt zárójelek által közrefogott részsorozatok egymás utáni egymásba ágyazását.

A szabályos zárójeles szekvenciák alkotják a Dyck nyelvet , és formálisan a következőképpen definiálhatók :

az üres karakterlánc érvényes zárójelsorozat;
az azonos típusú zárójelbe tett szabályos zárójelsorozat szabályos zárójelsorozat;
az a szabályos zárójelsorozat, amelyhez egy szabályos zárójelsort adunk a bal vagy a jobb oldalon, szintén szabályos zárójelsorozat.

A helyes zárójelsorozatok száma

Az azonos típusú zárójelekből ( nyitó és záró) helyes zárójelsorozatok száma megegyezik a katalán számmal , amely többféleképpen is származtatható: $2n$ $n$ $n$ $C_{n}$

Ismétlődő kapcsolat :

C_{0}=1

és azért

\qquad C_{n}=\sum _{{i=0}}^{{n-1}}C_{i}C_{{n-1-i}}

n\geq 1.

Ez az összefüggés könnyen megállapítható, ha megjegyezzük, hogy bármely nem üres szabályos zárójelsorozat egyedileg reprezentálható a formában , ahol a szabályos zárójelsorozatok vannak. $\omega$ $\omega =(\omega _{{1}})\omega _{{2}}$ $\omega _{{1,2}}$

Kifejezés binomiális együtthatókban :

C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{n!(n+1)!}}={2n \choose n }-{2n\válasszon n-1}.

Egy másik rekurzív reláció:

R(o,n)={\begin{cases}1,&o=0\,\,{\mbox{and))\,\,n=0;\\0,&n=0\,\,{\ mbox{vagy}}\,\,o>n\,\,{\mbox{or}}\,\,o<0;\\R(o+1,n-1)+R(o-1, n-1),&{\mbox{egyébként}}.\\\end{cases}}

Ahol $C_{n}=R(0,2n).$

Könnyen kimutatható, hogy ha egy zárójelsorozatban vannak zárójelek típusai, akkor a lehetséges helyes zárójelsorozatok száma nyitó zárójelekkel megegyezik a szorzatával . Valójában minden nyitókonzolhoz különböző lehetőségek állnak rendelkezésre. A zárókonzol kiválasztását egyedileg a már kiválasztott nyitókonzol-pár határozza meg, és nem veszik figyelembe. $k$ $n$ $C_{n}$ $k^{n}$ $n$ $k$

Helyes zárójelsorozatok generálása

Most mutassuk be a zárójeles sorozatok lexikográfiai sorrendjét. Mindenekelőtt vegye figyelembe, hogy a nyitó kapocs a záró merevítő előtt van; mert a záró zárójellel kezdődő zárójelsor nem megfelelő. Most minden zárójeltípushoz saját lexikográfiai prioritás tartozik. Ennek a prioritásnak a megválasztása nem alapvető, és a további érvelés során semmit sem befolyásol. Ezért feltételezzük, hogy az i - edik típusú zárójelek a lexikográfiai sorrendben az i - edik helyen vannak. Nyilvánvaló, hogy az első sorozat nyitó zárójelekkel a formátumú sorozat lesz . $k$ $n$ $(_{1}(_{1}...(_{1})_{1})_{1}...)_{1}$