678. 有效的括号字符串[leetcode]

给定一个只包含三种字符的字符串：（，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

1. 任何左括号 ( 必须有相应的右括号 )。
2. 任何右括号 ) 必须有相应的左括号 ( 。
3. 左括号 ( 必须在对应的右括号之前 )。
4. * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
5. 一个空字符串也被视为有效字符串。

示例 1:

输入: "()"
输出: True
示例 2:

输入: "(*)"
输出: True
示例 3:

输入: "(*))"
输出: True
注意:

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parenthesis-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

执行用时 :4 ms, 在所有 C 提交中击败了68.72%的用户
内存消耗 :6.9 MB, 在所有 C 提交中击败了5.52%的用户

typedef struct charPoint{
    bool isLeft;
    struct charPoint *before;
} CharPoint;

typedef struct stack{
    CharPoint *top;
    CharPoint *bottom;
} Stack;

void pushPoint(Stack *stack,bool isLeft){
    if (!stack) {
        return;
    }
    CharPoint *point = calloc(sizeof(CharPoint), 1);
    if (!point) {
        return;
    }
    point->isLeft = isLeft;
    point->before = stack->top;
    stack->top = point;
}

bool popPoint(Stack *stack,bool *isLeft){
    if (stack->top == stack->bottom) {
        return false;
    }

    CharPoint *point = stack->top;
    stack->top = point->before;
    if (isLeft) {
        *isLeft = point->isLeft;
    }
    free(point);
    return true;
}

bool deleteLeftBrace(Stack *stack, bool *isLeft){
    CharPoint *leftBrace = NULL;
    CharPoint *index = stack->top;
    CharPoint *afterLeftBrace = NULL;
    if (stack->top == stack->bottom) {
        return false;
    }

    while ( index != stack->bottom) {
        if(index->isLeft){
            leftBrace = index;
            break;
        }
        afterLeftBrace = index;
        index = index->before;
    }
    if (!leftBrace) {
        if (isLeft) {
            *isLeft = false;
        }
        popPoint(stack,NULL);
        return true;
    }
    if(leftBrace == stack->top){
        stack->top = leftBrace->before;
    }else{
        afterLeftBrace->before = leftBrace->before;
    }
    free(leftBrace);
    if (isLeft) {
        *isLeft = true;
    }
    return true;
}



Stack *createStack(){
    CharPoint *bottom = calloc(sizeof(CharPoint), 1);
    if (!bottom) {
        return NULL;
    }
    Stack *stack = calloc(sizeof(Stack), 1);
    if (!stack) {
        return NULL;
    }
    stack->top = stack->bottom = bottom;
    return stack;
}

bool checkValidString(char * s){

    Stack *stack = createStack();

    while (*s != '\0') {
//        printf("%c\t",*s);
        if (*s == '(') {
            pushPoint(stack, true);
        }else if(*s == ')'){
            if(!deleteLeftBrace(stack,NULL)){
                return false;
            }
        }else{
            pushPoint(stack, false);
        }
        s++;
    }

    int countOf8Last = 0;
    while (stack->top != stack->bottom) {
        bool isLeft;
        popPoint(stack, &isLeft);
        if (!isLeft) {
            countOf8Last ++;
        }else{
            if (countOf8Last <=0 ) {
                return false;
            }
            countOf8Last --;
        }
    }
    return true;
}