精华内容
下载资源
问答
  • 括号匹配的检验

    2018-01-13 23:09:33
    通过数据结构的知识进行括号匹配的检验代码简单易懂
  • 数据结构与算法(括号匹配的检验括号匹配的检验一、题目二、代码实现三、实例运行总结 括号匹配的检验 一、题目 问题描述: 假设表达式中允许有两种括号:圆括号和方括号,其嵌套的顺序随意,即(()[ ])或...


    括号匹配的检验

    一、题目

    • 问题描述:

    假设表达式中允许有两种括号:圆括号和方括号,其嵌套的顺序随意,即(()[ ])或[([ ] [ ])]等为正确格式,[( ])或(((]均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如:考虑下列的括号序列:
    [ ( [ ] [ ] ) ]
    1 2 3 4 5 6 7 8
    当计算机接受了第1个括号以后,他期待着与其匹配的第8个括号的出现,然而等来的却是第2个括号,此时第1个括号“[”只能暂时靠边,而迫切等待与第2个括号相匹配的 第7个括号“)”的出现,类似的,因只等来了第3个括号“[”,此时,其期待的紧迫程度较第2个括号更紧迫,则第2个括号只能靠边,让位于第3个括号,显然第3个括号的期待紧迫程度高于第2个括号,而第2个括号的期待紧迫程度高于第1个括号;在接受了第4个括号之后,第3个括号的期待得到了满足,消解之后,第2个括号的期待匹配就成了最急迫的任务了,…… ,依次类推。可见这个处理过程正好和栈的特点相吻合。

    • 基本要求:
      读入圆括号和方括号的任意序列,输出“匹配”或“此串括号匹配不合法”。

    • 测试数据:
      输入([ ]()),结果“匹配”
      输入 [( )],结果“此串括号匹配不合法”

    • 实现提示:
      设置一个栈,每读入一个括号,若是左括号,则作为一个新的更急迫的期待压入栈中;若是右括号,并且与当前栈顶的左括号相匹配,则将当前栈顶的左括号退出,继续读下一个括号,如果读入的右括号与当前栈顶的左括号不匹配,则属于不合法的情况。在初始和结束时,栈应该是空的。

    • 选作内容
      考虑增加大括号的情况。

    二、代码实现

    代码如下(示例):

    #include "iostream"
    #include "stdlib.h"
    #include "string.h"
    #define MAXSIZE 100
    #define ERROR 0
    #define OK 1
    using namespace std;
    
    typedef int Status;
    typedef struct{
    	char *base;
    	char *top;
    	int stacksize;
    }SqStack;
    Status InitStack(SqStack &S){ //初始化一个顺序栈 
    	S.base = new char[MAXSIZE];
    	if(!S.base) exit(ERROR);
    	S.top = S.base;
    	S.stacksize = MAXSIZE;
    	return OK; 
    }
    Status Push(SqStack &S,char e){ //入栈函数 
    	if(S.top - S.base == S.stacksize) return ERROR;
    	*S.top++ = e;
    	return OK;
    }
    Status Pop(SqStack &S,char &e){ //出栈函数 
    	if(S.top == S.base) return ERROR;
    	e = *--S.top;
    	return OK;
    }
    char GetTop(SqStack S){ //取栈顶元素 
    	if(S.top != S.base) return *(S.top - 1); 
    }
    Status StackEmpty(SqStack S){ //判断顺序栈是否为空 
        if(S.base==S.top){
            return true;
        }
        return false;
    }
    int main(){
    	SqStack S;
    	char str[20],e,c;
    	int t;
    	InitStack(S);
    	cout<<"输入要检验的式子:"; 
    	cin>>str;//输入要检验的式子 
    	t = strlen(str);//得出式子字符串长度(后面循环用) 
    	if(str[0] == ')' || str[0] == ']' || str[0] == '}'){
    		cout<<"此串括号匹配不合法"<<endl; 
    	} //判断第一个字符;(特殊,需要单独判断) 
    	for(int i=1;str[i] !='\0';i++){//判断除第一个字符外的所有字符 
    		e = str[i]; 
    		c = GetTop(S); //取栈顶元素 
    		switch(e){// 选择函数来进行判断,后续操作 
    			case '(':Push(S,e); break;
    			case '[':Push(S,e); break;
    			case '{':Push(S,e); break;
    			case ')':if(c == '(') Pop(S,e);
    			else cout<<"此串括号匹配不合法"<<endl; 
    			break;
    			case ']':if(c == '[') Pop(S,e);
    			else cout<<"此串括号匹配不合法"<<endl; 
    			break;
    			case '}':if(c == '{') Pop(S,e);
    			else cout<<"此串括号匹配不合法"<<endl; 
    			break;
    			default:break; 
    		}
    		if((i+1 == strlen(str)) && StackEmpty(S)) cout<<"此串括号匹配"<<endl;
    		//给匹配结果写条件。 
    	}
    	return 0;
    }
    

    三、实例运行

    输入:()
    结果:
    样例运行
    输入:(2+3)
    结果:
    样例运行
    输入:((]
    结果:
    样理运行

    总结

    这道题,利用了顺序栈来进行解决。将“( [ { ) } ]”等符号通过switch函数选择的方法来进行是否入栈,取栈顶元素的比较,出栈等等…的限定条件来进行结果判断。
    其实利用for函数if函数也能进行实现但是通过最优的解法和代码复杂程度,选择了switch函数。

    展开全文
  • XDOJ 307 括号匹配的检验

    千次阅读 2020-12-16 15:26:27
    XDOJ 307 括号匹配的检验 ***喜欢请点个赞,代码人会超开心的!!!***???????????? 问题描述 假设一个表达式或一段程序中含有三种括号:圆括号“(”和“)”、方括号“[”和“]”、花括号“{”和“}”。试写一个...

    XDOJ 307 括号匹配的检验

    ***喜欢请点个赞,代码人会超开心的!!!***😊🦄🎈

    问题描述

    假设一个表达式或一段程序中含有三种括号:圆括号“(”和“)”、方括号“[”和“]”、花括号“{”和“}”。试写一个程序判别给定的表达式或程序中所含括号是否正确配对出现。

    输入说明

    每行为一个含有括号的表达式或一段程序。

    输出说明

    输出一个right或wrong,表明正确匹配与否。

    输入样例

    while (m<(a[8]+t) {m=m+1; t=t-1;}

    输出样例

    wrong

    解决思路

    • 用栈来解决
    • 遇到左括号入栈,遇到右括号则与栈顶元素相比较看是否匹配,如果不匹配说明可能出现了(({)这种情况,则直接判错flag=0,退出循环;如果匹配则出栈,检验下一个元素。
    • 如果flag=1且栈为空(top=-1)则说明正确配对,输出right

    完整代码

    #include<stdio.h>
    #include<string.h>
    int main()
    {
    	char str[100],stack[100],top;
    	top=-1;//top=-1表示栈为空,入栈top加一然后入栈,出栈top-1
    	gets(str);
        int i,len,flag=1;
    	len=strlen(str);//字符串的长度
    	for(i=0;i<len;i++)
    	{
    		if(str[i]=='('||str[i]=='{'||str[i]=='[')//左括号入栈
    		{
    			top++;
    			stack[top]=str[i];
    		}
    		if(str[i]==')')
    		{
    			if(stack[top]=='(')//右括号匹配
    			 top--;
    			else//右括号不匹配
    			{
    				flag=0;break;
    			}
    		}
    		if(str[i]=='}')
    		{
    			if(stack[top]=='{')
    			 top--;
    			else
    			{
    				flag=0;break;
    			}
    		}
    		if(str[i]==']')
    		{
    			if(stack[top]=='[')
    			 top--;
    			else
    			{
    				flag=0;break;
    			}
    		}	
    	}
    	if(flag==1&&top==-1)//左右括号都匹配且栈空
    		printf("right");
    	else
    		printf("wrong");
    	return 0;
    }
    
    展开全文
  • 利用栈编写满足下列要求的括号匹配检验程序:假设表达式中允许包含两种括号:圆括号和方括号,其嵌套 顺序随意,即([]())或[([][])]等为正确格式,[(]或([())或(()])均为不正确格式。输入一个包含上 述括号...

    栈的实际应用很多,其中括号匹配是很常见的例子。下面列出基本算法和源代码,标明注释以便日后复习和翻阅。

    Description:

    利用栈编写满足下列要求的括号匹配检验程序:假设表达式中允许包含两种括号:圆括号和方括号,其嵌套的

    顺序随意,即([]())或[([][])]等为正确的格式,[(]或([())或(()])均为不正确的格式。输入一个包含上

    述括号的表达式,检验括号是否配对。本题给出部分check()函数,要求将check()函数补充完整,并完成

    整个程序。

    算法:

        

     

    代码:

     1 void check()
     2  { // 对于输入的任意一个字符串,检验括号是否配对
     3    SqStack s;
     4    SElemType ch[80],*p,e;
     5    if(InitStack(s)) // 初始化栈成功
     6    {
     7      scanf("%s",ch);
     8      p=ch;
     9      while(*p) // 没到串尾
    10        switch(*p)
    11   {
    12      case '(':
    13      case '[':Push(s,*p);
    14                 p++;
    15                   break; // 左括号入栈,且p++,读下一个字符
    16      case ')':
    17      case ']':if(!StackEmpty(s)) // 栈不空,如果为空的话返回0;!0=1
    18                   {
    19                    Pop(s,e); // 弹出栈顶元素
    20                     if(*p==')'&&e!='('||*p==']'&&e!='[')
    21                                                 // 弹出的栈顶元素与*p不配对
    22 {
    23                       printf("isn't matched pairs\n");
    24                       exit(ERROR);
    25                     }
    26                     else
    27                     {
    28                       p++;//读取下一个字符
    29                       break; // 跳出switch语句
    30                     }
    31                   }
    32                   else // 栈空
    33                   {
    34                     printf("lack of left parenthesis\n");
    35                     exit(ERROR);
    36                   }
    37          default: p++; // 其它字符不处理,指针向后移
    38        }
    39      if(StackEmpty(s)) // 字符串结束时栈空
    40        printf("matching\n");
    41      else
    42        printf("lack of right parenthesis\n");
    43    }
    44  }

     

    转载于:https://www.cnblogs.com/LizG192/p/5334638.html

    展开全文
  • 括号匹配检验

    2011-12-29 02:55:13
    数据结构里练习,括号匹配检验c代码实现
  • 利用顺序栈实现括号匹配的检验

    千次阅读 2020-03-20 17:48:51
    利用顺序栈实现括号匹配的检验(严蔚敏版《数据结构》第49页3.2.2) 思路 我的思路是直接入栈和检验同时进行,即:如果两个相近的括号的差值符合要求([ ] 的差值为 2、( ) 的差值为 1),就将此时顺序栈的最上边...

    NOTICE: 本题代码是按照源码顺序贴上的,复制可直接运行

    环境: Visual Stdio Code

     

    题目

    利用顺序栈实现括号匹配的检验(严蔚敏版《数据结构》第49页3.2.2)

    思路

    我的思路是直接入栈和检验同时进行,即:如果两个相近的括号的差值符合要求([ ] 的差值为 2、( ) 的差值为 1),就将此时顺序栈的最上边两个元素出栈,如果 StackLength 为 0, 则证明所有元素均已出栈(即:匹配检验通过),返回成功提醒,否则必须输入‘#’才能停止程序。最后打印出当前的顺序栈(此时如果看到顺序栈不为空,就证明没有通过检验)。

    操作流程示意图:

    emmmm,小编觉得思路还是比较清晰的。

    源码

    初始化:

    #include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    
    #define STACK_INIT_SIZE 10 // 初始化分配量
    #define STACKINCREMENT 1  // 分配增量
    #define ERROR 0
    #define OK 1
    
    typedef int Status;
    typedef char SElemType;
    
    typedef struct
    {
        SElemType *base;  // 栈底指针
        SElemType *top;   // 栈顶元素
        int stacksize;
    }SqStack;
    
    Status InitStack(SqStack &S)
    {   // 初始化
        S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
        if(!S.base) return ERROR;
        S.top = S.base;
        S.stacksize = STACK_INIT_SIZE;
        return OK;
    }//InitStack

    销毁:

    Status DestroyStack(SqStack &S)
    {   // 销毁
        if(S.base)
        {
            delete S.base;  // C++ 中用来释放之前动态分配的内存
            S.stacksize = 0;
            S.base = S.top = NULL;
        }
        return OK;
    }//DestroyStack

    判断是否为空栈:

    Status StackEmpty(SqStack &S)
    {   // 判断是否为空栈
        if(S.top == S.base) return OK;
        else return ERROR;
    }//StackEmpty

    获取栈容量:

    Status StackLength(SqStack &S)
    {   // 获取栈容量
        return S.top - S.base;
    }//StackLength
    

    入栈:

    Status Push(SqStack &S, SElemType *e)
    {   // 入栈
        if(S.top - S.base == S.stacksize)
        {
            S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
            if(!S.base) return ERROR;
            S.top = S.base + S.stacksize;
            S.stacksize += STACKINCREMENT;
        }
        *S.top ++= *e;
        return OK;
    }//Push

    出栈:

    Status Pop(SqStack &S, SElemType *e)
    {   // 出栈
        if(S.top == S.base) return ERROR;
        *e = *--S.top;
        return OK;
    }//Pop

    打印栈:

    Status StackTraverse(SqStack &S)
    {   // 打印
        SElemType *p = (SElemType *)malloc(sizeof(SElemType));
        p = S.top;
        if(!p) return ERROR;
        else
        {
            p--;
            while(p >= S.base)
            {
                printf("%c ", *p);
                p--;
            }
        }
        return OK;
    }//StackTraverse

    获取栈顶元素:

    Status GetTop(SqStack &S, SElemType *e)
    {   // 若栈不空,用 e 返回 S 的栈顶元素,并返回 OK,否则返回 ERROR
        if(S.top == S.base) return ERROR;
        *e = *(S.top-1);
        return OK;
    }//GetTop

    检验:

    Status Judge(SqStack &S)
    {   // 括号匹配检验
        SElemType e, out;
        // 入栈、判断
        printf("\n请依次输入想要检验的括号(输入 # 结束):\n");    
        while(e != '#')    // 如果匹配不通过,必须手动输入 # 来结束程序
        {
            printf("\n请输入入栈元素:\n");
            scanf("%c", &e);
            getchar();
            if(e == '#') break;       // 我发现不写这行会出现一个问题,就是输入一个 # 不会退出
            if(StackLength(S) >= 0)     
            {
                int i = 0;
                GetTop(S, &out);       // 获取当前栈顶元素
                Push(S, &e);            // 入栈
                printf("\n栈顶元素与输入元素的差的绝对值为:%d\n",abs(out-e));   // 如上文分析所说,'[' - ']' = 2, '(' - ')' = 1
                if(abs(out-e) == 1 || abs(out-e) == 2)  // 如果括号匹配通过
                {
                    while(i != 2)         // 之所以出栈两次是因为,新的元素已经插入,此时栈顶两个元素是匹配成功的,删除的是这两个元素
                    {
                        Pop(S, &out);         
                        printf("\n出栈元素为:%c\n", out);
                        i ++;
                    }
                    if(StackEmpty(S))    // 顺序栈为空,跳出循环,提示通过
                    {
                        printf("\n检验通过!\n");
                        break;
                    }
                    continue;
                }
                printf("\n栈容量:%d\n", StackLength(S));     // 可以不要,我只是想直观地看一下栈当前容量
            }
        }
        printf("\n栈的当前容量为:%d\n", StackLength(S));       // 从这行往下都是最后返回栈元素的语句,目的是当匹配不通过时返回所有元素
        printf("\n------------------------------------\n");
        {   // 出栈,查看当前剩余元素
            printf("\n栈的元素为:\n");
            while(S.top != S.base)
            {
                Pop(S, &e);
                printf("%c ", e);
            }
        }
        return OK;
    }//Judge

    主函数:

    int main()
    {
        SqStack S;
        
        if(InitStack(S)) printf("\n初始化成功!\n");
        else exit(0);
        Judge(S);
        DestroyStack(S);      // 要养成用完即销毁的好习惯,虽然现在的计算机会自动销毁,但是养成这个好习惯还是没坏处的
        return OK;
    }

    运行结果示意图:

    我不晓得怎么截取长图.......

    THE END!

    展开全文
  • 括号匹配检验

    2018-05-14 20:29:45
    OJ作业题 8586 括号匹配检验,其实里面很多代码课本上都有
  • 1. 括号匹配的检验 假设表达式中含有3种括号:(),[],{},其嵌套的顺序随意。检验括号是否匹配。 基本思想:在算法中设置一个栈,每读入一个括号,若是右括号,则或者与栈顶匹配的左括号相互消解,或者是不合法的...
  • 17、括号匹配的检验(限2人完成)通过键盘输入一个表达式,其中包含圆括号和方括号(如:()[]),圆括号和方括号时成对出现,其中可以出现嵌套。嵌套形式如([]())或者[([][])]均为正确的格式,而[()或者([()]或者...
  • 栈的应用--括号匹配的检验(C++)

    千次阅读 2016-04-21 18:54:45
    括号匹配的检验。题目的意思是假定只有两种括号[]()要求我们检测一组由'('')'']''['组成的数据是否满足括号匹配 ---()()[][] YES ([])([]()) YES ]]]((])) NO解题思路:读取字符,如果是左括号则入栈,如果是有括号...
  • 数据结构--用栈实现括号匹配的检验目录括号匹配要求程序思路代码实现商务合作及建议 目录 括号匹配要求 假设表达式中允许包含三种括号:{大括号}、[中括号]和(小括号),其嵌套的顺序随意,即{()}、[{([][])}]、({}[]...
  • 遇到左括号入栈 遇到右符号 从栈中弹出栈顶符号,比配 匹配成功,继续扫描 匹配失败,停止,报错 结束: 所有字符扫描完毕,栈为空:成功 匹配失败或扫描完毕,但是栈不为空:失败 代码 // // Created by xuehu...
  • 8586 括号匹配检验

    2021-05-29 10:57:14
    Description 利用栈编写满足下列要求的括号匹配检验程序:假设表达式中允许包含两种括号:圆括号和方括号,其嵌套顺序随意,即()或[([][])]等为正确格式,[(]或([())或(()])均为不正确格式。输入一个包含上述...
  • 括号匹配的检验来自于严薇敏数据结构3.2节的3.2.2留下的的习题实现代码如下:ps:存在的问题:当每次给getchar值之后,会打印两次"请输入:" 如果您在看这篇文章 碰巧知道我的问题所在之处,还请不吝指教...
  • Description 利用栈编写满足下列要求的括号匹配检验程序:假设表达式中允许包含两种括号:圆括号和方括号,其嵌套顺序随意,即()或[([][])]等为正确格式,[(]或([())或(()])均为不正确格式。输入一个包含上述...
  • 这个应用来自于严蔚敏的《数据结构(C语言版)》,即这...在设计程序的时候,借助于栈,将每个元素遍历一遍,根据一定的条件来确定是出栈还是入栈,如果最后栈为空,则括号匹配的,否则不会匹配。实现的代码如下:
  • SCAU 8586 括号匹配检验

    2020-04-14 15:40:09
    Description 利用栈编写满足下列要求的括号匹配检验程序:假设表达式中允许包含两种括号:圆括号和方括号,其嵌套顺序随意,即()或[([][])]等为正确格式,[(]或([())或(()])均为不正确格式。输入一个包含上述...
  • 应用:括号匹配检验

    千次阅读 2018-04-23 11:39:03
    其嵌套顺序随意,即()或{{()[]}}等均为正确输入格式,检验输入表达式中的括号是否匹配。 源代码:BracketMatch.h#ifndef __BRACKETMATCH_H__ #define __BRACKETMATCH_H__#define MAXSIZE 100typedef char ...
  • ``` ```#include #include #define MI 100; #define MX 1000; typedef struct { int *base; int *top; int stacklist; }sqstack; int InitStack(sqstack *s) { s->base = (int *)malloc(MI *sizeof(int))...
  • 检验括号匹配的方法,就是对给定的字符串依次检验:若是左括号,入栈;若是右括号,出栈一个左括号判断是否与之相匹配;是其他字符,不检验检验到字符串尾,还要检查栈是否为空。只有栈空,整个字符串才匹配完。 ...
  • 1、把此段代码添加到“数据结构(严蔚敏)顺序栈” 就可以了2、把“数据结构(严蔚敏)顺序栈”定义SElemType改成下面 typedef char SElemType就可以了 void check() { /* 对于输入任意一个字符串,检验...
  • 括号匹配

    2019-07-11 21:07:05
    括号匹配括号匹配的检验问题分析功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建...
  • 行编辑程序、括号匹配检验

    千次阅读 2014-05-04 09:00:24
    行编辑程序、括号匹配检验程序都是利用数据结构。而这两个 小程序也非常好显示了栈先进后出思想。由于程序本身很简短、清晰,所 以也就不做多解释了,直接上代码了。 行编辑程序: #include #...
  • 可能出现的不匹配的情况: ①到来的有括号不是所“期待的” ②盗来的是“不速之客”; ③直到结束,也没有到来所“期待”的括号; 二、使用步骤 1.引入库 代码如下(示例): import numpy as np import pandas as ...
  • 与栈顶元素利用ascii码值来进行比较,如果匹配则将栈中压入元素弹出,否则继续匹配下一个。当输入结束符“#”时,若栈为空,则匹配成功,否则,匹配失败 核心代码: int match(char p,char q) void parenthesis_...

空空如也

空空如也

1 2 3 4 5
收藏数 86
精华内容 34
关键字:

括号匹配的检验的代码