括号的匹配 数据结构_数据结构实验之栈与队列四:括号匹配 测试数据 - CSDN
  • 给定一个字符串,其中的字符只包含三种括号:花括号{ }、中括号[ ]、圆...括号匹配要求括号必须以正确的顺序配对,如“{ [ ] ( ) }”或 “[ ( { } [ ] ) ]” 等为正确的格式,而“[ ( ] )”或“{ [ ( ) }”或“( { ...

           给定一个字符串,其中的字符只包含三种括号:花括号{ }、中括号[ ]、圆括号( ),即它仅由 “( ) [ ] { }” 这六个字符组成。设计算法,判断该字符串是否有效,即字符串中括号是否匹配。括号匹配要求括号必须以正确的顺序配对,如 “{ [ ] ( ) }” 或 “[ ( { } [ ] ) ]” 等为正确的格式,而 “[ ( ] )” 或 “{ [ ( ) }” 或 “( { } ] )” 均为不正确的格式。

    这个问题可以用栈stack来解决,具体的代码如下:

    #pragma once
    
    #include<stdio.h>
    #include<assert.h>
    #include<string.h>
    
    
    
    //typedef int DataType;
    typedef char DataType;
    
    
    
    #define MAX_SIZE 100
    
    typedef struct Stack
    {
    	DataType _arr[MAX_SIZE];
    	int _top;
    }Stack;
    
    void StackInit(Stack* s)
    {
    	assert(s);
    	s->_top = 0;
    }
    
    int StackEmpty(Stack* s)
    {
    	assert(s);
    	return 0 == s->_top;
    }
    
    void StackPush(Stack* s, DataType data)
    {
    	assert(s);
    	if (s->_top == MAX_SIZE)
    	{
    		printf("栈已经满了!\n");
    	}
    	s->_arr[s->_top] = data;
    	s->_top++;
    }
    void StackPop(Stack* s)
    {
    	assert(s);
    	if (StackEmpty(s))
    	{
    		printf("栈已经空了!\n");
    		return;
    	}
    	s->_top--;
    
    }
    DataType StackTop(Stack* s)
    {
    	assert(s);
    	return s->_arr[s->_top - 1];
    }
    int StackSize(Stack* s)
    {
    	assert(s);
    	return s->_top;
    }
    
    
    //
    void Test()
    {
    	Stack s;
    	StackInit(&s);
    
    	StackPush(&s, 1);
    	StackPush(&s, 2);
    	StackPush(&s, 3);
    	StackPush(&s, 4);
    	StackPush(&s, 5);
    	StackPush(&s, 6);
    
    	printf("size = %d\n", StackSize(&s));
    	printf("top = %d\n", StackTop(&s));
    
    
    	StackPop(&s);
    	printf("size = %d\n", StackSize(&s));
    	printf("top = %d\n", StackTop(&s));
    }
    
    
    
    ////括号匹配/////
    int isBracket(char ch)
    {
    	if (('(' == ch || ')' == ch) ||
    		('[' == ch || ']' == ch) ||
    		('{' == ch || '}' == ch))
    		return 1;
    	return 0;
    }
    int MatchBrackets(const char* pStr)
    {
    	int len = 0, i = 0;
    	Stack s;
    	if (NULL == pStr)
    	{
    		return 1;
    	}
    	StackInit(&s);
    	len = strlen(pStr);
    	for (; i < len; ++i)
    	{
    		if (isBracket(pStr[i]))
    		{
    			if ('(' == pStr[i] || '[' == pStr[i] || '{' == pStr[i])
    			{
    				StackPush(&s, pStr[i]);
    			}
    			else
    			{
    				if (StackEmpty(&s))
    				{
    					printf("右括号比左括号多!\n");
    					return 0;
    				}
    				else
    				{
    					//用当前的括号和栈顶元素匹配
    					char top = StackTop(&s);
    					if ('(' == top && ')' == pStr[i] ||
    						'[' == top && ']' == pStr[i] ||
    						'{' == top && '}' == pStr[i])
    				{
    					StackPop(&s);
    				}
    			
    					else
    					{
    						printf("左右括号次序匹配有误!\n");
    						return 0;
    					}
    
    				}
    			}
    		}
    	}
    	if (!-StackEmpty(&s))
    	{
    		printf("左括号比右括号多!\n");
    		return 0;
    	}
    
    	printf("括号匹配正确!!!\n");
    	return 1;
    }
    
    
    
    
    void TestMatchBrackets()
    {
    	char a[] = "(())abc{[(])}";
    	char b[] = "(()))abc{[]}";
    	char c[] = "(()()abc{[]}";
    	char d[] = "(())abc{[]()}";
    	char e[] = "{}";
    	MatchBrackets(a);
    	MatchBrackets(b);
    	MatchBrackets(c);
    	MatchBrackets(d);
    	MatchBrackets(e);
    
    
    }
    #include "Stack.h"
    int main()
    {
    	TestMatchBrackets();
    	system("pause");
    	return 0;
    }

    以上是用C语言对栈和括号匹配问题的简单实现,代码结果如下:

     

    展开全文
  • 利用栈的括号匹配算法 C语言数据结构 利用栈的括号匹配算法 C语言数据结构
  • 最近在学数据结构,所以发的大多数都是关于数据结构的题 括号匹配原来用动态规划做的一道题,现在老师要用栈来实现,用就用吧,还不让用函数,只能用链栈,不开森 很简单的思路,如果是’(’ ‘{’ ‘[’ 就入栈,...

    最近在学数据结构,所以发的大多数都是关于数据结构的题

    括号匹配原来用动态规划做的一道题,现在老师要用栈来实现,用就用吧,还不让用函数,只能用链栈,不开森

    很简单的思路,如果是’(’ ‘{’ ‘[’ 就入栈,如果是’)’ ‘}’ ‘]’,就看栈顶元素是否匹配,匹配就往下操作,如果表达式完了,栈不为空,不匹配;如果栈空了,表示匹配

    下面是代码的实现

    
    #include <stdio.h>
    #include <malloc.h>
    #include <stdlib.h>
    //用双结构体存储数据
    typedef struct node
    {
    	int data;
    	struct node* next;
    }node,*Pnode;
    typedef struct stack
    {
    	Pnode top;
    	Pnode base;
    
    }stack,*Pstack;
    //虽然用不了这么多函数,还是顺便实现了
    void init(Pstack);//初始化函数
    void push(Pstack S,int val);//入栈操作
    void printS(Pstack S);//打印栈
    int pop(Pstack S,int *p);//出栈操作
    int empty(Pstack S);//判空
    void clear(Pstack S);//清空
    int getLength(Pstack S);//取得栈的长度
     
    
    int main()
    {
    	stack s;
    	init(&s);
    	char ch[100],*p;
    	int e;
    	p = ch;
    	printf("输入一个含有()[]{}的括号表达式:\n");
    	gets(ch);
    	while(*p)
    	{
    		switch(*p)
    		{
    		case '{':
    		case '[':
    		case '(':
    			push(&s,*p++);//左括号就入栈
    			break;
    		case '}':
    		case ']':
    		case ')':
    			pop(&s,&e);	//右括号出栈
    			if((e=='{'&& *p=='}')||(e=='['&&*p==']')||(e=='('&&*p==')'))
    				p++;
    			else
    			{
    				printf("括号不匹配!\n");
    				exit(-1);
    			}
    			break;
    		default:	//其他字符就后移
    			p++;
    		}
    	}
    	
    	if(empty(&s))
    		printf("括号匹配成功");
    	else
    		printf("缺少右括号");
    	return 0;
    }
    
    void init(Pstack S)
    {
    	S->top = (Pnode)malloc(sizeof(node));
    	if(S->top== NULL)
    	{
    		printf("动态内存分配失败\n");
    		exit(-1);
    	}
    	else
    	{
    		S->base = S->top;
    		S->top->next = NULL;
    	}
    }
    
    int getLength(Pstack S)
    {
    	Pnode p = S->top;
    	int count = 0;
    	while(p!=S->base)
    	{
    		count++;
    		p = p->next;
    	}
    	return count;
    }
    
    void push(Pstack S,int val)
    {
    	Pnode New = (Pnode)malloc(sizeof(node));
    	New->data = val;
    	New->next = S->top;
    	S->top = New;
    }
    
    void printS(Pstack S)
    {
    	Pnode p = S->top;
    	if(p == NULL)
    	{
    		printf("错误\n");
    		exit(-1);
    	}
    	while(p->next!=NULL)
    	{
    		printf("%d",p->data);
    		p = p->next;
    	}
    	printf("\n");
    }
    
    int empty(Pstack S)
    {
    	if(S->top == S->base)
    		return 1;
    	else
    		return 0;
    }
    
    int pop(Pstack S,int *val)
    {
    	if(empty(S))
    	{
    		return 0;
    	}
    	else
    	{
    		Pnode q = S->top;
    		*val = q->data;
    		S->top = q->next;
    		free(q);
    		return 1;
    	}
    }
     
    void clear(Pstack S)
    {
    	if(empty(S))
    	{
    		return;
    	}
    	else
    	{
    		Pnode p = S->top;
    		Pnode q = NULL;
    		while(p!= S->base)
    		{
    			q = p->next;
    			free(p);
    			p = q;
    		}
    		S->top = S->base;
    	}
    }
    
    

    下面是代码的实现结果
    在这里插入图片描述

    展开全文
  • 问题: 输入一个带有 '(' 、')'的字符串,编写程序判断左右括号个数是否匹配。 输入:(4+3)*5/((34+2)-64) 思路: | 若有左括号压入栈中 输入字符串--->遍历各字符---> | ...

    问题:

    输入一个带有 '(' 、')'的字符串,编写程序判断左右括号个数是否匹配。

    输入:(4+3)*5/((34+2)-64) 

    思路:

                                                       |  若有左括号压入栈中

    输入字符串--->遍历各字符--->   |                                                                            --->判断栈是否为空--->空--->匹配

                                                       |  若有右括号进入判断--->栈为空--->括号不匹配                                --->不空--->不匹配

                                                                                          --->栈不空--->将栈顶弹出

     

    c++代码:

    #include<stack>
    #include<string>
    #include<iostream>
    
    using namespace std;
    bool matchParenthesis(const string& s)
    {
        stack<char> let;
        string::size_type len = s.length();
        for(string::size_type i=0;i<len;i++)
        {
            char a = s.at(i);
            if(a=='(')
                let.push(a);
            else if(a==')')
            {
                if(let.empty())
                {
                    cout<<"false"<<endl;
                    return false;
                }
                let.pop();
            }
        }
        if(let.empty())
        {
            cout<<"true"<<endl;
            return true;
        }   
        else
        {
            cout<<"false"<<endl;
            return false;
        }
    }
    int main(void)
    {
        string s;
        cout<<"please input string:";
        cin>>s;
        matchParenthesis(s);
    }

     

    展开全文
  • 数据结构——栈实现括号匹配 真正学习之后,才发现那些所谓的大婶不过是多用功了些。不知道以前为什么不亲自动手做做,原来这么简单。 #include #include #include #include /**栈的链式存储**/ typedef ...

    数据结构——栈实现括号匹配

    真正学习之后,才发现那些所谓的大婶不过是多用功了些。不知道以前为什么不亲自动手做做,原来这么简单。敲打
    #include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #include <string.h>
    /**栈的链式存储**/
    typedef struct Data{
    	char c;
    };
    typedef struct Stack{
    	Data data;
    	Stack *top;	//指向栈顶元素
    };
    /**初始化空栈**/
    void InitStack(Stack *S){
    	S->top = NULL;
    }
    /**判断是否为空栈**/
    int StackEmpty(Stack S){
    	//为空返回1否则返回0
    	if(S.top==NULL) return 1;
    	else return 0;
    }
    /**返回栈顶元素**/
    void GetTop(Stack S,Data *d){
    	if(StackEmpty(S)==1)
    		printf("It's an empty stack!");
    	else{
    		d->c = S.top->data.c;
    	}
    }
    /**向栈顶插入新元素 入栈**/
    void PushStack(Stack *S,Data d){
    	Stack* p = (Stack *)malloc(sizeof(Stack));
    	p->data.c = d.c;
    	p->top = S->top;
    	S->top = p;
    }
    /**从栈顶删除元素 出栈**/
    void PopStack(Stack *S,Data *d){
    	if(StackEmpty(*S)==1){
    		printf("It's an empty stack!\n");
    	}else{
    		Stack *p = S->top;
    		S->top = p->top;
    		d->c = p->data.c;
    	}
    }
    /**清空栈**/
    void ClearStack(Stack *S){
    	if(StackEmpty(*S)==1){
    		printf("It's already an empty stack!\n");
    	}else{
    		S->top = NULL;
    	}
    }
    /**打印栈内信息**/
    void PrintStack(Stack S){
    	if(StackEmpty(S)==1){
    		printf("It's an empty stack!\n");
    	}else{
    		printf("name----age\n");
    		while(S.top!=NULL){
    			printf("%s\n",S.top->data.c);
    			S.top = S.top->top;
    		}
    	}
    }
    /**检查右括号与栈顶元素是否匹配**/
    int Match(Data r,Data s){
    	//匹配成功返回1
    	if(r.c==')'&&s.c=='('){
    		return 1;
    	}else if(r.c=='}'&&s.c=='{'){
    		return 1;
    	}else if(r.c==']'&&s.c=='['){
    		return 1;
    	}else{
    		return 0;
    	}
    }
    /**括号匹配**/
    void CheckMatch(char *m,Stack *S){
    	Data r,s;
    	while(*m){
    		switch (*m){
    		case '(':
    		case '{':
    		case '[':
    			s.c = *m;
    			PushStack(S,s);
    			*m++;
    			break;
    		case ')':
    		case '}':
    		case ']':
    			if(StackEmpty(*S)){
    				printf("Location %s can't match!\n",*m);
    				return;
    			}
    			GetTop(*S,&s);
    			r.c = *m;
    			if(Match(r,s)){
    				PopStack(S,&s);
    				*m++;
    			}else{
    				printf("Location %c can't match!\n",*m);
    				return;
    			}
    		default:
    			*m++;
    		}
    	}
    	if(StackEmpty(*S)){
    		printf("Match successfully!\n");
    	}else{
    		printf("Can't match!Lack of right bracket!\n");
    	}
    }
    void main(){
    	char d[12];
    	Stack S;
    	char *p;
    	printf("Input your expression:");
    	gets(d);
    	p = d;	//指向表达式
    	InitStack(&S);
    	CheckMatch(p,&S);
    	system("pause");
    }
    展开全文
  • 假设一个括号表达式可以包含3种括号:(),{},[],它们可按任意次序嵌套,编写判断表达式中括号是否正确匹配的程序。若正确匹配输出yes,否则输出no。#include&lt;stdio.h&gt; #include&lt;string.h&...
  • 括号匹配的检验: eg: [([][][)]] 不匹配 [([][])] 匹配思路: 0x0.首先建立两个栈,并对其初始化 0x1.对表达式进行遍历,将相邻两个不能匹配的入栈到栈A,然后检测栈空间A是否为偶数,如果是表明有存在的可能,...
  • 数据结构实验之栈与队列四:括号匹配 Time Limit:1000 msMemory Limit:65536 KiB SubmitStatistic Problem Description 给你一串字符,不超过50个字符,可能包括括号、数字、字母、标点符号、空格,你的任务是...
  • 利用循环链表实现的括号匹配数据结构实验报告,适合新手,有程序运行截图
  • 题目描述: 思路: 代码实现 #ifndef STACK #define STACK typedef struct { char str[200]; int top; }*stack, Stack; #endif #define max 20 #include&lt;stdio.h&...#inc...
  • //头文件 #include <stdio.h> #include <stdlib.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define...
  • D - 数据结构实验之栈与队列四:括号匹配 数据结构实验之栈与队列四:括号匹配 Time Limit: 1000 ms Memory Limit: 65536 KiB Submit Statistic Problem Description  给你一串字符,不超过50个字符,...
  • #include #include #include #define STACK_INIT_SIZE 100 #define STACKINCREACE 10 typedef struct { char *base; char *top; int stacksize; }stack; int main() { // 初始化栈 void InitSt
  • 利用栈数据结构解决括号匹配问题 题目描述: 在文字处理软件或编译程序设计时,常常需要检查一个字符串或一个 表达式中的括号是否相匹配?利用数据结构的“栈”机制,设计算法并 编写程序,判断表达式中括号匹配问题...
  • 括号匹配算法在各种编程的IDE工具中都会用到,用来检测关于括号匹配的语法错误,括号匹配实际上不复杂,主要就是利用栈这个数据结构,扫描输入的字符串,若遇到左括号则直接入栈,若遇到右括号则弹出栈顶括号,看...
  • 数据结构_括号匹配

    2015-10-21 15:36:19
    数据结构_括号匹配
  • 【C++数据结构与算法】括号匹配算法这是从《c++数据结构与程序设计》这本书改过来的一个算法。 会用到c++内置的数据结构栈。要解决的问题:输入一行括号,判断这行括号是否匹配算法原理和代码思路一句话概括算法...
  • 括号匹配(C++数据结构) 描述:给出由()、{}、[]三种类型括号所组成的字符串,判断所给字符串中的括号能否全部匹配,若能匹配,则输出true!,否则输出false! 输入输出示例 输入 ({}) ([{]) 输出 true! ...
  • 问题描述:对一个字符串的左右括号进行匹配。 输入:一个字符串表达式 输出:匹配成功true或匹配失败false 例如:假设一个算术表达式中可以包含三种括号:圆括号“()”,方括号“[]”和花括号“{}”,且这三种...
  • 数据结构之---C语言实现括号匹配(栈实现)
1 2 3 4 5 ... 20
收藏数 81,940
精华内容 32,776
关键字:

括号的匹配 数据结构