解决问题的核心步骤.doc

解决问题的核心步骤：1、构造一个20字节的栈，不够再10个10个地追加2、从第一个字符开始检查，遇到左括号，进栈，遇见右括号时检查栈顶元素是否与之相匹配，是则弹出栈顶元素；否，则返回0程序构造思想主程序模块char main() 定义变量 定义指向栈的指针 读入字符串 调用Match()函数栈的初始化InitStack() 创建一个可以存储20个字节的栈 若创建失败，退出压栈PushStack() 判断栈是否栈满，栈满，追加 若存储分配失败，退出 e赋值给top所指向的单元 top向上移一位获取栈顶元素GetTop() 返回top-1所指单元的值匹配函数Match() for 从首字符开始判断 遇到左括号，进栈 遇到右括号，和栈顶字符比较，与之匹配，栈顶元素弹栈 遇到不匹配的右括号，提示配对失败 返回r值（bool函数）程序源代码#include #include #include #include#includeusing namespace std;#define STACK_INIT_SIZE 20#define STACKINCREMENT 10/类型说明typedef struct char * base; /设置栈底指针char * top; /设置栈顶指针int stacksize;SqStack;/构造一个栈Svoid InitStack(SqStack *S)S-base = (char *) malloc (STACK_INIT_SIZE ); /分配可以放得下个整数的内存空间。if(!S-base) exit (0); /存储分配失败S-top=S-base;S-stacksize=STACK_INIT_SIZE;/插入新的栈顶元素evoid Push(SqStack *S,char e)if(S-top - S-base =S-stacksize)/栈满，追加存储空间S-base =(char * )realloc(S-base, (S-stacksize + STACKINCREMENT);if(!S-base) exit (0); /存储分配失败S-top =S-base +S-stacksize ;S-stacksize +=STACKINCREMENT;* S-top=e;S-top+;/获取栈顶元素char GetTop(SqStack *S)if(S-top=S-base ) return 0;return *(S-top - 1); /弹出栈顶元素echar Pop(SqStack *S)if(S-top=S-base ) return 0;/栈空，返回ERRORreturn *(-S-top); /栈不空，用e返回栈顶元素/栈空int Empty(SqStack *S)if(S-base =S-top) return 1;else return 0;/匹配函数bool Match(char c40, SqStack *S)int i;bool r = true;InitStack(S);for(i=0;i20;i+) /从首元素开始判断if(ci&(ci=(|ci=)/是否为左括号，Push(S,ci); /是，进栈coutPush a parenthesis ci into the stack!endl;else if(ci&ci=) /是否为右括号if(GetTop(S)&GetTop(S)=()/是，判断前一括号是否为与之相对的括号Pop(S); /是，弹栈coutSuccess to match one pair of parenthesis ( ) endl; else coutFail to match a pair of parenthesis( )endl; r=false;else if(ci&ci=) /是否为右括号if(GetTop(S)&GetTop(S)=)/是，判断前一括号是否为与之相对的括号Pop(S); /是，弹栈coutSuccess to match one pair of parenthesis endl; elsecoutFail to match a pair of parenthesis endl; r = false; return r;char main()char c40;SqStack s, *S = &s;coutplease input a