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

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