leetcode valid parentheses

String Stack

时间复杂度:O(N),空间复杂度:O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class  {
public:
bool isValid(string s) {
stack<char> ps;
for(int i = 0; i < s.size(); ++i) {
if(s[i] == '(' || s[i] == '{' || s[i] == '[') {
ps.push(s[i]);
}else {
if(ps.empty()) return false;
char top_v = ps.top();
if((s[i] == ')' && top_v == '(') || (s[i] == '}' && top_v == '{') || (s[i] == ']' && top_v == '[')) {
ps.pop();
}else {
return false;
}
}
}
if(!ps.empty()) {
return false;
}
return true;
}
};