西北工业大学NOJ数据结构—007表达式括号匹配

题意如下，输入一个表达式来判断这个表达式的括号是否匹配（づ￣3￣）づ╭❤～

    本题为栈的应用，整体思路如下(⇀‸↼‶)：

    依次读入一串字符串，若   

    1.是左括号，则直接Push压进栈

    2.如果是字符则继续读取下一个字符

    3.如果是右括号，则与栈顶元素的左括号比较是否匹配，即‘）’与‘（’，‘】’与‘【’，‘}’与‘{’匹配

如果出现不匹配则直接打印no并停止运行；

如果匹配成功则将栈顶的左括号弹出；

    4.等到所有字符串都读取完毕之后，要检查栈是否为空，即栈内是否留有左括号

如果有则返回no；

如果栈空则返回yes，即表达式符合 （づ￣3￣）づ╭❤～

下边直接上代码（顺便提一句，noj测试数据太少，很多情况根本不会测试，比如可以试着将最后一个no改为yes，会发现！同样AC！\(^o^)/）

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Node{//定义带有节点的链表
	char KuoHao;
	struct Node *next;
}Node;

typedef struct LinkStack{//定义栈顶指针
	struct Node *top;
}stack;

stack *creat(void)
{//生成一个空栈并返回栈
	stack *plstack;
	plstack=(struct LinkStack*)malloc(sizeof(struct LinkStack));
	if(plstack!=NULL)
		plstack->top=NULL;
	else
		printf("out!\n");
	return plstack;
}

int is_empty(stack *plstack)
{//判断栈是否为空
	return(plstack->top==NULL);
}

void Push(stack *plstack,char x)
{//从栈顶压入一个元素
	struct Node *p;
	p=(struct Node*)malloc(sizeof(struct Node));
	if(p==NULL)
		printf("out!\n");
	else
	{
		p->KuoHao=x;
		p->next=plstack->top;
		plstack->top=p;
	}
}

char pop(stack *plstack)
{//从栈中弹出一个元素并返回该元素
	struct Node *p;
	char elem;
	if(is_empty(plstack))
		printf("out!");
	else
	{
		p=plstack->top;
		elem=p->KuoHao;
		plstack->top=plstack->top->next;
		free(p);
	}
	return elem;
}

char toplink(stack *plstack)
{//返回栈顶元素
	if(is_empty(plstack))
		printf("out!");
	return plstack->top->KuoHao;
}

int Match(char e,char ch)  
{  //比较两个字符
    if (e=='('&&ch==')')  
    {  
        return 1;  
    }   
    else if (e=='['&&ch==']')  
    {  
        return 1;  
    }   
    else if (e=='{'&&ch=='}')  
    {  
        return 1;  //如果两个元素是匹配的括号则返回1
    }  
    else  
    {  
        return 0;  //否则返回0
    }  
  
}  

int main()  
{  
    stack *s;  
    char *p;  
    char e;  
    char ch[60];  
    s=creat();  //初始化链栈  
    gets(ch); 
    p=ch;  //p作为数组的“指针”移动来获取数据
    while(*p)  
    {  
        switch(*p)  
        {  
        case '(':  //如果是左括号直接进栈
        case '[':  
        case '{':  
            Push(s,*p++);  
            break;  
        case ')':  
        case ']':  
        case '}': 
            if (is_empty(s)==1)  //如果是右括号则先检查是否为空
            {  
                printf("no");  
                return 0;  //直接return出main函数 不再执行下边的代码，否则会打印两次no
            }  
            else  
            {  
                e=toplink(s);  
                if (Match(e,*p))  //如果不空则比较右括号和栈顶括号
                {  
                    pop(s);  
                }  
                else  
                {  
                    printf("no");  //不匹配则返回no
                    return 0;  
                }  
            }  
        default:    //如果是其他字符，则不处理，直接指向下一个字符  
            p++;  
        }  
    }  
    if (is_empty(s))  
    {  
        printf("yes");  
        return 1;  //所有元素结束后检查栈是否为空
    }   
    else  
    {  
        printf("no");  //如果为空且之前元素都匹配则输出yes
        return 0;  
    }  
}