栈-符号配对

[c++]代码库

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef char ElemType;
const int Max =(1e5+10) * 10;
typedef struct StackNode
{
    ElemType data;
    struct StackNode *next;
} StackNode,*LinkStack;

void Push(LinkStack &S,char ch)
{
    StackNode *p;
    p=new StackNode;
    p->data=ch;
    p->next=S;
    S=p;
}
int StackEmpty(LinkStack &S)
{
    if(S)
        return 0;
    else
        return 1;
}
char GetTop(LinkStack &S)
{
    if(S)
        return S->data;
}
void Pop(LinkStack &S)
{
    if(S)
    {
        StackNode *p;
        p=S;
        S=S->next;
        delete p;
    }
}
int main()
{
    LinkStack S=NULL;
    char str[Max];
    char str1[200];
    int flag=1,i=0;
    char a;
    while(gets(str)&&str[0]!='.')
    {
        int l=strlen(str);
        for(int j=0; j<l; j++)
        {
            if(str[j]=='/'&&str[j+1]=='*')
            {
                str1[i++]='x';
                j++;
            }
            else if(str[j]=='*'&&str[j+1]=='/')
            {
                str1[i++]='y';
                j++;
            }
            else if(str[j]=='('||str[j]==')'||str[j]=='{'||str[j]=='}'||str[j]=='['||str[j]==']')
                str1[i++]=str[j];
        }
    }
    int l2=strlen(str1);
    for(int j=0; (j<l2)&&(flag); j++)
    {
        a=str1[j];
        switch(a)
        {
        case '[':
        case '(':
        case '{':
        case 'x':
            Push(S,a);
            break;
        case 'y':
            if(!StackEmpty(S)&&GetTop(S)=='x')
                Pop(S);
            else if(StackEmpty(S))
            {
                cout<<"NO"<<endl<<"?-*/"<<endl;
                flag=0;
            }
            else if(GetTop(S)!='x')
            {
                if(GetTop(S)=='x')
                    cout<<"NO"<<endl<<"/*-?";
                else
                    cout<<"NO"<<endl<<GetTop(S)<<"-?";
                flag=0;
            }
            break;
        case ')':
            if(!StackEmpty(S)&&GetTop(S)=='(')
                Pop(S);
            else if(StackEmpty(S))
            {
                cout<<"NO"<<endl<<"?-)"<<endl;
                flag=0;
            }
            else if(GetTop(S)!='(')
            {
                if(GetTop(S)=='x')
                    cout<<"NO"<<endl<<"/*-?";
                else
                    cout<<"NO"<<endl<<GetTop(S)<<"-?";
                flag=0;
            }
            break;
        case ']':
            if(!StackEmpty(S)&&GetTop(S)=='[')
                Pop(S);
            else if(StackEmpty(S))
            {
                cout<<"NO"<<endl<<"?-]"<<endl;
                flag=0;
            }
            else if(GetTop(S)!='[')
            {
                if(GetTop(S)=='x')
                    cout<<"NO"<<endl<<"/*-?";
                else
                    cout<<"NO"<<endl<<GetTop(S)<<"-?";
                flag=0;
            }
            break;
        case '}':
            if(!StackEmpty(S)&&GetTop(S)=='{')
                Pop(S);
            else if(StackEmpty(S))
            {
                cout<<"NO"<<endl<<"?-}"<<endl;
                flag=0;
            }
            else if(GetTop(S)!='{')
            {
                if(GetTop(S)=='x')
                    cout<<"NO"<<endl<<"/*-?";
                else
                    cout<<"NO"<<endl<<GetTop(S)<<"-?";
                flag=0;
            }
            break;
        }
    }
    if(StackEmpty(S)&&flag)
        cout<<"YES";
    else if(!StackEmpty(S)&&flag)
    {
        if(GetTop(S)=='x')
            cout<<"NO"<<endl<<"/*-?";
        else
            cout<<"NO"<<endl<<GetTop(S)<<"-?";
    }
    return 0;
}