diff options
Diffstat (limited to 'valid_parentheses.c')
-rw-r--r-- | valid_parentheses.c | 47 |
1 files changed, 47 insertions, 0 deletions
diff --git a/valid_parentheses.c b/valid_parentheses.c new file mode 100644 index 0000000..720fef4 --- /dev/null +++ b/valid_parentheses.c @@ -0,0 +1,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 +} |