aboutsummaryrefslogtreecommitdiff
path: root/valid_parentheses.c
diff options
context:
space:
mode:
Diffstat (limited to 'valid_parentheses.c')
-rw-r--r--valid_parentheses.c47
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
+}