【数据结构】--栈--括号匹配

在pop（）；那个地方卡了好一会，原来是NULL这个情况没有考虑

用栈实现：输入一行符号,以#结束，判断其中的括号是否匹配。括号包括：

{}  []  ()  <>

 

 

例如:

输入Result as(*x<{(({<>}))}>)# right (a.b)># The 6 character '>' is wrong. ({()# loss of right character }).

 

#include <iostream> #include<bits/stdc++.h> using namespace std; struct LinkNode { char data; LinkNode *next; }; class Stack { private: LinkNode *top; public: Stack() { top=NULL; } ~Stack(); void Push(char val); void Pop(); char Top(); bool Is_empty(); }; Stack::~Stack() { while(top) { LinkNode *p=new LinkNode; p=top->next; delete top; top=p; } } void Stack::Push(char val) { LinkNode *newnode=new LinkNode; newnode->data=val; newnode->next=top; top=newnode; } void Stack::Pop() { if(top!=NULL) { // cout<<top->data<<endl; // cout<<top->next->data<<endl; // cout<<"sdfghjik"<<endl; if(top->next==NULL) top=NULL; else { top->data=top->next->data; top=top->next; } } } char Stack::Top() { if(top!=NULL) { char ans=top->data; return ans; } } bool Stack::Is_empty() { if(top==NULL) return true; return false; } int main() { Stack s; // s.Push('a'); // s.Push('b'); // s.Push('c'); //cout<<s.Top()<<endl; // s.Pop(); //cout<<s.Top()<<endl; // s.Pop(); //cout<<s.Top()<<endl; // s.Pop(); char str[1000]; scanf("%s",str); int f=1; for(int i=0; i<strlen(str); i++) { if(f==2) continue; if(str[i]=='#') break; if((str[i]>='a'&&str[i]<='z')||(str[i]>='A'&&str[i]<='Z')) { continue; } if(str[i]=='('||str[i]=='{'||str[i]=='['||str[i]=='<') { s.Push(str[i]); } if(str[i]==')') { if(s.Is_empty()) { f=2; printf("The %d character ')' is wrong.",i+1); continue; } if(s.Top()=='(') { s.Pop(); } } if(str[i]=='}') { if(s.Is_empty()) { f=2; printf("The %d character '}' is wrong.",i+1); continue; } if(s.Top()=='{') { s.Pop(); } } if(str[i]==']') { if(s.Is_empty()) { f=2; printf("The %d character ']' is wrong.",i+1); continue; } if(s.Top()=='[') { s.Pop(); } } if(str[i]=='>') { if(s.Is_empty()) { f=2; printf("The %d character '>' is wrong.",i+1); continue; } if(s.Top()=='<') { s.Pop(); } } } if(f==1) { if(s.Is_empty())printf("right\n"); else { cout<<"loss of right character "; while(!s.Is_empty()) { if(s.Top()=='(') { cout<<')'; } if(s.Top()=='{') { cout<<'}'; } if(s.Top()=='<') { cout<<'>'; } if(s.Top()=='[') { cout<<']'; } s.Pop(); } cout<<"."; } } return 0; }