پرش به محتویات

رشته‌های پرانتز متوازن

یک رشته پرانتز متوازن رشته‌ای است که فقط از پرانتزها تشکیل شده، به طوری که این رشته، با قرار دادن اعداد و عملیات ریاضی مشخص، یک عبارت ریاضی معتبر را نتیجه می‌دهد. به‌طور رسمی، می‌توان رشته پرانتز متوازن را این‌گونه تعریف کرد:

  • $e$ (رشته خالی) یک رشته پرانتز متوازن است.
  • اگر $s$ یک رشته پرانتز متوازن باشد، آنگاه $(s)$ نیز متوازن است.
  • اگر $s$ و $t$ رشته‌های پرانتز متوازن باشند، آنگاه $st$ نیز متوازن است.

برای مثال، $(())()$ یک رشته پرانتز متوازن است، اما $())($ نیست.

البته می‌توان رشته‌های پرانتز دیگری را نیز با چندین نوع پرانتز به روشی مشابه تعریف کرد.

در این مقاله، به بررسی چند مسئله کلاسیک مرتبط با رشته‌های پرانتز متوازن می‌پردازیم (برای سادگی، آن‌ها را فقط «رشته» می‌نامیم): اعتبارسنجی، تعداد رشته‌ها، یافتن رشته بعدی از نظر ترتیب الفبایی، تولید تمام رشته‌ها با اندازه‌ای مشخص، یافتن اندیس یک رشته، و تولید $k$-امین رشته. همچنین دو نسخه متفاوت از این مسائل را بررسی خواهیم کرد: نسخه ساده‌تر که در آن فقط یک نوع پرانتز مجاز است، و حالت سخت‌تر که در آن چندین نوع پرانتز وجود دارد.

اعتبارسنجی توازن

می‌خواهیم بررسی کنیم که آیا یک رشته داده‌شده متوازن است یا خیر.

ابتدا فرض کنید تنها یک نوع پرانتز وجود دارد. برای این حالت، یک الگوریتم بسیار ساده وجود دارد. فرض کنید $\text{depth}$ تعداد فعلی پرانتزهای باز باشد. در ابتدا $\text{depth} = 0$ است. ما روی تمام کاراکترهای رشته پیمایش می‌کنیم؛ اگر کاراکتر پرانتز فعلی یک پرانتز باز باشد، $\text{depth}$ را افزایش می‌دهیم، در غیر این صورت آن را کاهش می‌دهیم. اگر در هر لحظه متغیر $\text{depth}$ منفی شود، یا در پایان مقدار آن مخالف $0$ باشد، رشته یک رشته متوازن نیست. در غیر این صورت، متوازن است.

اگر چندین نوع پرانتز درگیر باشند، الگوریتم باید تغییر کند. به جای شمارنده‌ای به نام $\text{depth}$، یک پشته (stack) ایجاد می‌کنیم که در آن تمام پرانتزهای بازی را که با آن‌ها مواجه می‌شویم، ذخیره می‌کنیم. اگر کاراکتر پرانتز فعلی یک پرانتز باز باشد، آن را به پشته اضافه می‌کنیم. اگر یک پرانتز بسته باشد، بررسی می‌کنیم که آیا پشته خالی نیست و آیا عنصر بالای پشته از همان نوع پرانتز بسته فعلی است. اگر هر دو شرط برقرار باشند، پرانتز باز را از پشته حذف می‌کنیم. اگر در هر لحظه یکی از این شرایط برآورده نشود، یا در پایان پشته خالی نباشد، رشته متوازن نیست. در غیر این صورت، متوازن است.

تعداد رشته‌های متوازن

فرمول

تعداد رشته‌های پرانتز متوازن با تنها یک نوع پرانتز را می‌توان با استفاده از اعداد کاتالان محاسبه کرد. تعداد رشته‌های پرانتز متوازن به طول $2n$ ($n$ جفت پرانتز) برابر است با:

$$\frac{1}{n+1} \binom{2n}{n}$$

اگر $k$ نوع پرانتز مجاز باشد، آنگاه هر جفت می‌تواند از هر یک از $k$ نوع باشد (مستقل از بقیه)، بنابراین تعداد رشته‌های پرانتز متوازن برابر است با:

$$\frac{1}{n+1} \binom{2n}{n} k^n$$

برنامه‌نویسی پویا

از طرف دیگر، این اعداد را می‌توان با استفاده از برنامه‌نویسی پویا (dynamic programming) محاسبه کرد. فرض کنید $d[n]$ تعداد رشته‌های پرانتز منظم با $n$ جفت پرانتز باشد. توجه داشته باشید که در موقعیت اول همیشه یک پرانتز باز قرار دارد. و جایی بعدتر، پرانتز بسته متناظر آن جفت قرار دارد. واضح است که درون این جفت، یک رشته پرانتز متوازن وجود دارد و به همین ترتیب، پس از این جفت نیز یک رشته پرانتز متوازن وجود دارد. بنابراین برای محاسبه $d[n]$، بررسی می‌کنیم که چند رشته متوازن با $i$ جفت پرانتز درون این جفت پرانتز اول قرار دارد و چند رشته متوازن با $n-1-i$ جفت پس از این جفت قرار دارد. در نتیجه، فرمول به شکل زیر است:

$$d[n] = \sum_{i=0}^{n-1} d[i] \cdot d[n-1-i]$$

مقدار اولیه برای این رابطه بازگشتی $d[0] = 1$ است.

یافتن رشته متوازن بعدی از نظر ترتیب الفبایی

در اینجا فقط حالتی را در نظر می‌گیریم که یک نوع پرانتز معتبر وجود دارد.

با داشتن یک رشته متوازن، باید رشته متوازن بعدی (از نظر ترتیب الفبایی) را پیدا کنیم.

باید واضح باشد که باید راست‌ترین پرانتز باز را پیدا کنیم که بتوانیم آن را با یک پرانتز بسته جایگزین کنیم، بدون اینکه این شرط را نقض کنیم که تا این موقعیت، تعداد پرانتزهای بسته از پرانتزهای باز بیشتر شود. پس از جایگزینی این موقعیت، می‌توانیم بخش باقیمانده رشته را با کوچکترین رشته از نظر الفبایی پر کنیم: یعنی ابتدا با بیشترین تعداد ممکن پرانتز باز، و سپس پر کردن موقعیت‌های باقیمانده با پرانتزهای بسته. به عبارت دیگر، سعی می‌کنیم بلندترین پیشوند ممکن را بدون تغییر باقی بگذاریم و پسوند را با کوچکترین حالت ممکن از نظر الفبایی جایگزین کنیم.

برای یافتن این موقعیت، می‌توانیم از راست به چپ روی کاراکترها پیمایش کنیم و توازن $\text{depth}$ (تعداد پرانتزهای باز و بسته) را حفظ کنیم. وقتی با یک پرانتز باز مواجه می‌شویم، $\text{depth}$ را کاهش می‌دهیم و وقتی با یک پرانتز بسته مواجه می‌شویم، آن را افزایش می‌دهیم. اگر در نقطه‌ای با یک پرانتز باز مواجه شویم و توازن پس از پردازش این نماد مثبت باشد، راست‌ترین موقعیتی را که می‌توانیم تغییر دهیم پیدا کرده‌ایم. نماد را تغییر می‌دهیم، تعداد پرانتزهای باز و بسته‌ای را که باید به سمت راست اضافه کنیم محاسبه می‌کنیم و آنها را به کوچکترین شکل ممکن از نظر الفبایی مرتب می‌کنیم.

اگر موقعیت مناسبی پیدا نکنیم، به این معنی است که این رشته در حال حاضر بزرگترین رشته ممکن است و جوابی وجود ندارد.

bool next_balanced_sequence(string & s) {
    int n = s.size();
    int depth = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '(')
            depth--;
        else
            depth++;

        if (s[i] == '(' && depth > 0) {
            depth--;
            int open = (n - i - 1 - depth) / 2;
            int close = n - i - 1 - open;
            string next = s.substr(0, i) + ')' + string(open, '(') + string(close, ')');
            s.swap(next);
            return true;
        }
    }
    return false;
}

