計算使所有平衡括號子序列為空所需的配對移除次數

---

C 編譯器將字串視為字元陣列，因此可以根據字元的位置輕鬆地移除字串中的字元。需要檢查字串的第一個和最後一個位置是否存在括號，並將其移除。可以將字串複製到另一個變數中並顯示。

C 中有許多預定義函式可以有效地用於操作字串。藉助這些函式，可以輕鬆地在 C 中移除字串開頭或結尾的字元。

移除字串開頭和結尾的括號

括號是輸入字串的一部分，是一個單字元，可以透過遵循以下邏輯和演算法將其從字串中移除。

字元是我們在鍵盤上看到的任何字母數字鍵，它儲存在 C 中的字元變數中。

() 在 c 中稱為括號。我們需要在使用者輸入的字串中識別此字元，並需要將其從字串中移除。

陣列是一個變數，它具有許多由單個名稱和連續編號定址的記憶體位置，而字串是字元陣列。

在許多情況下，我們需要從字串中移除括號，例如在解決正則表示式時。

語法

函式 countRemoval 以字串 str 作為輸入，並返回一個整數值，該值表示使字串中所有平衡括號子序列為空所需的配對移除次數。該函式使用變數 count 來跟蹤所需的移除次數，最初設定為 0。它還使用變數 balance 來跟蹤字串中左括號和右括號之間的平衡。然後，該函式遍歷字串的長度並檢查每個索引處的字元。如果字元是左括號，則 balance 加 1，如果字元是右括號，則 balance 減 1。如果 balance 變成負數，則表示存在多餘的右括號，移除次數加 1，並將 balance 重置為 0。迴圈結束後，count 會更新為包含剩餘 balance 除以 2 的結果，作為使字串中所有平衡括號子序列為空所需的移除次數。

int countRemoval(string str) {
   int count = 0;
   int balance = 0;
   for (int i = 0; i < str.length(); i++) {
      if (str[i] == '(') {
         balance++;
      } else {
         balance--;
      }
      if (balance < 0) {
         count++;
         balance = 0;
      }
   }
   count += balance / 2;
   return count;
} 

演算法

• 步驟 1 − 宣告 str1、str2，初始化為空。

• 步驟 2 − 宣告整數變數 len、n、i

• 步驟 3 − 從控制檯接收 str1

• 步驟 4 − 檢查第一個字元是否為 (

• 步驟 5 − 如果是，則 n = 1

• 步驟 6 − 當 n < 輸入字串長度 len 時，將 str1 中的每個字元複製到 str2 中

• 步驟 7 − 檢查 str2 的最後一個字元是否為 )。

• 步驟 8 − 如果是，則將其替換為 \0。

• 步驟 9 − 列印 str2，其中包含輸入字串減去 ()。

方法

方法 1 − 暴力遞迴：在第一種方法中，我們使用暴力遞迴來查詢所有可能的子序列，並檢查它們是否平衡。如果子序列是平衡的，我們移除括號對並計算移除的括號對的數量。我們計算使字串為空所需的最小配對移除次數。

方法 2 − 動態規劃：第二種方法使用動態規劃來最佳化解決方案。我們可以使用一個二維 DP 表來儲存從索引 'i' 到 'j' 的子字串所需的最小移除次數。我們遍歷字串並根據給定條件填充 DP 表。

方法 1 暴力遞迴

程式碼

在此程式碼中，我們檢查所有可能的子序列組合，這會導致指數時間複雜度。對於較大的輸入，此方法可能效率不高。

#include <iostream>
#include <string>
using namespace std;

int countRemovalsRecursion(const string &s, int index, int open) {
   if (index == s.size()) {
      return open;
   }

   if (s[index] == '(') {
      return countRemovalsRecursion(s, index + 1, open + 1);
   } else if (open > 0) {
      return countRemovalsRecursion(s, index + 1, open - 1);
   } else {
      return 1 + countRemovalsRecursion(s, index + 1, open);
   }
}

int main() {
   string s = "(()())(";
   cout << "Input string: " << s << endl;
   cout << "Minimum removals (Brute Force Recursion): " << countRemovalsRecursion(s, 0, 0) << endl;
   return 0;
}

輸出

Input string: (()())(
Minimum removals (Brute Force Recursion): 1

方法 2

示例

此動態規劃解決方案計算使所有平衡括號子序列為空所需的最小移除次數。它遍歷字串，使用一維 DP 表更新左括號的數量，並將最終的 DP 值作為最小移除次數返回。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int countRemovalsDP(const string &s) {
   int n = s.size();
   vector<int> dp(n + 1, 0);

   for (int i = 0; i < n; ++i) {
      if (s[i] == '(') {
         dp[i + 1] = dp[i] + 1;
      } else {
         dp[i + 1] = max(dp[i] - 1, 0);
      }
   }
   return dp[n];
}

int main() {
   string s = "(()())()";
   cout << "Input string: " << s << endl;
   cout << "Minimum removals (Dynamic Programming): " << countRemovalsDP(s) << endl;
   return 0;
}

輸出

Input string: (()())()
Minimum removals (Dynamic Programming): 0

結論

此程式利用了 C 的基本概念，例如字元和字串資料型別之間的區別、字串分隔符、如何初始化字串和陣列、陣列的第一個字元是索引為 0 的位置以及最後一個字元必須為 null 的計算，以獲得正確的輸出。

程式透過實現 C 程式設計的基本簡單概念實現了括號的移除。