b838 - 104北二2.括號問題
題目描述
題目要求判斷輸入字串中的括號是否成對且符合先左後右的順序。如果括號正確配對，則輸出括號的數量；否則輸出 0。輸入字串只包含括號，沒有其他字符。
解題思路
程式碼直接遍歷字串，統計左括號和右括號的數量。如果左右括號數量不相等，則判斷為錯誤，輸出 0。如果數量相等，則使用貪婪演算法嘗試配對括號。程式碼使用一個迴圈，尋找未配對的左括號，然後尋找對應的右括號。如果找到配對的括號，則將它們標記為已配對（替換為 '0'），並增加配對的括號數量。如果在尋找右括號的過程中遇到字串結尾，則判斷為錯誤，輸出 0。
複雜度分析
- 時間複雜度: O(n^2)
- 空間複雜度: O(1)
程式碼
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main(){
string a;
getline(cin,a);
while(getline(cin,a)){
int l=0,r=0,k=0,ans;
bool c=1;
for(int i=0;i<a.length();i++){
if(a[i]=='('){
l++;
}
else if(a[i]==')'){
r++;
}
}
for(int i=0;i<a.length();i++){
while(a[i]=='('){
k=i;
a[i]='0';
while(a[i]!=')'){
i++;
if(i>a.length()){
c=0;
break;
}
}
a[i]='0';
i=k;
ans++;
}
}
if(l!=r||c==0){
ans=0;
}
cout << ans << endl;
ans=0;
}
}