表达式括号匹配配对判断问题.doc

实验 表达式括号匹配配对判断问题 姓名： 班 级： 学号： 1，问题的描述 假设一个算法表达式中包括圆括号，方括号两种，设计判别表达式中括号是否正确匹配的算法。 2，数据结构设计 （1）匹配判别发生在右括号出现时，且被匹配的左括号应是距离右括号最近被输入的，二不是最先被输入的括号 ，即“先入后匹配”。因此用栈来解决。 struct Node { int top; char data[stacksize]; }; Node node; void InitStack( ) // 初始化栈 { node.top=-1; } （2）一是表达式的串；二是栈。串可以采用顺序表表示。所以采用顺序栈，站元素类型为字符型。 sqstack(int n) { base=newT[m]; if(base=NULL){ cout“创栈失败”； exit（1）； } stacksize=m;top=-1;} } 3,算法设计 （1）进栈的算法设计 voidPush(charx) { if(node.top==stacksize-1); node.top++; node.data[node.top]=x; } （2）出栈的算法设计 void Pop(char x) { if(node.top==-1); x=node.data[node.top--];} （3）判断是否匹配的算发。如果右括号，进栈，取下个字符；如果是左括号，出栈，取下个字符；最后判断栈是否为空；得出结论。 3．1因为其中包含几种括号，所以用采用switch语句 for(i=0;*(p+i)!=\0count!=0;i++) { switch (*(p+i)) { case ( : Push(*(p+i)) ; break ; case [ : Push(*(p+i) ) ; break ; case ) : { Pop(e) ; if ( e!=( ) count=0 ; }; break ; case ] : { Pop(e) ; if ( e!=[ ) count=0 ; }; break ;