e168 - 演唱會記行 - 周邊商品確認
題目描述
題目要求判斷給定的字串是否為有效的包裝結構，如果有效，則輸出移除最外層包裝後的字串；否則輸出 "Product Broken!!"。有效的包裝結構必須滿足以下條件：
- 所有括號（
(),[],{}）必須成對出現。 - 移除最外層包裝後，字串不能為空。
解題思路
這題的核心是驗證括號的配對是否正確。可以使用堆疊 (Stack) 來解決這個問題。
- 遍歷輸入字串。
- 如果遇到開括號 (
(,[,{)，則將其推入堆疊。 - 如果遇到閉括號 (
),],})，則檢查堆疊是否為空。如果堆疊為空，則表示沒有匹配的開括號，字串無效。 - 如果堆疊不為空，則將堆疊頂端的元素彈出。如果彈出的元素與當前閉括號不匹配，則字串無效。
- 遍歷完字串後，如果堆疊為空，則表示所有括號都已正確配對，字串有效。否則，字串無效。
- 如果字串有效，則移除最外層的包裝，並輸出結果。
程式碼中，arr 陣列模擬了堆疊的功能，a, b, c 分別記錄了 (), [], {} 的數量，it 記錄了堆疊的頂端索引。cut 函式用於移除字串首尾的括號。
複雜度分析
- 時間複雜度: O(n)，其中 n 是輸入字串的長度。需要遍歷字串一次來驗證括號的配對。
- 空間複雜度: O(n)，在最壞的情況下，堆疊可能需要儲存所有開括號。
程式碼
#include <iostream>
using namespace std;
int ac;
string cut(string p){
string rt;
if(p.length()<=2){
ac=0;
return "";
}
for(int i=1;i<p.length()-1;++i){
rt+=p[i];
}
return rt;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
string t;
int n;
cin >> n;
while(n--){
cin >> t;
ac=1;
int a,b,c,it,arr[101]={0};
string ans,tmp;
a=b=c=it=0;
for(int i=0;i<t.length()&∾++i){
if(t[i]=='('){
++a;
arr[it++]=1;
}
else if(t[i]=='['){
++b;
arr[it++]=2;
}
else if(t[i]=='{'){
++c;
arr[it++]=3;
}
else if(t[i]==')'){
if(--a<0||--it<0||arr[it]!=1)
ac=0;
}
else if(t[i]==']'){
if(--b<0||--it<0||arr[it]!=2)
ac=0;
}
else if(t[i]=='}'){
if(--c<0||--it<0||arr[it]!=3)
ac=0;
}
tmp+=t[i];
if(a==0&&b==0&c==0){
ans+=cut(tmp);
tmp.clear();
}
}
if(a||b||c||ans.length()==0){
ac=0;
ans+=cut(tmp);
tmp.clear();
}
if(ac==0)
cout << "Product Broken!!\n";
else
cout << ans << "\n";
}
}