美文网首页
括号匹配

括号匹配

作者: IT播客 | 来源:发表于2020-04-16 16:02 被阅读0次

    题目:
    假设表达式中允许包含两种括号:圆括号与方括号,其嵌套顺序随意,即() 或者[([][])] 都是正确的。而这[(] 或者 (()] 或者 ([()) 都是不正确的格式。检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例如,考虑一下括号的判断:[([][])]

    #define StackInitSize 100
    #define StackIncrement 10
    
    // 定义栈
    typedef struct {
        char *base;
        char *top;
        int stackSize;
    }SqStack;
    
    // 初始化栈
    int Init(SqStack *stack){
        if (!stack->base) {
            stack->base = (char *)malloc(StackInitSize*sizeof(char));
            stack->top = stack->base;
            stack->stackSize = StackInitSize;
            printf("初始化\n");
            return 0;
        } else {
            return -1;
        }
    }
    
    // 获取栈顶数据
    char GetTopData(SqStack stack){
        if (stack.base == stack.top) {
            return 'p';
        }
        return *(stack.top - 1);
    }
    
    // 插入数据
    int Push(SqStack *stack,char element){
        if (stack->top - stack->base == stack->stackSize) {
            stack->base = (char *)realloc(stack->base, StackIncrement * sizeof(char));
            stack->top = stack->base + stack->stackSize;
            stack->stackSize += StackIncrement;
        }
        *stack->top = element;
        stack->top += 1;
        return 0;
    }
    
    // 删除栈顶元素
    char Pop(SqStack *stack){
        if (stack->top == stack->base) {
            return 'p';
        }
        return *--stack->top;
    }
    
    // 释放栈空间
    int Destory(SqStack *stack){
        free(stack->base);
        stack->stackSize = 0;
        return 0;
    }
    
    // 处理数据
    int ExecuteData(SqStack stack,char *data){
        Push(&stack, data[0]);
        for (int i = 1; i < strlen(data); i++) {
            char top = GetTopData(stack);
            switch (top) {
                case '(':
                    if (data[i] == ')') {
                        Pop(&stack);
                    } else {
                        Push(&stack, data[i]);
                    }
                    break;
                case '[':
                    if (data[i] == ']') {
                        Pop(&stack);
                    } else {
                        Push(&stack, data[i]);
                    }
                    break;
                case 'p':
                    if (data[i] == '(' || data[i] == '[') {
                        Push(&stack, data[i]);
                    }
                    break;
                    
                default:
                    return -1;
                    break;
            }
        }
        
        if (stack.top == stack.base) {
            Destory(&stack);
            return 0;
        } else {
            Destory(&stack);
            return -1;
        }
    }
    
    // 测试
        SqStack stack;
        Init(&stack);
        char data[180];
        printf("请输入待匹配的字符串\n");
        scanf("%s", data);
        int result = ExecuteData(stack, data);
        if (result == 0) {
            printf("匹配正确");
        } else {
            printf("匹配错误");
        }
    
    

    相关文章

      网友评论

          本文标题:括号匹配

          本文链接:https://www.haomeiwen.com/subject/yznrvhtx.html