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

数据结构括号匹配实验报告 　　1、A括号的匹配1. 需求和规格说明(1) 实现括号的是否匹配的判定。(2) 实现匹配错误的提示。(3) 实现栈内容的动态显示。2. 设计2.1.设计思想(1)对于括号匹配的判定，首先输入字符串到缓冲区。逐个字符读取字串，遇到的是左括 号则入栈，若是右括号，则出栈。出栈的左括号如果和右括号匹配，则一对括号匹配成功； 否则，这对括号匹配失败，并给出错误提示。(2 )分析括号匹配错误出现的情况，主要有三种：左括号数大于右括号数，左括号与右括号不匹配，右括号数大于左括号数。根据栈的存储情况就能判定出这三种情况，并且实时的将信息放映到可视化控件上。(3) 对于匹配过程和栈内容的动态显示，可以用listbo 　　2、x 控件实时的显示和更新。窗口上有两个 listbox 控件，第一个动态显示 push 和 pop 动作以及提示错误信息；第二个 listbox 则动态模拟栈内的存储情况。2.2 .设计表示(1)存储结构Node 节点template class Nodepublic:eleme nt ele;Node *pre;前驱指针Node *n ext; /后继指针Node()pre=NULL; next=NULL;Node(eleme nt e) ele=e; pre=NULL; next=NULL;Node * MakeNode(eleme nt e)/传入参数返回一个节点指针, Nodevele 　　3、me nt *temp=new Node(e); return temp;实现参数的圭寸装A；MyListStack 链栈template class MyListStackpublic:Node *base;Node *top;int in dex;MyListStack()初始化链表base=new Node();top=base;in dex=0;void push(eleme nt n)/pushNode *temp=new Node(n); top-n ext=temp;temp-pre=top;top=temp;in dex+;void pop(eleme nt & out 　　4、) /popout=top-ele; top=top-pre; delete top-n ext; top-n ext=NULL; in dex-;BOOL isEmpty();返回栈是否为空if(i ndex) return FALSE;elsereturn TRUE;virtual MyListStack()析构链栈，释放空间Nodeveleme nt *p=base;Nodeveleme nt *q=p-n ext;while(p- next!=NULL)delete p; p=q;q=p-n ext;Adelete p;(2)涉及的操作void CKuohaopipeiDlg:O nB 　　5、utto nClear() / 清空窗口控件。void CKuohaopipeiDlg:O nButto nSlowShow( 慢速显示运行过程。void CKuohaopipeiDlg:O nOK() / 进行括号匹配过程。void CKuohaopipeiDlg:OnSelchangeListlnfo() / 此函数响应列表框中光标改变的 消息，定位错误的位置。2.3 .实现注释(此部分见源代码中注释)2.4 .详细设计表示(1)流程示意图A（2）功能示意图图表 2 功能示意图A3用户手册(1)在编辑框中输入表达式串。开始匹配测试则进行快速匹配。(3)慢速运行。(4)错误信息， 　　6、定位错误字符。4 调试报告输入：1+1+(A+d)结果: 正确输入：)结果: 错误输入：()结果: 错误输入：()结果: 错误5.源代码及运行结果截图(1)源代码void CKuohaopipeiDlg:O nOK()/ TODO: Add extra validation hereUpdateData(TRUE);MyListStack ls;mist_info.ResetContent();/清空 listmist_stack.ResetContent(); / 清空 listBOOL isNum=0;BOOL isError=0;int in putle ngth=m_cstri ng_ 　　7、in put.GetLe ngth();if (in putle ngth=0)MessageBox(输入值不能为空!,提示);/如果字符串为空elsefor(i nt j=0;ji nputle ngth;j+) /输入字串的长度char str_i n=m_cstri ng_in put.GetAt(j);if (str_i n=二(|str_i n=二|str_i n=二) 一 一isNum=1;ls.push(str_i n);/若为左括号则入栈CStri ng temp;Atemp.Format(push %c into stack rn ,str_i n);Am_l ist_i 　　8、 nfo.AddStri ng(temp);else if(str_i n=)|str_i n=|str_i n=)/若为右括号则出栈匹配isNum=1;char str_out;if (!ls.isEmpty()ls.pop(str_out);BOOL flag=0;if (str_i n=)&str_out=() 一 一flag=1;if (str_i n=&str_out=)flag=1;if (str_i n=&str_out=) 一 一flag=1;if (!flag /如果匹配不成功，则 isError 变量为 1，并更新提示信息。isError=1;CSt 　　9、ri ng temp;temp.Format(push %c but can not match %cm_l ist_i nfo.AddStri ng(temp);CStri ng temp;v-error!,str_out,str_in);else /如果匹配成功，更新提示信息Atemp.Format(pop %c out of stack rn ,str_out);m_l ist_i nfo.AddStri ng(temp); 一 一else /如果当前栈为空，且输入为右括号时，isError 为 1, 并更新控件信息。isError=1;CStri ng temp;temp.Format 　　10、(can not match %c -error!,str_in); m_l ist_info.AddStri ng(temp); 一 一mist_i nfo.RedrawWi ndow();UpdateData(FALSE);if (!ls.isEmpty()如果栈最后不为空，且栈中还有左括号，则提示栈中左括号没有匹配完成。char temp;ls.pop(temp);ls.push(temp);if (temp=(|temp=|temp=)CStri ng temp;temp=stack is not empty SetFocus();(CEdit*)GetDlgltem(IDC_EDIT 　　11、_INPUT)-SetSel(0,-1);void CKuohaopipeiDlg:O nButto nSlowShow()慢速显示运行过程/ TODO: Add your con trol no tificati on han dler code here/ TODO: Add extra validation heremist_i nfo.SetRedraw();m_l ist_stack.SetRedraw();UpdateData(TRUE);mist_i nfo.ResetC onten t();mist_stack.ResetC on te nt();BOOL isNum=0;BO 　　12、OL isError=0;int in putle ngth=m_cstri ng_in put.GetLe ngth();if (in putle ngth=0)MessageBox(输入值不能为空!,提示);elsefor(i nt j=0;j in putle ngth;j+)char str_ in=m_cstri ng_in put.GetAt(j); if (str_i n=(|str_i n=|str_i n=) isNum=1;Als.push(str_ in);/判断是否出现括号判断是否出现错误输入字串长度逐次字符II如果为左括弧， 则入栈。A-error!,str_ 　　13、CStri ng temp;temp.Format(push %c but can not match %c 将信息传入控件mist_i nfo.AddStri ng(temp);m_l ist_stack.DeleteStri ng(m_l ist_stack.GetCou nt()-1);m_l ist_i nfo.SetCurSel(m_l ist_i nfo.GetCou nt()-1);CStri ng temp;temp.Format(push %c into stack rn ”,str_i n);mist_i nfo.AddStri ng(temp);mist_i nfo.Se 　　14、tCurSel(mist_i nfo.GetCou nt()-1); temp.Format(%c,str_i n);m_list_stack.AddStri ng(temp);else if(str_i n=)|str_i n=T|str_i n=) isNum=1;char str_out;if (!ls.isEmpty()ls.pop(str_out);BOOL flag=0;if (str_i n=)&str_out=()flag=1;if (str_i n=&str_out=)flag=1;if (str_i n=&str_out=)flag=1;if (!f 　　15、lag)/如果为右括弧/pop 括号，判断是否匹配isError=1; /如果不匹配,则此变量为真,便于函数末尾判断。Aelse/如果匹配成功，将信息显示到控件。CStri ng temp;temp.Format(pop %c out of stack rn ”,str_out);m_l ist_i nfo.AddStri ng(temp);m_l ist_stack.DeleteStri ng(m_l ist_stack.GetCou nt()-1);m_l ist_i nfo.SetCurSel(mst_i nfo.GetCou nt()-1);else 如果栈中无括号了，且输入括号为右括 　　16、号。isError=1;CStri ng temp;temp.Format(ca n not match %c -error!,str_ in); mist_i nfo.AddString(temp);m_l ist_i nfo.SetCurSel(mi_l ist_i nfo.GetCou nt()-1);mist_i nfo.RedrawWi ndow();/ 重画控件mist_stack.RedrawWi ndow();Sleep(600);UpdateData(FALSE);if (!ls.isEmpty()如果栈中还有左括号， 说明右括号的数量小于左括号的数量。char temp;l 　　17、s.pop(temp);ls.push(temp);if (temp=(|temp=|temp=)CStri ng temp;temp=stack is n ot empty SetFocus();(CEdit*)GetDlgltem(IDC_EDIT_INPUT)-SetSel(0,-1);void CKuohaopipeiDlg:O nButto nClear()/ TODO: Add your con trol no tificati on han dler code here(CEdit*)GetDlgltem(IDC_EDIT_INPUT)-SetWi ndowText(”)；/ 此 　　18、函数中清空所有编辑框和 listbox 中的记录mist_i nfo.ResetC onten t();mist_stack.ResetC on te nt();mist_i nfo.RedrawWi ndow();/ 重画所有的控件mist_stack.RedrawWi ndow();void CKuohaopipeiDlg:O nSelcha ngeListl nfo()此函数响应列表框中光标改变的消息，定位错误的位置。/ TODO: Add your con trol no tificati on han dler code hereint i;i=mist_i nfo.GetCurSel();if(i!=LB_ERR&iSetFocus();(CEdit*)GetDlgltem(IDC_EDIT_INPUT)-SetSel(i,i+1);else(CEdit*)GetDlgltem(IDC_EDIT_INPUT)-SetFocus();(CEdit*)GetDlgltem(IDC_EDIT_INPUT)-SetSel(0,-1);(2 )运行截图图表 3 运行效果图 1图表 4 运行效果图 2何0TTWI【hhhhhhhhhh L L h hh h