0020-有效的括号

2019-01-17  本文已影响0人  liyoucheng2014

有效的括号

方案一


我们需要用一个栈,我们开始遍历输入字符串,如果当前字符为左半边括号时,则将其压入栈中,如果遇到右半边括号时,若此时栈为空,则直接返回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

上一篇 下一篇

猜你喜欢

热点阅读