栈-----链式存储结构及其操作算法的实现-----括号匹配问题
//file:stack_link.h#ifndef STACK_LINK_H_INCLUDED#define STACK_LINK_H_INCLUDEDtemplate <class T>class node{ public: T data; node<T>* next; node():next(NULL) {}; //No-arg constructor node(T p)//Constructor { this->data=p;//"this" means "class node" next=NULL; };};template <class T>class stack{public: stack(); bool empty(); void push(T x); void pop(); T top();private: node<T>* L;};template <class T>stack<T>::stack(){ L=new node<T>; L->next=NULL;};template <class T>bool stack<T>::empty(){ if(L->next==NULL)return true; else return false;}template <class T>void stack<T>::push(T x){ node<T>* s=new node<T>; s->data=x; s->next=L->next; L->next=s;}template <class T>void stack<T>::pop(){ node<T>* s=L->next; if(!empty()) { L->next=s->next; delete s; }}template <class T>T stack<T>::top(){ if(L->next) return L->next->data; else ;}#endif
//检查括号匹配#include <iostream>#include <stdio.h>#include "stack_link.h"#define maxlen 1000char a[maxlen];using namespace std;int main(){ stack<char> s; int i=0,j=0; char m; while(cin >> m && m!='#') i++; while (j<=i-1) { if(a[j]=='('||a[j]=='['||a[j]=='{') s.push(a[j]); else if(a[j]==')') { if(!s.empty()&&s.top()=='(') s.pop(); else break; } else if(a[j]==']') { if(!s.empty()&&s.top()=='[') s.pop(); else break; } else if(a[j]=='}') { if(!s.empty()&&s.top()=='{') s.pop(); else break; } j++; } if(j==i&&s.empty()) printf("匹配正确\n"); else printf("匹配错误\n"); return 0;}