/1、实现栈类
//2、检测表达式括弧匹配
//2006 05 13
#include <iostream.h>
#include<string>

class Node{
public:
    int data;
    Node *next;
};
class Stack:public Node{
    Node *Bottom;
    Node *Top;
    int SLen;
public:
    void InitStack();
    char Pop();
    void Push(int e);
    bool StackEmpty();
};

void Stack::InitStack()
{
    Top=new Node;
    Bottom=Top;
    SLen=0;
}
char Stack::Pop()
{
    char e;
    Node *p;
    if(!(Top->next))
        exit(0);
    else
    {
        p=Top;
        e=p->data;
        Top=p->next;
        delete p;
        SLen--;
    }
    return e;
}
void Stack::Push(int e)
{
    Node* p=new Node;
    p->next=Top;
    p->data=e;
    Top=p;
    SLen++;
}
bool Stack::StackEmpty()
{
    if(SLen==0)
        return 1;
    else
        return 0;
}

void Matching(char exp[])
{
    int state=1;
    char e;
    Stack s;
    s.InitStack();
    int i=0;
    while(i<strlen(exp)&&state)
    {
        state=0;
        switch(exp[i])
        {
        case'(':
        case'[':
        case'{':
        {
            s.Push(exp[i]);
            i++;
            state=1;
            break;
        }
        case')':
        {
            if(s.StackEmpty!=0)
            {
                e=s.Pop();
                if(e=='(')
                {i++;state=1;break;}
                else
                {cout<<"不匹配";break;}
            }
        }
        case']':
            {
            if(s.StackEmpty!=0)
            {
                e=s.Pop();
                if(e==']')
                {i++;state=1;break;}
                else
                {cout<<"不匹配";break;}
            }
        }
        case'}':
        {
            if(s.StackEmpty!=0)
            {
                e=s.Pop();
                if(e=='{')
                {i++;state=1;break;}
                else
                {cout<<"不匹配";break;}
            }
        }
        default:break;
        }
    }
    if(s.StackEmpty()&&state)
        cout<<"匹配成功";

}





void main()
{    char exp[]="((((()))){})";
    Matching(exp);
}

评论