括号匹配

2020-04-16  本文已影响0人  IT播客

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

#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("匹配错误");
    }

上一篇 下一篇

猜你喜欢

热点阅读