Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
An 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. Note that an empty string is also considered valid.
Example 1:
Input: “()” Output: true
Example 2:
Input: “()[]{}” Output: true
Example 3:
Input: “(]” Output: false
Example 4:
Input: “([)]” Output: false
Example 5:
Input: “{[]}” Output: true
// use the list stack to achieve //4ms 7.1M struct stack_node{ int data; struct stack_node *next; }; typedef struct stack_node *Node; typedef Node Stack; Stack create_stack(){ Stack s= (Stack)malloc(sizeof(struct stack_node)); if (s == NULL) printf("malloc failed\n"); s->next=NULL; return s; } void push_stack(Stack s, int data){ Stack node= (Stack)malloc(sizeof(struct stack_node)); if (node == NULL) printf("malloc failed\n"); node->data = data; node->next = s->next; s->next = node; } void pop_stack(Stack s){ Stack node= (Stack)malloc(sizeof(struct stack_node)); if (node == NULL) printf("malloc failed\n"); if (stack_is_empty(s)) return false; else { node = s->next; s->next = node->next; free(node); } } int stack_is_empty(Stack s) { return s->next == NULL; } //读取栈定元素一定要判断是否为空，用例：‘]’ int top_stack(Stack s) { if (stack_is_empty(s)) { printf("Stack is empty!\n"); return false; } else { return s->next->data; } } bool isValid(char * s){ Stack stack = create_stack(); char *p = s; while(*p != '\0') { if(*p == '(' || *p == '{' || *p == '[') push_stack(stack, *p); else if (*p == ')') { if (top_stack(stack) != '(') return false; else pop_stack(stack); } else if (*p == '}') { if (top_stack(stack) != '{') return false; else pop_stack(stack); } else if (*p == ']') { if (top_stack(stack) != '[') return false; else pop_stack(stack); } else return false; ++p; } if (stack_is_empty(stack)) return true; else return false; }通过链表也有很大的局限性。当前使用单链表来实现栈。通过在表顶端插入一个元素来实现 PUSH，通过删除表顶端元素来实现 POP。但是功能有些受限制，动态栈只能在栈顶处进行插入和删除操作，不能在栈尾或栈中间进行插入和删除操作。
