0020-有效的括号

有效的括号

方案一

我们需要用一个栈，我们开始遍历输入字符串，如果当前字符为左半边括号时，则将其压入栈中，如果遇到右半边括号时，若此时栈为空，则直接返回false，如不为空，则取出栈顶元素，若为对应的左半边括号，则继续循环，反之返回false

可以用Map简化代码

C-源代码

typedef char LinkStackData;

//节点
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);
}

参考Grandyang