数据结构实验之栈四：括号匹配

Problem Description

 给你一串字符，不超过50个字符，可能包括括号、数字、字母、标点符号、空格，你的任务是检查这一串字符中的( ) ,[ ],{ }是否匹配。

Input

 输入数据有多组，处理到文件结束。

Output

 如果匹配就输出“yes”，不匹配输出“no”

Example Input

sin(20+10)

{[}]

Example Output

yes

no

Hint

#include<bits/stdc++.h>
using namespace std;
#define STACK_INIT_SZIE 100//每次分配的空间个数
#define STACK_INCREMENT 10//每次追加的空间个数
#define OK 1;
#define ERROR 0;

typedef char ElemType;
typedef struct
{
    ElemType *top;
    ElemType *base;
    int stacksize;
}mystack;

void Initialstack(mystack &s)//栈的初始化
{
    s.base = (ElemType *)malloc(STACK_INIT_SZIE*sizeof(ElemType));
    if(!s.base)
    {
        exit(OVERFLOW);
    }
    s.top = s.base;
    s.stacksize = STACK_INIT_SZIE;
}

void Push(mystack &s, ElemType &e)//入栈
{
    if(s.top - s.base == s.stacksize)//栈满
    {
        s.base = (ElemType *)realloc(s.base,(s.stacksize + STACK_INCREMENT)*sizeof(ElemType));
        if(!s.base)
        {
            exit(OVERFLOW);
        }
        s.top = s.base + s.stacksize;
        s.stacksize += STACK_INCREMENT;
    }
    *(s.top)++ = e;
}

int Pop(mystack &s)//出栈
{
    if(s.top == s.base)//空栈
    {
        return ERROR;
    }
    else
        s.top--;
    return OK;
}

int Top(mystack &s, ElemType &e)//访问栈顶元素
{
        if(s.top == s.base)//空栈
    {
        return ERROR;
    }
    else
        e = *(--s.top);
    s.top++;
    return OK;
}

int main()
{
    char str[100];
    ElemType e;
    int n, i, f;
    while(gets(str))
    {
        mystack s;
        Initialstack(s);
        n = strlen(str);
        f = 1;
        for(i = 0; i < n; i++)
        {
            if(str[i] == '('|| str[i] == '[' || str[i] == '{' || str[i] == '}' || str[i] == ']' || str[i] == ')')
                {
                    if(str[i] == '('|| str[i] == '[' || str[i] == '{' )
                        {

                            Push(s,str[i]);
                        }
                    else
                    {

                        if(str[i] == ')')
                        {
                           if(!Top(s, e))
                            {
                                f = 0;
                                break;
                            }
                            if(e!='(')
                            {
                                f = 0;
                                break;
                            }
                            else
                                Pop(s);
                        }
                        else if(str[i] == '}')
                        {
                            if(!Top(s, e))
                            {
                                f = 0;
                                break;
                            }
                            if(e!='{')
                            {
                                f = 0;
                                break;
                            }
                            else
                                Pop(s);
                        }
                        else if(str[i] == ']')
                        {
                            if(!Top(s, e))
                            {
                                f = 0;
                                break;
                            }
                            if(e!='[')
                            {
                                f = 0;
                                break;
                            }
                            Pop(s);
                        }
                    }
                }
        }
        if(f)
        {
            if(!Top(s,e))
                f = 1;
            else
                f = 0;
        }
        if(f)
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}