UVa673
題敘
http://domen111.github.io/UVa-Easy-Viewer/?673
給一個只包含 ( ) [ ] 的字串
定義合法的字串需要符合以下任一條件
- 字串為空字串
- 如果 $A$ 和 $B$ 都為正確的運算式，則 $A B$ 也為正確的運算式，
- 如果 $A$ 為正確的運算式，則 $(A)$ 及 $[A]$ 都為正確的運算式。
求該字串是否為合法字串
想法
如果括號要能匹配的話，必定會兩者相鄰，例如 () 或是 []
那麼，我們只需要一找到匹配的括號就消除，最後如果還有剩餘就是不合法字串，否則為合法字串
利用stack的特性可以簡單地完成
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
int t;
string s;
stack<char>st;
int main(){
cin>>t;
getchar();
while(t--){
getline(cin,s);
while(!st.empty())
st.pop();
for(int i=0 ; i<s.size() ; i++){
if(s[i] == '(' || s[i] == '[')
st.push(s[i]);
else{
if(st.empty()){
st.push(s[i]);
}
else if(st.top()=='(' && s[i]==')'){
st.pop();
}
else if(st.top()=='[' && s[i]==']'){
st.pop();
}
else{
st.push(s[i]);
}
}
}
if(st.empty())
cout<<"Yes\n";
else
cout<<"No\n";
}
return 0;
}
|
複雜度
掃過一次字串即可，每次複雜度為 $O(len(s))$
總複雜度 $O(tlen(s))$