数据结构 栈和队列括号匹配检测

#include \"stdafx.h\" #include #include #include using namespace std;

const int Increament = 20; template

class SeqStack //顺序栈类定义 {

public:

SeqStack(int sz = 50); //构造函数

~SeqStack() { delete[]elements; } //析构函数 void Push(const T& x); //进栈 bool Pop(T& x); //出栈

bool getTop(T& x); //取栈顶元素 bool IsEmpty() const { return top == -1; }

bool IsFull() const { return top == maxSize - 1; } int getSize()const { return top + 1; } void MakeEmpty() { top = -1; } void output(); private:

T *elements; //栈元素存放数组 int top; //栈顶指针

int maxSize; //栈最大容量 void overflowProcess(); //栈的溢出处理 };

template

SeqStack::SeqStack(int sz) : top(-1), maxSize(sz) {

elements = new T[maxSize]; assert(elements != NULL); }

template

void SeqStack::overflowProcess() //栈满，溢出处理 {

T *newArray = new T[maxSize + Increament]; assert(newArray != NULL); for (int i = 0; i <= top; i++) newArray[i] = elements[i]; maxSize = maxSize + Increament; delete[]elements;

elements = newArray; }

template

void SeqStack::Push(const T& x)

{ //若栈不满, 则将元素x插入栈顶, 否则溢出处理 if (IsFull() == true) overflowProcess(); //栈满 elements[++top] = x; //栈顶指针先加1, x再进栈 }

template

bool SeqStack::Pop(T& x)

{ //若栈不空，返回栈顶元素的值，栈顶指针退1 if (IsEmpty() == true) return false; x = elements[top--]; //栈顶指针退1 return true; //退栈成功 }

template

bool SeqStack::getTop(T& x)

{ //若栈不空则函数返回该栈栈顶元素的值 if (IsEmpty() == true) return false; x = elements[top]; return true; }

template

void SeqStack::output() {

cout << \"top = \" << top << endl; if (top == -1) cout << \"空栈!\"； else {

for (int i = 0; i <= top; i++)

cout << setw(5) << elements[i]; }

cout << endl; }

bool Match(char *expression) {

SeqStack S(20); char ch, x; int i, length = strlen(expression),t=1; for (i = 0; ich = expression[i]; switch (ch) {

case'(': case'{':

case'[':S.Push(ch);break; case')': {

S.Pop(x); if (x == '(') t = 1; else

t = 0; }break; case']': {

S.Pop(x); if (x == '[') t = 1; else t = 0; }break; case'}': {

S.Pop(x); if (x == '{') t = 1; else t = 0; }break;

default:break; } if (!t) break; }

if (t == 1 && S.IsEmpty() == true) {

cout << \"success\" << endl; return true; } else {

cerr << \"failure\" << endl; return false; } }

int main() {

char c[20]; cin >> c; Match(c); return 0; }