b304 - 00673 - Parentheses Balance
題目描述
題目要求判斷一個只包含小括號 () 和中括號 [] 的字串是否為有效的運算式。有效的運算式需要滿足括號配對的規則，例如空字串、兩個有效運算式的連接、以及用括號包圍一個有效運算式。
解題思路
這題可以使用堆疊 (Stack) 的概念來解決。遍歷字串，遇到左括號 ( ( 或 [ ) 時，將其推入堆疊。遇到右括號 ( ) 或 ] ) 時，檢查堆疊是否為空。如果堆疊為空，則表示沒有匹配的左括號，字串無效。如果堆疊不為空，則將堆疊頂端的元素彈出。如果彈出的元素與當前的右括號不匹配，則字串無效。最後，遍歷完字串後，如果堆疊為空，則表示所有括號都已匹配，字串有效；否則，字串無效。
程式碼中，dp[0] 和 dp[1] 分別記錄了 ( 和 [ 的數量，tmp 陣列模擬了堆疊的功能，it 指標指向堆疊的頂端。
複雜度分析
- 時間複雜度: O(n)，其中 n 是字串的長度。需要遍歷字串一次。
- 空間複雜度: O(n)，在最壞情況下，字串中的所有字符都是左括號，需要將它們全部存入堆疊中。
程式碼
#include <iostream>
using namespace std;
int dp[2],t;
string a;
int main(){
cin >> t;
getline(cin,a);
while(t--){
getline(cin,a);
int al=a.length(),tmp[128]={0},it=1;
bool ans=1;
dp[0]=0;
dp[1]=0;
for(int i=0;i<al&&ans;++i){
if(a[i]=='('){
++dp[0];
tmp[it]=1;
++it;
}
else if(a[i]=='['){
++dp[1];
tmp[it]=2;
++it;
}
else if(a[i]==']'){
if(tmp[it-1]!=2)ans=0;
--dp[1];
--it;
tmp[it]=0;
if(dp[1]<0)ans=0;
}
else{
if(tmp[it-1]!=1)ans=0;
--dp[0];
--it;
tmp[it]=0;
if(dp[0]<0)ans=0;
}
}
if(dp[0]||dp[1])ans=0;
if(ans)
cout << "Yes\n";
else
cout << "No\n";
}
}