1648: 栈-括号匹配检测
题目描述
假设某个字符串表达式允许包含三种括号：( )、[ ]、{ }（存在其他字符），其嵌套的顺序随意，判断该字符串表达式是否合法。嵌套格式: [([][])]是正确的, 嵌套格式: [(](]]是不正确的。
#include <stdio.h>
#include <stdlib.h>
#define INIT_SIZE 80
#define OK 1
#define ERROR -1
#define TRUE 1
#define FALSE 0
typedef char SElemType;
typedef int Status;
typedef struct {
SElemType *base; // 栈底指针
SElemType *top; //栈顶指针
int stackSize; // 栈的初始分配容量
} SqStack;
Status initStack(SqStack &s);
Status stackEmpty(SqStack s);
Status stackFull(SqStack s);
Status push(SqStack &s,SElemType e);
Status pop(SqStack &s, SElemType &e);
int bracketMatch(SElemType *str, SqStack &stk);
int main(void) {
int result;
SElemType str[81];
SqStack stk;
initStack(stk);
scanf("%s",str);
result = bracketMatch(str,stk);
if(result) printf("Yes");
else printf("No");
return 0;
}
Status initStack(SqStack &s) {
s.base= (SElemType*) malloc(INIT_SIZE*sizeof(SElemType));
if (s.base == NULL) return ERROR;
s.top = s.base;
s.stackSize = INIT_SIZE;
return OK;
}
Status stackFull(SqStack s){
if(s.top-s.base == s.stackSize) return TRUE;
return FALSE;
}
/*提交以下代码*/
Status stackEmpty(SqStack s) {
}
Status push(SqStack &s,SElemType e) {
if (stackFull(s)) return ERROR;
____________
return OK;
}
Status pop(SqStack &s, SElemType &e) {
if(stackEmpty(s)) return ERROR;
____________
return OK;
}
int bracketMatch(SElemType *str, SqStack &stk) {
}
输入格式
输出格式
输入样例 复制
[a(b[c]d[e]f)g]h输出样例 复制
Yes提示
int bracketMatch(SElemType *str, SqStack &stk) {
for(int i=0; str[i]!='\0'; i++) {
if(str[i]=='(' || str[i]=='[' || str[i]=='{') {
// 入栈
} else if(str[i]==')' || str[i]==']' || str[i]=='}') {
// 如果栈空（有右括号无左括号）则返回0，否则{出栈；如果左右括号不匹配则返回0}
}
}
if( ) return 1;
else return 0; // 如果栈空返回1，否则（有左括号无右括号）返回0
}
匹配的结果有匹配（循环结束时栈空）和不匹配两种情况，其中不匹配又分为三种情况：
(1) 有右括号无左括号（出栈时栈空）
(2) 左右括号不匹配（栈顶元素与待匹配的右括号不匹配）
(3) 有左括号无右括号（循环结束时栈不空）