این تابع در زمان $O(n)$ رشته پرانتز متوازن بعدی را محاسبه می‌کند و در صورتی که رشته بعدی وجود نداشته باشد، false برمی‌گرداند.

یافتن تمام رشته‌های متوازن

گاهی اوقات لازم است تمام رشته‌های پرانتز متوازن با طول مشخص $n$ را پیدا و چاپ کنیم.

برای تولید آنها، می‌توانیم با کوچکترین رشته از نظر الفبایی، یعنی $((\dots(())\dots))$ شروع کنیم و سپس با استفاده از الگوریتم شرح داده شده در بخش قبل، به یافتن رشته‌های بعدی از نظر الفبایی ادامه دهیم.

با این حال، اگر طول رشته خیلی بلند نباشد (مثلاً $n$ کوچکتر از ۱۲)، می‌توانیم به راحتی تمام جایگشت‌ها را با تابع next_permutation از کتابخانه استاندارد C++ تولید کرده و توازن هر یک را بررسی کنیم.

همچنین می‌توان آنها را با استفاده از ایده‌هایی که برای شمارش تمام رشته‌ها با برنامه‌نویسی پویا به کار بردیم، تولید کرد. این ایده‌ها را در دو بخش بعدی مورد بحث قرار خواهیم داد.

اندیس رشته

