数据结构day12

寄吧vscode用的时候又出毛病了，浪费了好多时间也没得解决，重新用的DevC++。

依次输入括号，如果括号匹配出错立刻输出Error并退出，直到结束括号全部匹配正确则输出OK并退出。

确保正确的括号字符串中第一个括号与最后一个匹配，即不会出现"()[]"这种字符串输入，即栈空为结束
本代码设计的输入方式为依次输入一个括号字符，检测到匹配错误项会立刻报错并终止
使用栈来实现

使用栈来解决。当接收到字符为左括号时，入栈即可。当输入道右括号时，说明在此之前最近的一个左括号应该和其匹配，即栈顶元素，匹配成功后左括号出栈。先将第一个括号字符入栈，然后根据栈空判断是否有括号尚未匹配完成。

#include 
#include 

typedef struct SqStack{
    char data[10];		//存储括号字符
    int i;		//栈顶指针，始终指向最后入栈元素
}SqStack;


bool Push(SqStack &S,char x){
    if(S.i==9)
        return false;		//栈满
    S.i=S.i+1;
    S.data[S.i]=x;
    return true;
}

bool Pop(SqStack &S,char &x){
    if(S.i==-1)
        return false;		//栈空
    x=S.data[S.i];
    S.i=S.i-1;
    return true;
}

int level(char ch){
    if(ch=='('||ch==')')
        return 1;
    else if(ch=='['||ch==']')
        return 2;
    else if(ch=='{'||ch=='}')
        return 3;    
}

int empty(SqStack S){
	return (Pop(S,S.data[S.i]));		//出栈返回false即为空
}

int main()
{
    SqStack S;
    S.i=-1;		//栈顶指针初始化为-1，即栈空
    char ch=getchar();		//输入第一个括号字符
    Push(S,ch);		//将第一个括号字符入栈
    while(empty(S)!=0)		//栈空即输入结束
    {
		  ch=getchar();			
        if(ch=='('||ch=='['||ch=='{')
            Push(S,ch);		//左括号入栈
        if(ch==')'||ch==']'||ch=='}'){
            if(level(S.data[S.i])==level(ch))
                Pop(S,S.data[S.i]);		//匹配成功将对应左括号出栈
            else{
                printf("Errorn");		//匹配失败立刻报错终止
                system("pause");
                return 0;
            }
        }
    }
    printf("OKn");
    system("pause");    
}

输入一串字符串，然后将字符串依次传入。当传入过程中间有匹配错误，或者字符串全部传完后栈没有空，说明该括号字符串存在匹配错误。若字符串依次全部传入后过程没有匹配出错，结束后栈为空栈，则该括号字符串正确。