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
42
43
44
45
46
47
|
// 20. Valid Parentheses
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
* given a string 's' containing just the characters '(, ), {, }, [, ]',
* determine if the input string is valid. a input string is valid if open
* brackets must be closed by the same type of brackets. open brackets must be
* closed in the correct order. every close bracket has a corresponding open
* bracket of the same type.
*/
bool isValid(char *s) {
int len = strlen(s);
if (len % 2)
return false;
int n = len / 2, idx = 0;
char *stack = malloc(n), c, top;
for (int i = 0; i < len; i++) {
c = s[i];
if (c == '(' || c == '[' || c == '{') {
if (idx == n)
return false;
else
stack[idx++] = c;
} else {
if (!idx)
return false;
top = stack[idx - 1];
if (top == '(' && c == ')' || top == '[' && c == ']' ||
top == '{' && c == '}')
idx--;
else
return false;
}
}
return !idx;
}
int main() {
char s1[] = {"()"}, s2[] = {"()[]{}"}, s3[] = {"(]"};
printf("%d\n", isValid(s1)); // expect: 1
printf("%d\n", isValid(s2)); // expect: 1
printf("%d\n", isValid(s3)); // expect: 0
}
|