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