数据结构括号匹配实验报告

^.括号的匹配1.需求和规格说明（1）实现括号的是否匹配的判定。（2）实现匹配错误的提示。（3）实现栈内容的动态显示。2．设计2.1．设计思想（1）对于括号匹配的判定，首先输入字符串到缓冲区。逐个字符读取字串，遇到的是左括号则入栈，若是右括号，则出栈。出栈的左括号如果和右括号匹配，则一对括号匹配成功；否则，这对括号匹配失败，并给出错误提示。谢谢阅读（2）分析括号匹配错误出现的情况，主要有三种：左括号数大于右括号数，左括号与右括号不匹配，右括号数大于左括号数。根据栈的存储情况就能判定出这三种情况，并且实时的将信息放映到可视化控件上。精品文档放心下载（3）对于匹配过程和栈内容的动态显示，可以用listbox控件实时的显示和更新。窗口上有两个listbox控件，第一个动态显示push和pop动作以及提示错误信息；第二个listbox则动态模拟栈内的存储情况。谢谢阅读2.2．设计表示(1)存储结构Node节点template<classelement>classNode{public:elementele;Node*pre; //前驱指针Node*next; //后继指针Node(){pre=NULL;next=NULL;}Node(elemente){ele=e;pre=NULL;next=NULL;}^.Node*MakeNode(elemente)//传入参数返回一个节点指针，实现参数的封装。{精品文档放心下载Node<element>*temp=newNode(e);感谢阅读returntemp;}};MyListStack链栈template<classelement>classMyListStack{public:Node<element>*base;Node<element>*top;intindex;MyListStack() //初始化链表{base=newNode<element>();top=base;index=0;}voidpush(elementn){

//pushNode<element>*temp=newNode<element>(n);谢谢阅读top->next=temp;temp->pre=top;top=temp;index++;}voidpop(element&out){

//popout=top->ele;top=top->pre;deletetop->next;top->next=NULL;index--;}BOOLisEmpty();{

//返回栈是否为空if(index)^.returnFALSE;elsereturnTRUE;}virtual ~MyListStack() //析构链栈，释放空间。精品文档放心下载{Node<element>*p=base;Node<element>*q=p->next;while(p->next!=NULL){deletep;p=q;q=p->next;}deletep;}};(2)涉及的操作voidCKuohaopipeiDlg::OnButtonClear()//清空窗口控件。精品文档放心下载voidCKuohaopipeiDlg::OnButtonSlowShow( //慢速显示运行过程。精品文档放心下载voidCKuohaopipeiDlg::OnOK()//进行括号匹配过程。谢谢阅读voidCKuohaopipeiDlg::OnSelchangeListInfo()//此函数响应列表框中光标改变的消息，定位错误的位置。精品文档放心下载2.3．实现注释（此部分见源代码中注释）2.4．详细设计表示(1)流程示意图^.图表1匹配流程示意图（2）功能示意图图表2功能示意图^.3．用户手册(1)在编辑框中输入表达式串。(2)点击开始匹配测试则进行快速匹配。(3)点击慢速运行。(4)点击错误信息，定位错误字符。4．调试报告输入：{{{[1+1]+(A+d)}}} 结果：正确感谢阅读输入：{{{{}}}})) 结果：错误输入：}()){}} 结果：错误输入：([][])) 结果：错误5.源代码及运行结果截图(1)源代码voidCKuohaopipeiDlg::OnOK()精品文档放心下载{//TODO:Addextravalidationhere谢谢阅读UpdateData(TRUE);//MyListStack<char> ls;m_list_info.ResetContent(); //清空list谢谢阅读m_list_stack.ResetContent(); //清空list感谢阅读BOOLisNum=0;BOOLisError=0;intinputlength=m_cstring_input.GetLength();精品文档放心下载if(inputlength==0){MessageBox("输入值不能为空!","提示");//如果字符串为空感谢阅读}else{for(intj=0;j<inputlength;j++) //获取输入字串的长度谢谢阅读{charstr_in=m_cstring_input.GetAt(j);精品文档放心下载if(str_in=='('||str_in=='['||str_in=='{')谢谢阅读{isNum=1;ls.push(str_in);//若为左括号则入栈CStringtemp;谢谢阅读temp.Format("push%cintostack\r\n",str_in);谢谢阅读^.m_list_info.AddString(temp);感谢阅读}elseif(str_in==')'||str_in==']'||str_in=='}')//若为右括号感谢阅读则出栈匹配{isNum=1;charstr_out;if(!ls.isEmpty()){ls.pop(str_out);BOOLflag=0;if(str_in==')'&&str_out=='(')感谢阅读{flag=1;}if(str_in==']'&&str_out=='[')感谢阅读{flag=1;}if(str_in=='}'&&str_out=='{')感谢阅读{flag=1;}if(!flag//如果匹配不成功,则isError变量为1，并更新感谢阅读提示信息。{isError=1;CStringtemp;temp.Format("push%cbutcannotmatch%c<--error!",str_out,str_in);谢谢阅读m_list_info.AddString(temp);精品文档放心下载}else //如果匹配成功,更新提示信息。{CStringtemp;^.temp.Format("pop%coutofstack\r\n",str_out);精品文档放心下载m_list_info.AddString(temp);谢谢阅读}}else//如果当前栈为空，且输入为右括号时，isError为1，并更新控件信息。感谢阅读{isError=1;CStringtemp;temp.Format("cannotmatch%c<--error!",str_in);m_list_info.AddString(temp);谢谢阅读}}m_list_info.RedrawWindow();精品文档放心下载UpdateData(FALSE);}if(!ls.isEmpty())//如果栈最后不为空，且栈中还有左括号，则提示栈中左括号没有匹配完成。谢谢阅读{chartemp;ls.pop(temp);ls.push(temp);if(temp=='('||temp=='{'||temp=='[')谢谢阅读{CStringtemp;temp="stackisnotempty<--error!";精品文档放心下载m_list_info.AddString(temp);谢谢阅读}}if(ls.isEmpty()&&isNum==1&&!isError)精品文档放心下载{m_list_info.AddString("matchsuccess!");感谢阅读MessageBox("匹配成功!","提示");}elseif((!ls.isEmpty()&&isNum==1)||isError)感谢阅读{m_list_info.AddString("matchfailed!");感谢阅读MessageBox("匹配失败!","提示");^.}elseif(isNum==0){MessageBox("表达式中未出现括号!","提示");感谢阅读}}chartemp;while(ls.index!=0){ls.pop(temp);}((CEdit*)GetDlgItem(IDC_EDIT_INPUT))->SetFocus();感谢阅读((CEdit*)GetDlgItem(IDC_EDIT_INPUT))->SetSel(0,-1);感谢阅读}voidCKuohaopipeiDlg::OnButtonSlowShow() //慢速显示运行过程精品文档放心下载{//TODO:Addyourcontrolnotificationhandlercodehere精品文档放心下载TODO:Addextravalidationherem_list_info.SetRedraw();m_list_stack.SetRedraw();UpdateData(TRUE);精品文档放心下载m_list_info.ResetContent();谢谢阅读m_list_stack.ResetContent();精品文档放心下载BOOLisNum=0; //判断是否出现括号BOOLisError=0; //判断是否出现错误谢谢阅读intinputlength=m_cstring_input.GetLength(); //获取输入字串长度感谢阅读if(inputlength==0){MessageBox("输入值不能为空!","提示");感谢阅读}else{for(intj=0;j<inputlength;j++) //逐次获取字符感谢阅读{charstr_in=m_cstring_input.GetAt(j);精品文档放心下载if(str_in=='('||str_in=='['||str_in=='{') //如果为左括弧，则入栈。谢谢阅读{isNum=1;ls.push(str_in);^.CStringtemp;temp.Format("push%cintostack\r\n",str_in);精品文档放心下载m_list_info.AddString(temp);谢谢阅读m_list_info.SetCurSel(m_list_info.GetCount()-1);谢谢阅读temp.Format("%c",str_in);m_list_stack.AddString(temp);精品文档放心下载}elseif(str_in==')'||str_in==']'||str_in=='}')谢谢阅读{

//如果为右括弧isNum=1;charstr_out;if(!ls.isEmpty()){ls.pop(str_out);BOOLflag=0;if(str_in==')'&&str_out=='(')谢谢阅读{

//pop括号，判断是否匹配flag=1;}if(str_in==']'&&str_out=='[')感谢阅读{flag=1;}if(str_in=='}'&&str_out=='{')谢谢阅读{flag=1;}if(!flag){isError=1;//如果不匹配，则此变量为真，便于函数末尾判断。精品文档放心下载CStringtemp;temp.Format("push%cbutcannotmatch%c<--error!",str_out,str_in);//将信息传入控件精品文档放心下载m_list_info.AddString(temp);精品文档放心下载m_list_stack.DeleteString(m_list_stack.GetCount()-1);精品文档放心下载m_list_info.SetCurSel(m_list_info.GetCount()-1);谢谢阅读^.}else //如果匹配成功，将信息显示到控件。{CStringtemp;temp.Format("pop%coutofstack\r\n",str_out);精品文档放心下载m_list_info.AddString(temp);感谢阅读m_list_stack.DeleteString(m_list_stack.GetCount()-1);精品文档放心下载m_list_info.SetCurSel(m_list_info.GetCount()-1);精品文档放心下载}}else{//如果栈中无括号了，且输入括号为右括号。isError=1;CStringtemp;temp.Format("cannotmatch%c<--error!",str_in);感谢阅读m_list_info.AddString(temp);精品文档放心下载m_list_info.SetCurSel(m_list_info.GetCount()-1);谢谢阅读}}m_list_info.RedrawWindow(); //重画控件谢谢阅读m_list_stack.RedrawWindow();感谢阅读Sleep(600);UpdateData(FALSE);}if(!ls.isEmpty()) //如果栈中还有左括号，说明右括号的数量小于左括号的数量。精品文档放心下载{chartemp;ls.pop(temp);ls.push(temp);if(temp=='('||temp=='{'||temp=='[')精品文档放心下载{CStringtemp;temp="stackisnotempty<--error!"; //提示栈中还有未匹配的左括号。精品文档放心下载m_list_info.AddString(temp);谢谢阅读m_list_info.SetCurSel(m_list_info.GetCount()-1);精品文档放心下载}^.}if(ls.isEmpty()&&isNum==1&&!isError)感谢阅读{m_list_info.AddString("matchsuccess!");精品文档放心下载MessageBox("匹配成功!","提示");}elseif((!ls.isEmpty()&&isNum==1)||isError)谢谢阅读{m_list_info.AddString("matchfailed!");精品文档放心下载MessageBox("匹配失败!","提示");}elseif(isNum==0){MessageBox("表达式中未出现括号!","提示");谢谢阅读}}chartemp;while(ls.index!=0) //清空栈中的内容谢谢阅读{ls.pop(temp);}((CEdit*)GetDlgItem(IDC_EDIT_INPUT))->SetFocus();感谢阅读((CEdit*)GetDlgItem(IDC_EDIT_INPUT))->SetSel(0,-1);精品文档放心下载}voidCKuohaopipeiDlg::OnButtonClear()精品文档放心下载{//TODO:Addyourcontrolnotificationhandlercodehere