با داشتن یک رشته پرانتز متوازن با $n$ جفت پرانتز، باید اندیس آن را در لیست مرتب‌شده الفبایی تمام رشته‌های متوازن با $n$ جفت پرانتز پیدا کنیم.

بیایید یک آرایه کمکی $d[i][j]$ تعریف کنیم، که در آن $i$ طول رشته پرانتز (نیمه‌متوازن، یعنی هر پرانتز بسته یک پرانتز باز متناظر دارد، اما لزوماً هر پرانتز باز یک پرانتز بسته متناظر ندارد) و $j$ توازن فعلی (تفاوت بین پرانتزهای باز و بسته) است. $d[i][j]$ تعداد چنین رشته‌هایی است که با این پارامترها مطابقت دارند. ما این اعداد را فقط با یک نوع پرانتز محاسبه خواهیم کرد.

برای مقدار شروع $i = 0$ پاسخ واضح است: $d[0][0] = 1$ و $d[0][j] = 0$ برای $j > 0$. حالا فرض کنید $i > 0$ و به آخرین کاراکتر در رشته نگاه می‌کنیم. اگر آخرین کاراکتر یک پرانتز باز $($ بود، حالت قبلی $(i-1, j-1)$ بوده است. اگر یک پرانتز بسته $)$ بود، حالت قبلی $(i-1, j+1)$ بوده است. بنابراین فرمول بازگشتی زیر را به دست می‌آوریم:

$$d[i][j] = d[i-1][j-1] + d[i-1][j+1]$$

بدیهی است که $d[i][j] = 0$ برای $j$ منفی برقرار است. بنابراین می‌توانیم این آرایه را در زمان $O(n^2)$ محاسبه کنیم.

حالا بیایید اندیس را برای یک رشته داده‌شده تولید کنیم.

