精华内容
下载资源
问答
  • 顺序栈括号匹配问题

    2020-07-21 08:40:41
    使用顺序栈解决括号匹配问题 括号匹配问题:包括三种类型的括号()[]{}和其他字符,判断是否存在对应的左右括号 举例: [({a}s)]---满足条件 [({a}s)]---不满足条件 */ #include <iostream> using namespace ...
    /*
    使用顺序栈解决括号匹配问题
    括号匹配问题:包括三种类型的括号()[]{}和其他字符,判断是否存在对应的左右括号
    举例:
    [({a}s)]---满足条件
    [({a}s)]---不满足条件
    */
    #include <iostream>
    using namespace std;
    typedef char Elemtype;
    const int MAXSIZE = 100;
    struct SqStack{
    	Elemtype data[MAXSIZE];
    	int top;	//栈顶指针
    };
    void InitStack(SqStack &s){
    	s.top = -1;	//栈顶指针指向-1表示栈空
    }
    bool Push(SqStack &s, Elemtype e){
    	if(s.top==MAXSIZE-1){
    		cout << "栈满" << endl;
    		return false;
    	}
    	s.data[++s.top] = e;
    	return true;
    }
    bool StackEmpty(SqStack s){
    	if(s.top==-1)
    		return true;
    	return false;
    }
    bool Pop(SqStack &s, Elemtype &e){
    	if(s.top==-1){
    		cout << "栈空" << endl;
    		return false;
    	}
    	e = s.data[s.top--];
    	return true;
    }
    bool BasketMatch() {
    	Elemtype c, c1;
    	SqStack s;
    	InitStack(s);
    	while((c=getchar())!='\n'){	//换行退出
    		switch(c){
    			case '(':
    			case '[':
    			case '{':
    				Push(s, c);
    				break;
    			case ')':
    				if(StackEmpty(s)) return false;
    				Pop(s, c1);
    				if(c1!='(')
    					return false;
    				break;
    			case ']':
    				if(StackEmpty(s)) return false;
    				Pop(s, c1);
    				if(c1!='[')
    					return false;
    				break;
    			case '}':
    				if(StackEmpty(s)) return false;
    				Pop(s, c1);
    				if(c1!='{')
    					return false;
    				break;
    				
    		}
    	}
    	//处理右括号和左括号匹配,但是左括号比右括号多的情况。举例:({} 
    	if(StackEmpty(s))	
    		return true;
    	return false;
    }
    int main(){
    	if(BasketMatch()) 
    		cout << "输入括号匹配" <<endl;
    	else
    		cout << "输入括号不匹配" << endl; 
    	return 0;
    }
    

    程序小白,如果代码有任何问题,欢迎指出。

    展开全文
  • 使用顺序栈实现括号匹配
  • 顺序栈及其算法

    栈空时 S->top = -1
    添加第一个元素过程:
    S->data[s->top++] = value;

    #include <stdio.h>
    #include <stdlib.h>
    #define MAXLINE 100
    
    typedef struct
    {
        int data[MAXLINE];
        int top;
    }sql_stack;
    
    //顺序栈的初始化
    void init_sqlstack(sql_stack **s)
    {
          *s = (sql_stack *)malloc(sizeof(sql_stack));
         (*s)->top = -1;
    }
    
    //入栈
    void push_sqlstack(sql_stack *s,int value)
    {
         if(s->top == MAXLINE-1)
         {
            printf("stack is full\n");
            exit(1);
         }
         s->top++;
         s->data[s->top] = value;
    }
    
    //取栈顶
    void pop_sqlstack(sql_stack *s,int *value)
    {
        *value = s->data[s->top--];
        printf("%d ",*value);
    }
    
    int main(int argc,char **argv)
    {
         sql_stack *s = NULL;
         int i = 0;
         int value = 0;
    
         init_sqlstack(&s);
         for(i = 0;i < 5;++i)
         {
             push_sqlstack(s,rand()%10);
         }
    
         while(s->top != -1)
         {
             pop_sqlstack(s,&value);
         }
           printf("\n");
         return 0;
    }

    顺序栈的括号匹配算法:

    #include <stdio.h>
    #include <stdlib.h>
    #define MAXLINE 100
    
    typedef struct
    {
        char data[MAXLINE];
        int top;
    }sql_stack;
    
    //顺序栈的初始化
    void init_sqlstack(sql_stack **s)
    {
          *s = (sql_stack *)malloc(sizeof(sql_stack));
         (*s)->top = -1;
    }
    
    //入栈
    void push_sqlstack(sql_stack *s,char value)
    {
         if(s->top == MAXLINE-1)
         {
            printf("stack is full\n");
            exit(1);
         }
         s->top++;
         s->data[s->top] = value;
    }
    
    //取栈顶
    void pop_sqlstack(sql_stack *s,char *value)
    {
        if(s->top != -1)
        {
            *value = s->data[s->top--];
        //printf("%d ",*value);
        }
    }
    
    int main(int argc,char **argv)
    {
         sql_stack *s = NULL;
    
         init_sqlstack(&s);
         char rev[MAXLINE];
         char value;
         char *ch = rev;
         printf("输入表达式:\n");
         scanf("%s",rev);
         while(*ch != EOF){
             if(*ch =='(' || *ch == '{' || *ch =='['){
                 push_sqlstack(s,*ch);
                 //printf("%c",*ch);
             }
             if(*ch == ')')
             {
                pop_sqlstack(s,&value);
                //printf("%c",value);
                if(value != '('){
                   printf("括号不匹配\n");
                   return 1;
                }
             }
    
             if(*ch == ']')
             {
                pop_sqlstack(s,&value);
                //printf("%c",value);
                if(value != '['){
                   printf("括号不匹配\n");
                   return 1;
                }
             }
    
             if(*ch == '}')
             {
                pop_sqlstack(s,&value);
               // printf("%c",value);
                if(value != '{'){
                   printf("括号不匹配\n");
                   return 1;
                }
             }
    
             ch++;
         }
         printf("括号匹配成功\n");
         return 0;
    }
    展开全文
  • 顺序栈实现括号匹配

    千次阅读 2016-05-15 11:33:58
    //采用顺序栈编程实现:表达式的括号是否匹配问题。 //要求:输入带括号的表达式,判断其中括号是否配对。 //扩展功能:给出配对括号的位序和不配对括号的位序。#include #include #include #include #include ...
    //采用顺序栈编程实现:表达式的括号是否匹配问题。
    //要求:输入带括号的表达式,判断其中括号是否配对。
    //扩展功能:给出配对括号的位序和不配对括号的位序。
    
    #include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <algorithm>
    #define OVERFLOW -2
    #define STACK_INIT_SIZE 100
    #define STACKINCREMENT 10
    #define ERROR 0
    #define OK 1
    using namespace std;
    typedef struct
    {
        char c;
        int pos;
    } Brack,*Bracket;
    
    typedef struct
    {
        Bracket base;
        Bracket top;
        int stacksize;
    } SqStack;
    
    int InitStack(SqStack &S)
    {
        S.base=(Bracket)malloc(STACK_INIT_SIZE*sizeof(Brack));
        if(!S.base)
            return  ERROR;
        S.top=S.base;
        S.stacksize=STACK_INIT_SIZE;
        return OK;
    }
    
    Brack GetTop(SqStack S,Brack e)
    {
        if(S.top==S.base)
            exit(OVERFLOW);
        S.top--;
        e=*S.top;
        return e;
    }
    
    int Push(SqStack &S,Brack e)
    {
        if(S.top-S.base>=S.stacksize)
        {
            S.base=(Bracket)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(Brack));
            if(!S.base)
                exit(OVERFLOW);
            S.top=S.base+S.stacksize;
            S.stacksize+=STACKINCREMENT;
        }
        *S.top=e;
        S.top++;
        return OK;
    }
    
    int Pop(SqStack &S, Brack &e)
    {
        if(S.base==S.top)
            return ERROR;
        e=*(S.top-1);
        S.top--;
        return OK;
    }
    
    bool equal_e(char a,char b)
    {
        if(a=='('&&b==')')
            return true;
        else if(a=='{'&&b=='}')
            return true;
        else if(a=='['&&b==']')
            return true;
        else
            return false;
    }
    
    char ch[100];
    int match[100];
    int nomatch[100];
    int p=0,q=0;
    bool find_brack(SqStack S,char e)
    {
        int flag=0;
        while(S.base!=S.top)
        {
            S.top--;
            if(equal_e(S.top->c,e))
            {
                flag=1;
                match[p++]=S.top->pos;
                break;
            }
        }
        if(flag==1)
            return true;
        else
            return false;
    }
    void fun()
    {
        SqStack S;
        InitStack(S);
        Brack b;
        for(int i=0; i<strlen(ch); i++)
        {
            if(ch[i]=='{'||ch[i]=='('||ch[i]=='[')
            {
                b.c=ch[i];
                b.pos=i+1;
                Push(S,b);
            }
            //GetElem(S);
            if(ch[i]=='}'||ch[i]==')'||ch[i]==']')
            {
                if(find_brack(S,ch[i]))
                {
                    do
                    {
                        Pop(S,b);
                        if(equal_e(b.c,ch[i]))
                        {
                            break;
                        }
                        else
                        {
                            nomatch[q++]=b.pos;
                        }
                    }
                    while(true);
                }
                else
                {
                    nomatch[q++]=i+1;
                    //cout<<"fun"<<i+1<<endl;
                }
            }
        }
        while(S.base!=S.top)
        {
            Pop(S,b);
            nomatch[q++]=b.pos;
        }
        if(q!=0)
        {
            cout<<"括号匹配失败!"<<endl;
            if(p!=0)
            {
                cout<<"匹配成功的括号位序是:"<<endl;
                sort(match,match+p);
                for(int i=0; i<p; i++)
                {
                    cout<<match[i]<<" ";
                }
                cout<<endl;
    
            }
    
            cout<<"匹配不成功的括号位序是:"<<endl;
            sort(nomatch,nomatch+q);
            for(int i=0; i<q; i++)
            {
                cout<<nomatch[i]<<" ";
            }
            cout<<endl;
            cout<<"注:这里的位序是指括号在表达式中的位置顺序!"<<endl;
        }
        else
        {
            cout<<"表达式中的括号均是配对的。"<<endl;
        }
    }
    
    int main()
    {
        cin>>ch;
        fun();
        return 0;
    }
    
    展开全文
  • 利用顺序栈实现括号匹配的检验

    千次阅读 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!

    展开全文
  • 顺序栈的方法实现括号匹配的检查,例如输入( enter【enter{enter}enter】enter)enter,程序就会输出Match(匹配),注enter是回车。
  • 2018-11-11-14:28:31 1.顺序栈 下面是我用数组实现的顺序栈,包含的函数有出入栈,查看栈顶元素,栈的大小,栈是否空等函数,当栈空间不够用时,对应的数组会自动... 2 顺序栈实现括号匹配。 3 main函数操作:...
  • 顺序栈括号匹配

    2018-11-25 20:32:16
    bool matching(char exp[]) //括号匹配 { int state=1,i=0; char ch,e; ch=exp[i++]; seqstackS; while(ch!=’\0’&&state) { if(ch==’(’||ch==’[’)S.push(ch); else if(ch==’)’) if(!S.empty()&&S...
  • 利用顺序栈解决括号匹配问题(c++)-- 数据结构
  • 假设一个算术表达式中可以包含三种括号:园括号“(”和“)”、方括号“[”和“]”、花括号“{”和“}”,且这三种括号可按任意的次序嵌套使用。...要求:顺序栈存储;实现顺序栈的基本操作;调用基本操作完成。
  • C语言实现顺序栈括号匹配

    千次阅读 2015-07-08 21:48:46
    //顺序栈的使用举例:括号匹配 #include #include #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define BUFFERSIZE 256
  • 对于给定的一个表达式,其中一定会用到大量的左右括号,有小括号,中括号,甚至大括号。如何才能判断其中的括号是否是一一对应的。所以可以用数据结构中的顺序栈来解决这个...如果栈中是空的,则左右括号匹配 反之...
  • 括号匹配文件:Backets_match.c 1 #include 2 #include "Stack.h" 3 4 void brackets(char *expression) 5 { 6 SeqStack *S; 7 char ch1, ch2; 8 int pos = 1; 9 10 S = (SeqStack *)malloc...
  • 顺序栈括号匹配

    2015-09-29 21:15:44
    #include #include #include #define length 100 #define add 10 typedef struct size { char *top; char *basic; int stacksize; }Stacks; void InitStacks(Stacks &S) ... S.basic=(char *)malloc(length * siz
  • 利用顺序栈实现括号匹配

    千次阅读 2017-11-09 20:59:01
    printf("括号匹配成功"); return OK; } else printf("括号匹配失败"); return ERROR; } void main(){ char str[100]; SqStack S; InitStack (S); printf("请输入...
  • 顺序栈判断表达式的括号是否匹配
  • 顺序栈括号匹配的检验)

    千次阅读 2018-10-07 19:27:47
    #pragma warning(disable:4996) #include&lt;cstring&gt; #include&lt;cstdio&gt; #include&lt;cstdlib&gt; #define STACK_INIT_SIZE ...//顺序栈 typedef struct { char *base; char *t...
  • 顺序栈括号匹配算法

    千次阅读 2012-07-24 23:21:18
    #include const int Stack_Size = 30; const int TRUE = 1;...typedef struct //定义顺序栈结构 { char data[Stack_Size]; int top; //栈顶指针 }SqStack; void BracketMatch(char *);
  • 假设表达式中允许括号嵌套,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。 我们下面给和例子进行说明: 可能出现的不匹配的情况: ① 盼来的右括号不是所“期待”的; ② 到来的是“不速之客” ...
  • 顺序栈使用——括号匹配的检验

    千次阅读 多人点赞 2017-11-30 16:12:17
    顺序栈使用——括号匹配的检验 码文不易,如果帮助到您,希望您可以帮我刷一下点击量,与您无害,与我有益谢谢 支持原创 。   欢迎大家阅读我的博客,如果有错误请指正,有问题请提问,我会尽我全力改正...
  • //用栈括号匹配的问题  //采用的存储结构为顺序存储结构  #include   using namespace std; #define MAXSIZE 100  //栈的结构体 struct Node { int *base; int *top; int stackSize; };  //...
  • #include "strack.h" int main() {  char e;  char a;  StrackPtr s = InitStrack();//初始化  int count = 0;  char string[50] = {0};  gets(string);    int n = strlen(string);  //pr...
  • 数据结构习题与解析(B级第3版) 李春葆 喻丹丹 编著 3.2
  • 顺序栈实现匹配括号功能

    千次阅读 2007-11-12 19:15:00
    //用顺序栈实现匹配括号功能#include #include #define MAXSIZE 100typedef char datatype;typedef struct //定义数据结构{ datatype data[MAXSIZE]; int top;}SeqStack;SeqStack *InitStack(){ SeqStack *s; s...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 910
精华内容 364
关键字:

顺序栈括号匹配