精华内容
下载资源
问答
  • 利用栈数据结构解决括号匹配问题 题目描述: 在文字处理软件或编译程序设计时,常常需要检查一个字符串或一个 表达式中的括号是否相匹配?利用数据结构的“”机制,设计算法并 编写程序,判断表达式中括号匹配问题...

    利用栈数据结构解决括号匹配问题
    题目描述:
    在文字处理软件或编译程序设计时,常常需要检查一个字符串或一个
    表达式中的括号是否相匹配?利用数据结构的“栈”机制,设计算法并
    编写程序,判断表达式中括号匹配问题。(了解“栈” 的定义)
    题目描述:输入算术表达式 A,以#键结束。其中包括:整数、四则运
    算符,和六种括号“(”, “)”, “[”, “]” , “{”, “}”,请你利
    用数据结构的“栈”机制设计算法并编写程序,检查算术表达式 A 的
    括号是否匹配,如果匹配输出“括号匹配成功”,否则输出“括号匹配
    失败”。
    样例 1: 8*(3+3)/5*[9-3]+9#
    输出:括号匹配成功
    样例 2: 8*(9-6)/5*[3+3*{9-5}]#
    输出:括号匹配成功
    样例 2: 8*(9-6)/5][3+3{9-5}#
    输出:括号匹配失败

    源程序编码如下:
    #include
    #include
    using namespace std;

    int main()
    {string s;
    int n=0;
    while ( cin>>s[n]&&s[n]!= ‘#’)
    {
    n++;
    }

    stack<char> brackets;
    int i=0;
    for(i=0;i<s.length();i++)
     {      if(s[i]=='('||s[i]=='['||s[i]=='{')
               brackets.push(s[i]);
            if(s[i]==')')
            {if(brackets.empty()){
                    cout<<"NO!"<<endl;
                return 0;}
                if(brackets.top()=='(')
            brackets.pop();
                else {cout<<"NO!"<<endl;
                return 0;}
            }
            if(s[i]==']')
            {if(brackets.empty()){
                    cout<<"NO!"<<endl;
                return 0;}
                if(brackets.top()=='[')
            brackets.pop();
                else {cout<<"NO!"<<endl;
                return 0;}
            }
            if(s[i]=='}')
            {if(brackets.empty()){
                    cout<<"NO!"<<endl;
                return 0;}
                if(brackets.top()=='{')
            brackets.pop();
                else {cout<<"NO!"<<endl;
                return 0;}
            }
    }
    if(!brackets.empty()) cout<<"NO!"<<endl;
    else cout<<"Yes!"<<endl;
    return 0;
    

    }

    使用说明:
    输入任意算术表达式,检验其中的括号是否匹配,中括号套在大括号外面也算正确。#之后的表达式不再检查。

    重点:
    1.了解栈的用法;
    定义栈:
    #include
    stack a;
    出栈 a.pop()
    入栈 a.push()
    返回栈顶元素 a.top()
    返回栈是否为空 a.empty()

    展开全文
  • 算法数据结构面试分享 符号匹配问题今天在帖子上看见有同学在问,如果一个字符串中包含大括号和小括号,我们该如何解决括号匹配问题。我们今天就一起看下这道题吧。按照我们之前的套路,按部就班来:1. 确保我们理解...

    算法数据结构面试分享 符号匹配问题

    今天在帖子上看见有同学在问,如果一个字符串中包含大括号和小括号,我们该如何解决括号匹配问题。我们今天就一起看下这道题吧。按照我们之前的套路,按部就班来:

    1. 确保我们理解了问题,并且尝试一个例子,确认理解无误。

    举个例子,这样的括号是匹配的, ()、{}、({}), ({()}(){}), 而类似于{(、{,({)都是不匹配的。

    2. 想想你可以用什么方法解决问题,你会选择哪一种,为什么?

    我们拿这个字符串为例,({()}(){}), 最后一个)匹配的是第一个(, 倒数一个}匹配的是倒数第三个。所以我们可以从尾往头扫描,第一个)我们先记录下来,第一个}我们记录下来,第三个{我们发现它和}是匹配的,消除掉,第四个是),我们保存下来,第五个是(,我们发现和第四个匹配,消除掉,依次类推,到最后一个(,我们发现它还最开始的第一个匹配。所以我们自然想到了栈,不匹配我们就入栈,匹配我们就出栈。

    3. 解释你的算法和实现的方法

    我们申明两个栈,首先将所有字符依次入栈,再逐个出栈,出栈时,我们看下辅助栈里的第一个字符是否匹配,若匹配我们出栈,否则入栈。当主栈里所有字符都出栈时,我们检查辅助栈是否为空。空表示完全匹配,否则不匹配。

    4. 写代码的时候,记住,一定要解释你现在在干什么

    我们先来定义一个栈,一般我们会借助于数组,这里我们就简单的用列表来处理了,实现它的Pop, Push, IsEmpty 方法,看代码:

    public class Mystack

    {

    private List list = new List();

    public Mystack()

    { }

    public Mystack(T[] input)

    {

    if (input != null)

    {

    for (int index = 0; index < input.Length; index++)

    {

    list.Add(input[index]);

    }

    }

    }

    public T Pop()

    {

    if (!this.IsEmpty())

    {

    T element = list[list.Count-1];

    list.RemoveAt(list.Count-1);

    return element;

    }

    throw new IndexOutOfRangeException("The stack is empty already.");

    }

    public void Push(T element)

    {

    list.Add(element);

    }

    public bool IsEmpty()

    {

    return this.list.Count == 0;

    }

    }

    接下来,我们看算法:

    public static bool IsMatch(string input)

    {

    if (!string.IsNullOrEmpty(input))

    {

    Mystack stack = new Mystack(input.ToArray());

    Mystack secondStack = new Mystack();

    while (!stack.IsEmpty())

    {

    char current = stack.Pop();

    if (secondStack.IsEmpty())

    {

    secondStack.Push(current);

    }

    else

    {

    char target = secondStack.Pop();

    if (!IsClosed(current, target))

    {

    secondStack.Push(target);

    secondStack.Push(current);

    }

    }

    }

    return secondStack.IsEmpty();

    }

    return false;

    }

    这中间使用了一个IsClosed方法,我们用来匹配 ( 和 ), { 和 }, 看代码:

    private static bool IsClosed(char first, char second)

    {

    if (first == '(') return second == ')';

    if (first == '{') return second == '}';

    return false;

    }

    最后我们一起来测试这个方法:

    static void Main(string[] args)

    {

    string input = "({(){}})";

    var result = IsMatch(input);

    Console.WriteLine(result);

    }

    欢迎大家关注我的公众号,还有我的专题系列:

    大家有什么更好的解法,也欢迎讨论哈。

    展开全文
  • 主要介绍了基于PHP实现栈数据结构括号匹配算法,结合实例形式分析了php数组操作实现栈数据结构的进栈、出栈,以及基于括号匹配应用技巧,需要的朋友可以参考下
  • 数据结构栈-括号匹配

    2015-11-20 17:08:40
    该源码在VS2010上,正确编译、运行,无任何错误和警告。
  • 数据结构作业 实现 括号匹配 问题

    数据结构作业  栈  实现 括号匹配 问题

    毕竟太菜 照着demo敲了几天才 搞定。

    栈的几个基本应用函数顺便敲了  其他的就不详说了.

    见代码:

    #include <stdio.h>
    #include <stdlib.h>
    
    #define OK      1
    #define ERROR   0
    #define TRUE    1
    #define FALSE   0
    #define OVERFLOW -1
    #define STACK_INIT_SIZE 100
    #define STACKINCREMENT 10
    #define BUFFERSIZE 200
    
    typedef int Status; //函数返回状态
    typedef char SElemType;  //栈元素类型
    typedef struct{//栈结构定义
        SElemType *base;
        SElemType *top;
        int stacksize;
    }SqStack;
    
    Status InitStack(SqStack *S)
    {
        //构造一个空栈S
        S->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
        if(!S->base)//分配失败
        {
            printf("分配内存失败.\n");
            return 0;
        }
        S->top=S->base;
        S->stacksize=STACK_INIT_SIZE;
        return OK;
    }
    
    Status DestroyStack(SqStack *S)
    {
        //销毁栈S,S不再存在
        if(!S)//S为空
        {
            printf("指针为空,释放失败.\n");
            exit(0);
        }
        free(S);
        return OK;
    }
    
    Status ClearStack(SqStack *S)
    {
        //把栈S置为空栈
        if(!S)//S不存在
            return FALSE;
        S->top=S->base;//直接将栈顶指针指向栈底
        return OK;
    }
    
    Status StackEmpty(SqStack S)
    {
        //若栈S为空栈,则返回TRUE,否则返回FALSE
        if(S.top==S.base)
            return TRUE;
        else
            return FALSE;
    }
    
    int StackLength(SqStack S)
    {
        //返回S元素的个数,即栈的长度
        return S.stacksize;
    }
    
    Status GetTop(SqStack S,SElemType *e)
    {
        //若栈不为空,则用e返回S的栈顶元素,并返回OK;否则返回FALSE
        if(S.top==S.base)
        {
            return FALSE;
        }
        else
        {
            *e=*(S.top-1);
            return OK;
        }
    }
    
    Status Push(SqStack *S,SElemType e)
    {
        //插入元素e为新的栈顶元素
        if(S->top-S->base>=S->stacksize)//栈已满,追加存储空间
        {
            S->base=(SElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(SElemType));
            if(!S->base)
            {
                printf("重新申请空间失败.\n");
                exit(0);
            }
            S->top=S->base+S->stacksize;//更改栈顶指针
            S->stacksize+=STACKINCREMENT;
        }
        *S->top++=e;
        return OK;
    }
    
    Status Pop(SqStack *S,SElemType *e)
    {
        //若栈S不为空,则删除S的栈顶元素,用e返回其值,并返回OK,否则返回ERROR
        if(S->top==S->base)//栈为空
        {
            printf("栈为空.\n");
            return ERROR;
        }
        *e=*(--S->top);
        return OK;
    }
    
    Status StackTraverse(const SqStack *S){
        //从栈底到栈顶依次对每个元素进行访问
        SElemType *p=S->base;
        if(S->base==S->top)
        {
            printf("栈为空.\n");
            return FALSE;
        }
        while(p!=S->top)
        {
            printf("%c",*p++);
        }
        printf("\n");
        return OK;
    }
    
    Status BracketMatch(SqStack *S,const char *string){
        //输入字符串string中的括号匹配,返回TRUE;否则返回FALSE
        const char *p=string;
        SElemType e;
        InitStack(S);
        while(*p!='\0')//遍历字符串
        {
            switch(*p)//判断p的值
            {
                case '('://左括号,入栈
                case '[':
                case '{':
                    Push(S,*p);
                    break;
                case ')':
                    if(FALSE==GetTop(*S,&e))
                        return FALSE;
                    if(e=='(')
                    {
                        if(ERROR==Pop(S,&e))
                            return FALSE;
                    }
                    else
                        return FALSE;
                    break;
                case ']':
                    if(FALSE==GetTop(*S,&e))
                        return FALSE;
                    if(e=='[')
                    {
                        if(ERROR==Pop(S,&e))
                            return FALSE;
                    }
                    else
                        return FALSE;
                    break;
                case '}':
                    if(FALSE==GetTop(*S,&e))
                        return FALSE;
                    if(e=='{')
                    {
                        if(ERROR==Pop(S,&e))
                            return FALSE;
                    }
                    else
                        return FALSE;
                    break;
                default:  ;
            }
            p++;
        }
        if(!StackEmpty(*S)) //字符串遍历完,栈非空,不匹配
            return FALSE;
        return TRUE;
    }
    
    
    int main()
    {
        char *String;
        SqStack stack;
        String=(char*)malloc(sizeof(char)*BUFFERSIZE);
        if(!String)
        {
            printf("分配内存失败.\n");
            return 0;
        }
        while(1)
        {
            printf("请输入一行含括号的表达式(输入\"!\"退出):");
            gets(String);
            if(String[0]=='!')//退出
                break;
            if(TRUE==BracketMatch(&stack,String))
            {
                printf("\n能正确匹配.\n\n");
            }
            else
            {
                printf("\n不能正确匹配.\n\n");
            }
        }
        return 0;
    }
    


    展开全文
  • 运用的知识当输入的字符串扫瞄时遇到左括号就进栈,右括号就弹。最后查看括号是否匹配
  • 数据结构括号匹配问题

    万次阅读 多人点赞 2018-06-11 17:07:10
    给定一个字符串,其中的字符只包含三种括号:花括号{ }、中括号[ ]、圆...括号匹配要求括号必须以正确的顺序配对,如“{ [ ] ( ) }”或 “[ ( { } [ ] ) ]” 等为正确的格式,而“[ ( ] )”或“{ [ ( ) }”或“( { ...

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

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

     

    展开全文
  • 数据结构中利用实现括号匹配 本资源有两个文件 main.cpp Stack.h
  • 利用完成括号匹配问题 从一个文本中读取文件 然后在程序中进行括号的匹配
  • 问题描述 任意给定一个字符串,字符串中包含除了空格、...如果字符串中的括号匹配,则输出数字 1,并且在下一行输出{}、[]、()相对应的匹配个数,否则输出数字 0。 示例 输入: &()dgn*[{%}12] 输出: 1 ...
  • C语言--数据结构 实现括号匹配问题

    千次阅读 多人点赞 2020-03-26 16:36:06
    基本特点:“后进先出”,好比子弹上膛,最后放入弹夹中的子弹最先被射出,正因为有此特性,可以解决许多实际问题,例如即将讨论的括号匹配问题。 多说不易,来张图唤醒一下。 子弹上膛示意图 的特性类似于...
  • 问题引入;表达式中每一个左括号都会和一个右括号相匹配,不然就会报错; 当读一串表达式例如(a+b)*c+(d-p) 利用存储特点(先进后出,这里更... 若空则括号匹配 #include<iostream> using namespace std;
  • 数据结构括号匹配问题

    千次阅读 2017-08-02 23:39:22
    数据结构实验之四:括号匹配 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Description  给你一串字符,不超过50个字符,可能包括括号、数字、字母、标点符号、空格,你的任务是检查...
  • 心希盼 c++ 数据结构 的应用 括号匹配 说明在“心希盼 括号匹配.doc”中
  • 数据结构——实现括号匹配

    千次阅读 多人点赞 2017-04-21 18:13:38
    数据结构——实现括号匹配 真正学习之后,才发现那些所谓的大婶不过是多用功了些。不知道以前为什么不亲自动手做做,原来这么简单。 #include #include #include #include /**的链式存储**/ typedef ...
  • 数据结构的应用-括号匹配 实验要求: 括号匹配检验:假设表达式中允许包括两种括号:圆括号和方括号,其嵌套的顺序随意,即()或[([][])]等为正确的格式,[(])或([())等均为不正确格式。输入一个表达式,...
  • // 括号匹配问题 InitStack ( &S) : 的初始化 DestoryStack(&S) : 销毁S Push ( &S, e) :进栈 Pop (&S ) : 出栈 GetTop (S ): 取栈顶元素 IsEmpty (S): 判空否 ***/ #include #include #define STACK_MAX 1
  • 数据结构栈应用系列】括号匹配

    万次阅读 2016-03-26 16:59:10
    括号匹配算法在各种编程的IDE工具中都会用到,用来检测关于括号匹配的语法错误,括号匹配实际上不复杂,主要就是利用这个数据结构,扫描输入的字符串,若遇到左括号则直接入栈,若遇到右括号则弹出栈顶括号,看...
  • 数据结构括号匹配问题 要求大、中、小括号两两匹配,基本思路可以通过来实现。这里我使用的是简单的静态顺序,大小固定,同时定义了栈顶指针top。程序包含了的几个最基本的操作,初始化、判空、压入、弹出,...
  • 数据结构实验 的应用 多括号匹配问题 包含实验代码以及步骤等内容
  • 利用括号匹配算法 C语言数据结构 利用括号匹配算法 C语言数据结构
  • 括号匹配问题C语言实现
  • 利用顺序解决括号匹配问题(c++)-- 数据结构
  • 数据结构括号匹配问题

    千次阅读 2016-09-29 20:24:12
    输入一个表达式,表达式中包括三种括号“()”、“[]”和“{}”,判断该表达式的括号是否匹配。 没达到输出那个括号出错的目的,不过也能判断是否正确了。 #include #include #include #define STACK_INIT_...
  • 数据结构_括号匹配

    2015-10-21 13:50:49
    数据结构_括号匹配
  • 所以可以用数据结构中的顺序来解决这个问题 。在此我就以小括号匹配为例来说明。在匹配检查时,我们建立一个空的顺序。我们从左到右依次的进行检查,当遇到的是左括号'('时,就让其进栈。当遇到')'时在将其...
  • 的应用括号匹配问题:原理:代码实现: 括号匹配问题: 原理: 1、括号匹配成功的情况:为空 2、括号匹配失败的情况:  a、下一个为右括号但是和栈顶左括号不匹配  b、下一个是右括号但以空  c、所有的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 28,932
精华内容 11,572
关键字:

数据结构栈括号匹配问题

数据结构 订阅