ابتدا فرض می‌کنیم تنها یک نوع پرانتز وجود دارد. از شمارنده $\text{depth}$ استفاده می‌کنیم که به ما می‌گوید در حال حاضر چقدر تودرتو هستیم و روی کاراکترهای رشته پیمایش می‌کنیم. اگر کاراکتر فعلی $s[i]$ برابر با $($ باشد، $\text{depth}$ را افزایش می‌دهیم. اگر کاراکتر فعلی $s[i]$ برابر با $)$ باشد، باید مقدار $d[2n-i-1][\text{depth}+1]$ را به پاسخ اضافه کنیم، که تمام پایان‌های ممکن که با یک $($ شروع می‌شوند (که رشته‌های کوچکتر از نظر الفبایی هستند) را در نظر می‌گیرد، و سپس $\text{depth}$ را کاهش می‌دهیم.

اکنون فرض کنید $k$ نوع پرانتز مختلف وجود دارد.

بنابراین، وقتی به کاراکتر فعلی $s[i]$ نگاه می‌کنیم، قبل از محاسبه مجدد $\text{depth}$، باید تمام انواع پرانتزی را که از کاراکتر فعلی کوچکتر هستند، مرور کنیم و سعی کنیم این پرانتز را در موقعیت فعلی قرار دهیم (که توازن جدید $\text{ndepth} = \text{depth} \pm 1$ را به دست می‌دهد) و تعداد راه‌های تکمیل رشته (طول $2n-i-1$، توازن $ndepth$) را به پاسخ اضافه کنیم:

$$d[2n - i - 1][\text{ndepth}] \cdot k^{\frac{2n - i - 1 - ndepth}{2}}$$

این فرمول را می‌توان به این صورت استنتاج کرد: ابتدا "فراموش" می‌کنیم که چندین نوع پرانتز وجود دارد و فقط پاسخ $d[2n - i - 1][\text{ndepth}]$ را در نظر می‌گیریم. حالا بررسی می‌کنیم که اگر $k$ نوع پرانتز داشته باشیم، پاسخ چگونه تغییر می‌کند. ما $2n - i - 1$ موقعیت تعریف‌نشده داریم که از این تعداد، $\text{ndepth}$ موقعیت به دلیل پرانتزهای باز از قبل مشخص شده‌اند. اما تمام پرانتزهای دیگر ($(2n - i - 1 - \text{ndepth})/2$ جفت) می‌توانند از هر نوعی باشند، بنابراین عدد را در چنین توانی از $k$ ضرب می‌کنیم.

یافتن k-امین رشته

فرض کنید $n$ تعداد جفت پرانتزها در رشته باشد. باید برای یک $k$ داده‌شده، $k$-امین رشته متوازن را در لیست مرتب‌شده الفبایی تمام رشته‌های متوازن پیدا کنیم.

همانند بخش قبل، آرایه کمکی $d[i][j]$ را محاسبه می‌کنیم که تعداد رشته‌های پرانتز نیمه‌متوازن به طول $i$ با توازن $j$ است.

ابتدا با یک نوع پرانتز شروع می‌کنیم.

روی کاراکترهای رشته‌ای که می‌خواهیم تولید کنیم، پیمایش خواهیم کرد. مانند مسئله قبل، یک شمارنده $\text{depth}$ را برای عمق تودرتویی فعلی ذخیره می‌کنیم. در هر موقعیت، باید تصمیم بگیریم که یک پرانتز باز یا یک پرانتز بسته قرار دهیم. برای قرار دادن یک پرانتز باز، باید شرط $d[2n - i - 1][\text{depth}+1] \ge k$ برقرار باشد. اگر چنین بود، شمارنده $\text{depth}$ را افزایش داده و به کاراکتر بعدی می‌رویم. در غیر این صورت، $k$ را به اندازه $d[2n - i - 1][\text{depth}+1]$ کاهش می‌دهیم، یک پرانتز بسته قرار می‌دهیم و ادامه می‌دهیم.

string kth_balanced(int n, int k) {
    vector<vector<int>> d(2*n+1, vector<int>(n+1, 0));
    d[0][0] = 1;
    for (int i = 1; i <= 2*n; i++) {
        d[i][0] = d[i-1][1];
        for (int j = 1; j < n; j++)
            d[i][j] = d[i-1][j-1] + d[i-1][j+1];
        d[i][n] = d[i-1][n-1];
    }

    string ans;
    int depth = 0;
    for (int i = 0; i < 2*n; i++) {
        if (depth + 1 <= n && d[2*n-i-1][depth+1] >= k) {
            ans += '(';
            depth++;
        } else {
            ans += ')';
            if (depth + 1 <= n)
                k -= d[2*n-i-1][depth+1];
            depth--;
        }
    }
    return ans;
}

حالا فرض کنید $k$ نوع پرانتز وجود دارد. راه‌حل فقط کمی متفاوت خواهد بود، به این صورت که باید مقدار $d[2n-i-1][\text{ndepth}]$ را در $k^{(2n-i-1-\text{ndepth})/2}$ ضرب کنیم و در نظر داشته باشیم که برای کاراکتر بعدی می‌توان انواع مختلفی از پرانتزها را داشت.

در اینجا پیاده‌سازی با استفاده از دو نوع پرانتز، گرد و مربعی، آورده شده است:

string kth_balanced2(int n, int k) {
    vector<vector<int>> d(2*n+1, vector<int>(n+1, 0));
    d[0][0] = 1;
    for (int i = 1; i <= 2*n; i++) {
        d[i][0] = d[i-1][1];
        for (int j = 1; j < n; j++)
            d[i][j] = d[i-1][j-1] + d[i-1][j+1];
        d[i][n] = d[i-1][n-1];
    }

    string ans;
    int shift, depth = 0;

    stack<char> st;
    for (int i = 0; i < 2*n; i++) {

        // پرانتز باز گرد '('
        shift = ((2*n-i-1-depth-1) / 2);
        if (shift >= 0 && depth + 1 <= n) {
            int cnt = d[2*n-i-1][depth+1] << shift;
            if (cnt >= k) {
                ans += '(';
                st.push('(');
                depth++;
                continue;
            }
            k -= cnt;
        }

        // پرانتز بسته گرد ')'
        shift = ((2*n-i-1-depth+1) / 2);
        if (shift >= 0 && depth && st.top() == '(') {
            int cnt = d[2*n-i-1][depth-1] << shift;
            if (cnt >= k) {
                ans += ')';
                st.pop();
                depth--;
                continue;
            }
            k -= cnt;
        }

        // پرانتز باز مربعی '['
        shift = ((2*n-i-1-depth-1) / 2);
        if (shift >= 0 && depth + 1 <= n) {
            int cnt = d[2*n-i-1][depth+1] << shift;
            if (cnt >= k) {
                ans += '[';
                st.push('[');
                depth++;
                continue;
            }
            k -= cnt;
        }

        // پرانتز بسته مربعی ']'
        ans += ']';
        st.pop();
        depth--;
    }
    return ans;
}