括号匹配

问题描述:

输入一行符号,以#结束,判断其中的括号是否匹配。括号包括:{}  []  ()  <>(用栈实现)

代码如下:

#include<iostream>
#include<stdlib.h>
#include<assert.h>
#include <stdio.h>
#include <string.h>
using namespace std;
struct StackNode {
public:
     char  data;
     StackNode *link;
     StackNode(char d = 0, StackNode *next = NULL) : data(d), link(next) { }
     ~StackNode( ){};
};
class LinkedStack  {
private:
    StackNode *top;
public:
      LinkedStack() : top(NULL) {}
    void Push(char &x);
    int  Pop(char & x);
    friend ostream & operator << (ostream& os, LinkedStack& s) ;
};
ostream& operator << (ostream& os, LinkedStack& S){
// //输出栈元素的重载操作 <<

     StackNode *p=S.top;int i=0;
    while(p!=NULL)
        {os<<++i<< ":" << p->data<<endl; p=p->link;}
    return os;
};

void LinkedStack::Push(char &x) {
//将元素值x插入到链式栈的栈顶,即链头。
     top = new StackNode( x, top );    //创建新结点
     assert (top != NULL);        //创建失败退出
};

int LinkedStack::Pop(char & x) {
//删除栈顶结点, 返回被删栈顶元素的值。
     if (top == NULL ) return 0;         //栈空返回
       StackNode *p = top;                    //暂存栈顶元素
     top = top->link;                  //退栈顶指针
     x = p->data;
     delete p;                  //释放结点
        return 1;
};

void judge(char s[]){
    LinkedStack L;
    char x;
    int j=0;
    int p1=0,p2=0;
    for(int i=0;s[i]!='#';i++)
    {
        char a=s[i];
        j++;
        switch(a)
        {
            case '(':
            case '[':
            case '{':
            case '<':
            L.Push(a);p1++;
            break;
        case ')':L.Pop(x);
        if(x!='(')
            cout<<"The "<<j<<" character "<<"')' is wrong."<<endl;
            p2++;
        break;
        case ']':L.Pop(x);
        if(x!='[')
            cout<<"The "<<j<<" character "<<"']' is wrong."<<endl;
            p2++;
        break;
        case '}':L.Pop(x);
        if(x!='{')
            cout<<"The "<<j<<" character "<<"'}' is wrong."<<endl;
            p2++;
            break;
        case '>':L.Pop(x);
        if(x!='<')
            cout<<"The "<<j<<" character "<<"'>' is wrong."<<endl;
            p2++;
        break;
        }
    }
    if(p1==p2)
    {
        cout<<"right"<<endl;
    }
    else if(p1>p2)
    {
        cout<<"loss of right character ";
        while(L.Pop(x))
        {
            if(x=='(')
            cout<<")";
            else if(x=='[')
                cout<<"]";
            else if(x=='{')
                cout<<"}";
            else
                cout<<">";
        }
        cout<<"."<<endl;
    }
}


int main()
{
    char  s[100] ;
    gets(s);
    judge(s);
    return 0;
}


You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注