头文件:
#pragma once #include <iostream> #include <assert.h> #include <string.h> using namespace std; template<class Type> class SeqStack { public: SeqStack(size_t sz = INIT_SZ); ~SeqStack(); public: bool empty()const; bool full()const; void show()const; bool push(const Type &x); bool pop(); void gettop(Type &x); int length()const; void clear(); void destory(); void quit_system(Type &x); private: enum{ INIT_SZ = 20 }; Type *base; int capacity; int top; }; template<class Type> SeqStack<Type>::SeqStack(size_t sz = INIT_SZ) { capacity = sz > INIT_SZ ? sz : INIT_SZ; base = new Type[capacity]; assert(base != NULL); top = 0; } template<class Type> SeqStack<Type>::~SeqStack() { destory(); } // 判断栈是否满了 template<class Type> bool SeqStack<Type>::full()const { return (top >= capacity); } // 判断是否为空栈 template<class Type> bool SeqStack<Type>::empty()const { return (top == 0); } // 显示 template<class Type> void SeqStack<Type>::show()const { if (top == 0) { cout << "the stack is empty!" << endl; return; } for (int i = top - 1; i >= 0; --i) { cout << base[i] << endl; } } // 入栈 template<class Type> bool SeqStack<Type>::push(const Type &x) { if (full()) { cout << "the stack is full,can not enter!" << endl; return false; } else { base[top] = x; top++; return true; } } // 出栈 template<class Type> bool SeqStack<Type>::pop() { if (empty()) { cout << "the stack is empty,can not pop!" << endl; return false; } else { top--; return true; } } // 获得栈顶元素 template<class Type> void SeqStack<Type>::gettop(Type &x) { x = base[top - 1]; } // 求栈长度 template<class Type> int SeqStack<Type>::length()const { return top; } // 清空栈 template<class Type> void SeqStack<Type>::clear() { top = 0; } // 摧毁栈 template<class Type> void SeqStack<Type>::destory() { delete[]base; base = NULL; capacity = top = 0; } // 退出系统 template<class Type> void SeqStack<Type>::quit_system(Type &x) { x = 0; }
主函数:
#include "stack.h" bool Check(const char *str) { SeqStack<char> mystack; char value; mystack.push('#'); while (*str != '\0') { if (*str == ')') { mystack.gettop(value); if (value == '(') { mystack.pop(); } else { return false; } } else if (*str == ']') { mystack.gettop(value); if (value == '[') { mystack.pop(); } else { return false; } } else { mystack.push(*str); } str++; } mystack.pop(); return mystack.empty(); } int main() { char *str = "[(()[])]"; bool flag = Check(str); if (flag) { cout << "OK" << endl; } else { cout << "Error" << endl; } return 0; }