【栈和队列】有效的括号

程序员Carl解决方法

思路：用栈实现

• 遍历字符串，当字符串中字符为左括号时，将其压入栈中
• 若字符串中字符串为右括号，出栈最顶层字符，看其是否与输入字符串匹配

程序员Carl分析：

1. 三种不匹配的情况：
   1. 字符串中左符号多余，所以不匹配
   2. 字符串中括号不多余，但是不是配对的括号
   3. 字符串中右符号多余，所以不匹配
2. 对应的三种解决方案：
   1. 在遍历完后，栈中仍剩余元素。说明有左符号多余
   2. 弹出右括号时发现不匹配
   3. 弹出右括号后发现栈空了。这时说明没有左括号可以和右括号进行配对了

顺序栈的实现

#define MAXSIZE 10000
struct Stack{
    char* arr;
    int head;
}stack;

void InitStack() {
    stack.arr = (char*)malloc(MAXSIZE*sizeof(char));
    stack.head = 0;
}

void StackPush(char s) {
    assert(stack.head<MAXSIZE);
    stack.arr[stack.head++] = s;
}

char StackPop() {
    assert(stack.head);
    return stack.arr[--stack.head];
}

int StackEmpty() {
    if(stack.head == 0)
        return 1;
    return 0;
}

算法的实现

int checkMatch(char s1, char s2) {
    if(s1 == '(') {
        return s2 == ')';
    } else if(s1 == '{') {
        return s2 == '}';
    } else if(s1 == '[') {
        return s2 == ']';
    }
    return 0;
}

int getLength(char* s) {
    int count = 0;
    while(s[++count]) {
        ;
    }
    return count;
}

bool isValid(char * s){
    int length = getLength(s);
    InitStack();
    int i = 0;
    for(i = 0; i < length;i++) {
        if(s[i] == '(' || s[i] == '{' || s[i] == '[') {
            //将元素入栈
            StackPush(s[i]);
        } else {
            //出栈栈顶元素，看是否匹配
            if(StackEmpty()||!checkMatch(StackPop(),s[i]))
                return 0;
        }
    }
		//如果栈空，则代表所有括号都有匹配，返回1
    if(StackEmpty())
        return 1;
    return 0;
}

缺陷：

• 第一次时用了顺序栈，未考虑到如果字符串或大或小时的空间浪费，若用链栈实现空间会更低

改进：用了链栈实现。空间复杂度降低了，但是时间却上升了