• 给定一个字符串,其中的字符只包含三种括号:花括号{ }、中括号[ ]、圆...括号匹配要求括号必须以正确的顺序配对,如“{ [ ] ( ) }”或 “[ ( { } [ ] ) ]” 等为正确的格式,而“[ ( ] )”或“{ [ ( ) }”或“( { ...

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

    这个问题可以用栈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语言对栈和括号匹配问题的简单实现,代码结果如下:

     

    展开全文
  • 题目描述: 思路: 代码实现 #ifndef STACK #define STACK typedef struct { char str[200]; int top; }*stack, Stack; #endif #define max 20 #include&lt;stdio.h&...#inc...

    题目描述:
    这里写图片描述

    思路:


    这里写图片描述


    代码实现

    #ifndef STACK
    #define STACK
    
    typedef struct {
        char str[200];
        int top;
    }*stack, Stack;
    
    #endif
    
    #define max 20
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<stdbool.h>
    
    void init(stack s) {
        s->top = -1;
        memset(s->str, '\0', 200);
    }
    
    char pop(stack s) {
        if (s->top == -1) {
            return ' ';
        }
        char result = s->str[s->top--];
        return result;
    }
    
    char push(stack s, char ch) {
        if (s->top == max - 1) {
            return ' ';
        }
        s->str[++s->top] = ch;
        return ch;
    }
    
    int main(void)
    {
        char str[20];
        gets_s(str, 20);
    
        stack s = (stack)malloc(sizeof(Stack));
    
        init(s);
    
        for (int i = 0; i < strlen(str); i++) {
            if (str[i] == '(' || str[i] == '[') {
                push(s, str[i]);
            }
            else {
                if (str[i] == ')') {
                    if (s->str[s->top] == '(') {
                        pop(s);
                    }
                }
                else if (str[i] == ']') {
                    if (s->str[s->top] == '[') {
                        pop(s);
                    }
                }
            }
        }
    
        if (s->top == -1) {
            puts("匹配");
        }
        else {
            puts("不匹配");
        }
        return 0;
    }
    
    展开全文
  • 问题: 输入一个带有 '(' 、')'的字符串,编写程序判断左右括号个数是否匹配。 输入:(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);
    }

     

    展开全文
  • 括号匹配(C++数据结构) 描述:给出由()、{}、[]三种类型括号所组成的字符串,判断所给字符串中的括号能否全部匹配,若能匹配,则输出true!,否则输出false! 输入输出示例 输入 ({}) ([{]) 输出 true! ...

    括号匹配(C++数据结构)

    描述:给出由()、{}、[]三种类型括号所组成的字符串,判断所给字符串中的括号能否全部匹配,若能匹配,则输出true!,否则输出false!

    输入输出示例
    输入
    ({})
    ([{])

    输出
    true!
    false!

    此题需要用到栈(stack),为了便于简单,直接调用stack标准库,首先将所有的左括号,即(、{、[,压入栈中,然后按顺序和右括号进行匹配判断,只要有一个不能匹配成功,则匹配失败。

    下面是我的代码:

    #include<iostream>
    #include<string.h>
    #include<stack>//调用标准库
    using namespace std;
    int main()
    {
        char s[50];
        stack<char>st;//建立一个字符型栈
        while(cin>>s)
        {
            while(!st.empty())
            {st.pop();}
            int len=strlen(s),flag=1;
            for(int i=0;i<len;i++)
            {
                if(s[i]=='('||s[i]=='{'||s[i]=='[')
                    st.push(s[i]);//将左括号压入栈中
                else 
                {
                    if(st.empty())
                    {
                        flag=0;
                        break;  
                    }
                    char t=st.top();
                    st.pop();
                    if(s[i]==')'&&(t=='['||t=='{'))
                    {
                        flag=0;
                        break;
                    }
                    else if(s[i]=='}'&&(t=='('||t=='['))
                    {
                        flag=0;
                        break;
                    }
                    else if(s[i]==']'&&(t=='{'||t=='('))
                    {
                        flag=0;
                        break;
                    }
                }
            }
            if(!st.empty())
            flag=0;
            if(flag==1)
            cout<<"true!"<<endl;
            else
            cout<<"false!"<<endl;
        }
        return 0;
    } 
    展开全文
  • 最近在学数据结构,所以发的大多数都是关于数据结构的题 括号匹配原来用动态规划做的一道题,现在老师要用栈来实现,用就用吧,还不让用函数,只能用链栈,不开森 很简单的思路,如果是’(’ ‘{’ ‘[’ 就入栈,...

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

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

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

    下面是代码的实现

    
    #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;
    	}
    }
    
    

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

    展开全文
  • 数据结构之---C语言实现括号匹配(栈实现)
  • 假设一个括号表达式可以包含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个字符,可能包括括号、数字、字母、标点符号、空格,你的任务是...
  • 利用循环链表实现的括号匹配数据结构实验报告,适合新手,有程序运行截图
  • #include #define MAXSIZE 100 typedef int selemtype; ...typedef struct { //顺序栈的存储结构 selemtype *base; selemtype *top; int stacksize; }SqStack; void InitStack(SqStack
  • //头文件 #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
  • 利用栈数据结构解决括号匹配问题 题目描述: 在文字处理软件或编译程序设计时,常常需要检查一个字符串或一个 表达式中的括号是否相匹配?利用数据结构的“栈”机制,设计算法并 编写程序,判断表达式中括号匹配问题...
  • 数据结构_括号匹配

    2015-10-21 15:36:19
    数据结构_括号匹配
  • 问题描述:对一个字符串的左右括号进行匹配。 输入:一个字符串表达式 输出:匹配成功true或匹配失败false 例如:假设一个算术表达式中可以包含三种括号:圆括号“()”,方括号“[]”和花括号“{}”,且这三种...
  • 数据结构——栈实现括号匹配 真正学习之后,才发现那些所谓的大婶不过是多用功了些。不知道以前为什么不亲自动手做做,原来这么简单。 #include #include #include #include /**栈的链式存储**/ typedef ...
  • 【C++数据结构与算法】括号匹配算法这是从《c++数据结构与程序设计》这本书改过来的一个算法。 会用到c++内置的数据结构栈。要解决的问题:输入一行括号,判断这行括号是否匹配算法原理和代码思路一句话概括算法...
  • 1.在编写代码的时候,经常会用到两种括号:圆括号 “()” 和大括号 “{}” 。不管使用哪种括号,程序编译没有问题的其中一个重要因素就是所使用的括号是否能够...编写程序判断括号匹配问题的时候,使用栈结构会很容...
1 2 3 4 5 ... 20
收藏数 80,559
精华内容 32,223