括号匹配检验数据结构_数据结构实验之栈与队列四:括号匹配 测试数据 - CSDN
  • //本程序用于学习数据结构中的顺序栈 //调试环境 C-Free 5.0 #include #include #define MAXSIZE 100 typedef struct { int *base; //栈底指针 int *top; //栈顶指针 int stacksize; }SqStack; void InitS
    //本程序用于学习数据结构中的顺序栈
    //调试环境 C-Free 5.0 
    #include<stdio.h>
    #include<malloc.h>
    #define MAXSIZE 100
    typedef struct
    {
    	int *base;  //栈底指针 
    	int *top;   //栈顶指针 
    	int stacksize;
    }SqStack;
    
    void InitStack(SqStack*s)
    {
    	s->base = (int *)malloc(MAXSIZE*sizeof(int));//分配内存空间  100*sizeof(int) 
    	if (!s->base)    
    	{
    		return;   //栈空(分配失败) 
    	}
    	s->top = s->base;     
    	s->stacksize = MAXSIZE; 
    }
    void push(SqStack *s, char x)  //元素进栈 
    {
    	if (s->top-s->base==s->stacksize)   //栈满 
    	{
    		return;
    	}
    	*s->top++ = x;  
    }
    char GetTop(SqStack *s)   //取栈栈顶元素 
    {
    	if (s->top != s->base)
    	{
    		return*(s->top-1);      
    	}
    
    }
    char pop(SqStack *s)    //元素出栈 
    {
    	if (s->top == s->base)
    	{
    		return' '; 
    	}
    	char e;
    	e = *--s->top;
    	return e;
    }
    int Maching()
    {
    	SqStack ss;     //声明一个结构体 
    	SqStack *s = &ss;  //指向结构体的指针 
    	InitStack(s);   //初始化栈 
    	int flag = 1;
    	printf("请输入符号");
    	char ch = getchar();
    	while (ch != '#'&&flag)
    	{
    		switch(ch)
    		{
    			//char aa;
    			//char bb;
    			case '[':
    			case '(':
    					push(s, ch);  //压入栈 
    					break;
    				case ')':
    				    //aa=GetTop(s);
    					if (!(s->top == s->base) && GetTop(s) == '(')
    					{
    						pop(s);  //出栈 
    					}
    					else
    					{
    						flag = 0;
    					}
    					break;
    				case ']':
    				    //bb=GetTop(s);
    					if (!(s->top == s->base) &&GetTop(s) == '[')
    					{
    						pop(s);  //出栈 
    
    					}
    					else
    					{
    						flag = 0;
    					}
    					break;
    		}
    		ch = getchar();	
    	}
    	if (s->top == s->base)
    		{
    			return 1;                    
    		}
    		else
    		{
    			return 0;
    		}
    }
    
    void main()
    {
    	int n; 
    	n=Maching();
    	if(n)
    	{
    		printf("匹配成功\n"); 
    	}
    	else
    	{
    		printf("匹配失败\n");
    	}
    }
    
    

    展开全文
  • 检验算法借助一个栈,每当读入一个左括号,则直接入栈,等待相匹配的同类右括号;每当读入一个右括号,若与当前栈顶的左括号类型相同,则二者匹配,将栈顶的左括号出栈,直到表达式扫描完毕在处理过程中,还要考虑...

    1.案例分析

    • 检验算法借助一个栈,每当读入一个左括号,则直接入栈,等待相匹配的同类右括号;每当读入一个右括号,若与当前栈顶的左括号类型相同,则二者匹配,将栈顶的左括号出栈,直到表达式扫描完毕在处理过程中,还要考虑括号不匹配出错的情况。

    2.算法步骤

    • ①初始化一个空栈S
    • ②设置一标记性变flag,用来标记匹配结果以控制循环及返回结果,1表示正确匹配,0表示错误匹配,fag初值为1。
      ③扫描表达式,依次读入字符ch,如果表达式没有扫描完毕或flag非零,则循环执行以下操作:
      • 若ch是左括号“[”或“(",则将其压入栈;
      • 若ch是右括号“)”,则根据当前栈顶元素的值分情况考虑:若栈非空且栈顶元素是“(”,则正确匹配,否则错误匹配,fag置为0;
      • 若ch是右括号“]”,则根据当前栈顶元素的值分情况考虑:若栈非空且栈顶元素是"[",则正确匹配,否则错误匹配,flag置为0。
    • ④退出循环后,如果栈空且fag值为1,则匹配成功,返回true,否则返回false

    3.算法描述

    bool Matching() 
    {
    	stack<char> s;  // 定义一个stack容器
    	char ch, temp;
    	int flag = 1;     // 标记匹配结果以控制循环及返回结果
    	
    	cin >> ch; //读入第一个字符
    
    	while (ch != '#' && flag) //假设表达式以“#”结尾
    	{
    		switch (ch)
    		{
    			case '[':
    			case '(':      // 若是左括号,则将其压入栈
    				s.push(ch);
    			break;
    		
    			case ')':  //若是“)”,则根据当前栈顶元素的值分情况考虑
    				if (!s.empty() && s.top() == '(')  // 若栈非空且栈顶元素是“(”,则正确匹配
    				{
    					temp = s.top();
    					s.pop();
    				}		                           
    				else
    					flag = 0;    // 若栈空或栈顶元素不是“(”,则错误失败
    			break;
    		
    			case ']': //若是“]”,则根据当前栈顶元素的值分情况考虑
    				if (!s.empty() && s.top() == '[') // 若栈非空且栈顶元素是“[”,则正确匹配
    				{
    					temp = s.top();
    					s.pop();
    				}		                          
    				else
    					flag = 0;         //若栈空或栈顶元素不是“[”,则错误匹配
    			break;
    		} //switch
    		cin >> ch; //继续读入下一个字符
    	} //while
    	if (s.empty() && flag)
    		return true;         // 匹配成功
    	else
    		return false;      // 匹配失败
    }

    4.代码实现

    • main.cpp
    #include <iostream>
    #include <cstdlib>
    #include <stack>
    
    using namespace std;
    
    bool Matching() 
    {
    	stack<char> s;  // 定义一个stack容器
    	char ch, temp;
    	int flag = 1;     // 标记匹配结果以控制循环及返回结果
    	
    	cin >> ch; //读入第一个字符
    
    	while (ch != '#' && flag) //假设表达式以“#”结尾
    	{
    		switch (ch)
    		{
    			case '[':
    			case '(':      // 若是左括号,则将其压入栈
    				s.push(ch);
    			break;
    		
    			case ')':  //若是“)”,则根据当前栈顶元素的值分情况考虑
    				if (!s.empty() && s.top() == '(')  // 若栈非空且栈顶元素是“(”,则正确匹配
    				{
    					temp = s.top();
    					s.pop();
    				}		                           
    				else
    					flag = 0;    // 若栈空或栈顶元素不是“(”,则错误失败
    			break;
    		
    			case ']': //若是“]”,则根据当前栈顶元素的值分情况考虑
    				if (!s.empty() && s.top() == '[') // 若栈非空且栈顶元素是“[”,则正确匹配
    				{
    					temp = s.top();
    					s.pop();
    				}		                          
    				else
    					flag = 0;         //若栈空或栈顶元素不是“[”,则错误匹配
    			break;
    		} //switch
    		cin >> ch; //继续读入下一个字符
    	} //while
    	if (s.empty() && flag)
    		return true;         // 匹配成功
    	else
    		return false;      // 匹配失败
    }
    
    int main() 
    {
    	
    	cout << "请输入待匹配的表达式,以“#”结束:" << endl;
    	//int flag = (int)Matching();
    	if (Matching())
    		cout << "括号匹配成功!" << endl;
    	else
    		cout << "括号匹配失败!" << endl;
    	
    	system("pause");
    
    	return 0;
    }

    Leetcode 20题代码

    class Solution {
    public:
    	bool isValid(string s)
    	{
    		stack<char> S;  // 定义一个stack容器
    		char temp;
    		int flag = 1;
    		int i = 0;// 标记匹配结果以控制循环及返回结果 
    
    		while (s[i] != '\0'&& flag)
    		{
    			switch (s[i])
    			{
    			case '[':
    			case '(':
    			case '{':          // 若是左括号,则将其压入栈
    				S.push(s[i]);
    				break;
    
    			case ')':  //若是“)”,则根据当前栈顶元素的值分情况考虑
    				if (!S.empty() && S.top() == '(')  // 若栈非空且栈顶元素是“(”,则正确匹配
    				{
    					temp = S.top();
    					S.pop();
    				}
    				else
    					flag = 0;    // 若栈空或栈顶元素不是“(”,则错误失败
    				break;
    
    			case ']': //若是“]”,则根据当前栈顶元素的值分情况考虑
    				if (!S.empty() && S.top() == '[') // 若栈非空且栈顶元素是“[”,则正确匹配
    				{
    					temp = S.top();
    					S.pop();
    				}
    				else
    					flag = 0;         //若栈空或栈顶元素不是“[”,则错误匹配
    				break;
    
    			case '}': //若是“]”,则根据当前栈顶元素的值分情况考虑
    				if (!S.empty() && S.top() == '{') // 若栈非空且栈顶元素是“{”,则正确匹配
    				{
    					temp = S.top();
    					S.pop();
    				}
    				else
    					flag = 0;         //若栈空或栈顶元素不是“[”,则错误匹配
    				break;
    
    			} //switch
    			i++;
    		} //while
    		if (S.empty() && flag)
    			return true;         // 匹配成功
    		else
    			return false;      // 匹配失败
    	}
    };
    • 运行结果

    展开全文
  • 利用循环链表实现的括号匹配数据结构实验报告,适合新手,有程序运行截图
  • 数据结构》严蔚敏版习题3.2.2,括号匹配问题。是顺序栈的课后习题。原问题:假设表达式中允许包括两种括号:圆括号和方括号,其嵌套方式随意,即(【】())等都是正确的格式,【(】)是不正确的格式。设计一个...

    《数据结构》严蔚敏版习题3.2.2,括号匹配问题。是顺序栈的课后习题。原问题:假设表达式中允许包括两种括号:圆括号和方括号,其嵌套方式随意,即(【】())等都是正确的格式,【(】)是不正确的格式。设计一个算法检查输入的字符串中的括号是否是匹配的。
    /-------------------------------------------------------------/
    思路:使用栈来解决,遇到(、【就入栈,遇到)、】且刚还能和栈顶元素匹配是就出栈,遇到其他元素不做处理。字符转中所有的元素都处理完后,查看栈的长度,若为空栈说明括号匹配,栈非空则说明括号不匹配。
    所以需要一个可以存储字符元素的栈,以及匹配的各种方法:

    #include<stdio.h>
    #include<stdlib.h>
    #define INITSIZE 100
    #define INCRSIZE 10
    #define ERROR 0
    #define OK 1
    
    typedef int Status;
    typedef struct {
    	char *base;
    	char *top;
    	int size;
    }SqStack;
    
    Status InitStack(SqStack *s){
    	s->base=(char *)malloc(INITSIZE*sizeof(char));
    	if(!s->base){
    		return ERROR;
    	}
    	s->top=s->base;
    	s->size=INITSIZE;
    	return OK;
    }
    
    Status DestroyStack(SqStack *s){
    	if(!s->base){
    		exit(1);
    	}
    	free(s->base);
    	s->base=NULL;
    }
    
    Status ClearStack(SqStack *s){
    	s->top=s->base;
    }
    
    Status StackEmpty(SqStack *s){
    	if(s->top==s->base){
    		return 1;
    	}else{
    		return 0;
    	}
    }
    
    int StackLength(SqStack *s){
    	return (s->top-s->base);
    }
    
    Status GetTop(SqStack s,char *e){
    	if(s.top==s.base){
    		return ERROR;
    	}
    	*e=*(s.top-1);
    	return OK;
    }
    
    Status Push(SqStack *s,char e){
    	if(s->top-s->base>=s->size){
    		s->base=(char *)realloc(s->base,(s->size+INCRSIZE)*sizeof(char));
    		if(!s->base){
    			exit(1);
    		}
    		s->top=s->base+s->size;
    		s->size+=INCRSIZE;
    	}
    	*(s->top)=e;
    	s->top++;
    	return OK;
    }
    
    Status Pop(SqStack *s,char *e){
    	if(s->top==s->base){
    		return ERROR;
    	}
    	*e=*(--s->top);
    	return OK;
    }
    
    void StackTraverse(SqStack *s){
    	if(!s->base){
    		exit(1); 
    	}
    	char *t=s->top-1;
    	while(t>=s->base){
    		printf("%c",*t);
    		t--;
    	}
    }
    

    保存为stack.h的头文件:
    然后是设计主函数的算法:
    先画出算法流程图:
    算法流程图
    实现代码:

    #include<stdio.h>
    #include<stdlib.h>
    #include"stack.h"
    
    int main(){
    	SqStack s,*sp=&s;
    	InitStack(sp);
    	char str[20];
    	scanf("%s",str);
    	if(str[0]==']'||str[0]==')'){
    		printf("括号不匹配\n");
    		exit(1);
    	}
    	char c,d,*cp=&c,*dp=&d;
    	for(int i=0,c=str[0];c!='\0';i++){
    		c=str[i];
    		if(!StackEmpty(sp)){
    			GetTop(s,dp);
    		}
    		char t,*tp=&t;
    		switch(c){
    			case '[':Push(sp,c);break;
    			case '(':Push(sp,c);break;
    			case ']':if(d=='['){
    				Pop(sp,tp);
    			}else{
    				Push(sp,c);
    				//printf("括号不匹配\n");
    			}
    			break;
    			case ')':if(d=='('){
    				Pop(sp,tp);
    			}else{
    				Push(sp,c);
    				//printf("括号不匹配\n");
    			}
    			break;
    			default:break;
    		}
    	}
    	printf("当前栈长:%d\n",StackLength(sp));
    	if(StackEmpty(sp)){
    		printf("括号匹配\n");
    	}else{
    		printf("括号不匹配\n");
    	}
    	return 0;
    }
    

    运行实验:

    (x+y)+[z-t*(8*7)]
    当前栈长:0
    括号匹配
    
    --------------------------------
    Process exited after 49.2 seconds with return value 0
    请按任意键继续. . .
    /-------------------------------/
    
    
    (])
    当前栈长:3
    括号不匹配
    
    --------------------------------
    Process exited after 10.03 seconds with return value 0
    请按任意键继续. . .
    

    代码运行正确。

    展开全文
  • 8、数据结构笔记之八栈的应用之括号匹配检验实现  “人生的意义就在这个过程上。你要细细体认和玩味这个过程中的每节,无论它是一节黄金或一节铁;你要认识每节的充分价值。”  1. 括号匹配问题 括号匹配问题...

    8、数据结构笔记之八栈的应用之括号匹配检验实现

               “人生的意义就在这个过程上。你要细细体认和玩味这个过程中的每节,无论它是一节黄金或一节铁;你要认识每节的充分价值。” 

    1.  括号匹配问题

    括号匹配问题是指要匹配一个字符串的左,右括号:括号问题可以用来解决C语言中的“{”和“}”的匹配问题,可以观察到,如果从左至右扫描一个字符串,那么每个右括号将于最近遇到的那个未匹配的左括号相匹配,在从左至右的扫描工程中把所遇到的左括号存放到堆栈内,每当遇到一个右括号时,就将它与栈顶的左括号(如果存在)相匹配,同时从栈顶删除该左括号。

               在编译器中适用很多,此外括号匹配问题和栈的特性非常吻合。

    2.  结构定义

    定义栈的最大空间为100,可以存放100个左右括号

    #defineStackSize100   //假定预分配的栈空间最多为100个元素

    #defineMaxLength100   //最大的字符串长度

    typedefintDataType;   //假定栈元素的数据类型为整数

    typedefstruct

    {

        DataTypedata[StackSize];

        inttop;

    }SeqStack;

    其中结构体中定义了一个数组,一个整型。数组模拟堆栈,整型表示堆的TOP指针。

    3.  初始化堆

    设置top为-1,因为数组是从0开始的。

    void Initial(SeqStack *S)

    {

        S-> top = -1;

    }

     

    4.  判断栈是否空满

    通过结构体中的top来判断是否为空为满

    //判断栈是否空

    int IsEmpty(SeqStack *S)

    {

        returnS-> top == -1;

    }

     

    //判断栈是否满

    int IsFull(SeqStack *S)

    {

        returnS-> top == StackSize -1;

    }

     

    5.  进栈出栈

    进栈判断是否为满,出栈判断是否为空。

    进栈将top值加1,出栈将top 值减1.

    //进栈

    void Push(SeqStack *S, DataTypex)

    {

        if(IsFull(S))

        {

           printf("栈上溢!");

           exit(1);

        }

     

        S-> data[++ S -> top] = x;

     

        return;

    }

     

    //出栈

    DataType Pop(SeqStack *S)

    {

        if(IsEmpty(S))

        {

           printf("栈为空!");

            return-1;

        }

     

        returnS-> data[S -> top--];

    }

     

    6.  括号匹配

    出现(,则压入栈,出现)则出栈,同时判断弹出的top值是否为-1. 如果为1,说明)括号多了,弹不出(括号了。最后判断栈是否为空,如果不为空,则说明有多余的(符号。

    //括号匹配

    void PrintMatchedPairs(char *expr)

    {

        SeqStackS;

        int i, j , length = strlen(expr);

     

       Initial(&S);

     

        for(i= 1 ; i <= length ; i++)

        {

            if(expr[i- 1] == '(')

            {

               Push(&S,i);

            }

            elseif(expr[i- 1] == ')')

            {

                j= Pop(&S);

                if(j== -1)

                {

                   printf("没有对应第%d个右括号的左括号\n", i);

                }

                else

                {

                   printf("%d %d\n",i,j);

                }

            }

        }

     

        while(!IsEmpty(&S))

        {

            j =Pop(&S);

           printf("没有对应第%d个左括号的右括号\n", j);

        }

    }

     

     

    7.  源码

    #include"stdio.h"

    #include"string.h"

    #include"stdlib.h"

     

     

    #defineStackSize100   //假定预分配的栈空间最多为100个元素

    #defineMaxLength100   //最大的字符串长度

     

    typedefintDataType;   //假定栈元素的数据类型为整数

    typedefstruct

    {

        DataTypedata[StackSize];

        inttop;

    }SeqStack;

     

    //置栈空

    void Initial(SeqStack *S)

    {

        S-> top = -1;

    }

     

    //判断栈是否空

    int IsEmpty(SeqStack *S)

    {

        returnS-> top == -1;

    }

     

    //判断栈是否满

    int IsFull(SeqStack *S)

    {

        returnS-> top == StackSize -1;

    }

     

    //进栈

    void Push(SeqStack *S, DataTypex)

    {

        if(IsFull(S))

        {

           printf("栈上溢!");

           exit(1);

        }

     

        S-> data[++ S -> top] = x;

     

        return;

    }

     

    //出栈

    DataType Pop(SeqStack *S)

    {

        if(IsEmpty(S))

        {

           printf("栈为空!");

            return-1;

        }

     

        returnS-> data[S -> top--];

    }

     

    //取栈顶元素

    DataType Top(SeqStack *S)

    {

        if(IsEmpty(S))

        {

           printf("栈为空!\n");

           exit(1);

        }

     

        returnS-> data[S -> top];

    }

     

    //括号匹配

    void PrintMatchedPairs(char *expr)

    {

        SeqStackS;

        int i, j , length = strlen(expr);

     

       Initial(&S);

     

        for(i= 1 ; i <= length ; i++)

        {

            if(expr[i- 1] == '(')

            {

               Push(&S,i);

            }

            elseif(expr[i- 1] == ')')

            {

                j= Pop(&S);

                if(j== -1)

                {

                   printf("没有对应第%d个右括号的左括号\n", i);

                }

                else

                {

                   printf("%d %d\n",i,j);

                }

            }

        }

     

        while(!IsEmpty(&S))

        {

            j =Pop(&S);

           printf("没有对应第%d个左括号的右括号\n", j);

        }

    }

     

    void main(void)

    {

        charexpr[MaxLength];

        printf("输入符号个数小于%d的表达式:\n",MaxLength);

     

       gets(expr);

     

        printf("括号匹配:\n");

     

       PrintMatchedPairs(expr);

     

        return;

    }

     

     

     

     

     


    展开全文
  • 在这里 我 只说下 简单的思路 把下面的 字符存下来   ( ) [ ]  ( =  )  [ =  ] 只要 满足 上面的 字符 '=' 就出栈 如果不是 就进栈  ...最后判断 栈 是否为空 就行了
  • 数据结构之---C语言实现括号匹配(栈实现)
  • 括号匹配检验: eg: [([][][)]] 不匹配 [([][])] 匹配思路: 0x0.首先建立两个栈,并对其初始化 0x1.对表达式进行遍历,将相邻两个不能匹配的入栈到栈A,然后检测栈空间A是否为偶数,如果是表明有存在的可能,...
  • 遇到左括号入栈 遇到右符号 从栈中弹出栈顶符号,比配 匹配成功,继续扫描 匹配失败,停止,报错 结束: 所有字符扫描完毕,栈为空:成功 匹配失败或扫描完毕,但是栈不为空:失败 代码 // // Created by xuehu...
  • 与栈顶元素利用ascii码值来进行比较,如果匹配则将栈中压入的元素弹出,否则继续匹配下一个。当输入结束符“#”时,若栈为空,则匹配成功,否则,匹配失败 核心代码: int match(char p,char q) void parenthesis_...
  • #include<stdlib.h> #include<stdio.h> #define MAXSIZE 100 struct Stack { char* base; char* top; int size; }; void InitStack(Stack* S) ...base = (char*)malloc(sizeof(char)*MAXSIZ...
  • 利用栈数据结构解决括号匹配问题 题目描述: 在文字处理软件或编译程序设计时,常常需要检查一个字符串或一个 表达式中的括号是否相匹配?利用数据结构的“栈”机制,设计算法并 编写程序,判断表达式中括号匹配问题...
  • 数据结构--用栈实现括号匹配检验目录括号匹配要求程序思路代码实现商务合作及建议 目录 括号匹配要求 假设表达式中允许包含三种括号:{大括号}、[中括号]和(小括号),其嵌套的顺序随意,即{()}、[{([][])}]、({}[]...
  • SCAU 8586 括号匹配检验

    2020-04-14 20:12:50
    8586 括号匹配检验 时间限制:1000MS 代码长度限制:10KB 提交次数:4447 通过次数:1864 题型: 编程题 语言: G++;GCC Description 利用栈编写满足下列要求的括号匹配检验程序:假设表达式中允许包含两种括号:圆括号和...
  • 括号匹配检验来自于严薇敏数据结构3.2节的3.2.2留下的的习题实现代码如下:ps:存在的问题:当每次给getchar值之后,会打印两次"请输入:" 如果您在看这篇文章 碰巧知道我的问题所在之处,还请不吝指教...
  • 任意输入一个由若干个圆括号、方括号和花括号组成字符串,设计一个算法判断该串中的括号是否配对。
  • 接下来是n行由括号构成的字符串,包含‘(’、‘)’、‘[’、‘]’。 输出 对每一测试用例,用一行输出结果,如果匹配,输出“YES”,否则输出“NO” 样例输入 2 [([][]())] )[]() ...
  • ◆3.19④ 假设一个算术表达式中可以包含三种括号:圆括号"(" 和")",方括号"["和"]"和花括号"{"和"}",且这三种括号可按任意的次序嵌套使用(如:…[…{…}…[…]…]…[…]…(…)…)。编写判别给定表达式中所含括号...
  • 这篇文章讲述的是数据结构部分的括号匹配算法的java实现,如有错误或者不当之处,还望各位大神批评指正。 问题描述 假设一个表达式中允许包含两种括号圆括号()和方括号[],其嵌套的顺序随意,及()等正确格式,[(]...
  • 数据结构作业 栈 实现 括号匹配 问题
1 2 3 4 5 ... 20
收藏数 14,234
精华内容 5,693
关键字:

括号匹配检验数据结构