有效的括號(hào)
方案一
我們需要用一個(gè)棧蛮放，我們開(kāi)始遍歷輸入字符串缩抡，如果當(dāng)前字符為左半邊括號(hào)時(shí)，則將其壓入棧中包颁，如果遇到右半邊括號(hào)時(shí)瞻想，若此時(shí)棧為空压真，則直接返回false，如不為空蘑险，則取出棧頂元素滴肿，若為對(duì)應(yīng)的左半邊括號(hào)，則繼續(xù)循環(huán)佃迄，反之返回false
可以用Map簡(jiǎn)化代碼
C-源代碼
typedef char LinkStackData;
//節(jié)點(diǎn)
typedef struct link_stack_node {
LinkStackData data;
struct link_stack_node *next;
}LinkStackNode;
typedef struct link_stack {
LinkStackNode *top;//棧頂
int count;//棧大小
}LinkStack;
LinkStack *linkStackCreate() {
LinkStack *stack = NULL;
stack = (LinkStack *)malloc(sizeof(LinkStack));
if (stack == NULL) {
return NULL;
}
stack->top = NULL;
stack->count = 0;
return stack;
}
bool linkStackIsEmpty(LinkStack *stack) {
return stack->count == 0;
}
int linkStackPush(LinkStack *stack, LinkStackData data) {
LinkStackNode *p = NULL;
p = (LinkStackNode *)malloc(sizeof(LinkStackNode));
if (p == NULL) {
return -1;
}
p->data = data;
p->next = stack->top;
stack->top = p;
stack->count++;
return 0;
}
int linkStackTop(LinkStack *stack, LinkStackData *data) {
if (linkStackIsEmpty(stack)) {
return -1;
}
LinkStackNode *p = stack->top;
*data = p->data;
return 0;
}
int linkStackPop(LinkStack *stack, LinkStackData *data) {
if (linkStackIsEmpty(stack)) {
return -1;
}
LinkStackNode *p = stack->top;
*data = p->data;
stack->top = p->next;
stack->count--;
free(p);
return 0;
}
bool isValid(char* s) {
LinkStack *stack = linkStackCreate();
while(*s != '\0') {
if (*s == '(' || *s == '[' || *s == '{') {
linkStackPush(stack, *s);
}
else {
if (linkStackIsEmpty(stack)) {
return false;
}
char c;
linkStackTop(stack, &c);
if (*s == ')' && c!= '(') {
return false;
}
if (*s == ']' && c!= '[') {
return false;
}
if (*s == '}' && c!= '{') {
return false;
}
linkStackPop(stack, &c);
}
s++;
}
return linkStackIsEmpty(stack);
}
