顺序栈实现括号匹配的检验_用栈实现括号匹配问题[通俗易懂]

顺序栈实现括号匹配的检验_用栈实现括号匹配问题[通俗易懂]顺序栈使用——括号匹配的检验码文不易,如果帮助到您,希望您可以帮我刷一下点击量,与您无害,与我有益谢谢支持原创

顺序栈使用——括号匹配的检验


码文不易,如果帮助到您,希望您可以帮我刷一下点击量,与您无害,与我有益谢谢 支持原创

  欢迎大家阅读我的博客,如果有错误请指正,有问题请提问,我会尽我全力改正错误回答问题。在次谢谢大家。下面开始正式内容

  顺序栈部分在之前已经在另一篇文章中提及,本篇中就不再提及,如有需要请阅读
<顺序栈的各种基本运算>

实验环境


  • 语言c/c++
  • 编译器devc++5.11/5.40

实验内容与要求


问题描述:
  假设表达式中允许有两种括号:圆括号和方括号,其嵌套的顺序随意,即(()[ ])或[([ ] [ ])]等为正确格式,[( ])或(((]均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如:考虑下列的括号序列:

[ ( [ ] [ ] ) ]
1  2 3 4 5 6 7 8

  当计算机接受了第1个括号以后,他期待着与其匹配的第8个括号的出现,然而等来的却是第2个括号,此时第1个括号“[”只能暂时靠边,而迫切等待与第2个括号相匹配的 第7个括号“)”的出现,类似的,因只等来了第3个括号“[”,此时,其期待的紧迫程度较第2个括号更紧迫,则第2个括号只能靠边,让位于第3个括号,显然第3个括号的期待紧迫程度高于第2个括号,而第2个括号的期待紧迫程度高于第1个括号;在接受了第4个括号之后,第3个括号的期待得到了满足,消解之后,第2个括号的期待匹配就成了最急迫的任务了,…… ,依次类推。可见这个处理过程正好和栈的特点相吻合。
读入圆括号和方括号的任意序列,输出“匹配”或“此串括号匹配不合法”。
如:输入([ ]()),结果“匹配”
  输入 [( )],结果“此串括号匹配不合法”

目录


码文不易,如果帮助到您,希望您可以帮我刷一下点击量,与您无害,与我有益谢谢 支持原创

实验解析

思路方法


  设置一个栈,每读入一个括号,若是左括号,则作为一个新的更急迫的期待压入栈中;若是右括号,并且与当前栈顶的左括号相匹配,则将当前栈顶的左括号退出,继续读下一个括号,如果读入的右括号与当前栈顶的左括号不匹配,则属于不合法的情况。在初始和结束时,栈应该是空的。

定义说明


Stack  opr_stack 栈

  定义常用常量,类型别称

函数说明


运算函数

配对
int CheckMatch(char *s,Stack* opr_stack){
    int i= 0; 
    int length = strlen(s);
    while(i<length){
        if(s[i]=='('||s[i]==')'||s[i]=='{'||s[i]=='}'||s[i]=='['||s[i]==']'){
  
  //如果当前字符是运算符.
            switch(s[i]){
                case '(':
                    PushStack(*opr_stack,'(');          
                    break;
                case '[':
                    PushStack(*opr_stack,'[');
                    break;
                case '{':
                    PushStack(*opr_stack,'{');
                    break;
                case ')':
                    if(EmptyStack(*opr_stack)==1&&TopStack(*opr_stack)!='(')
                        return 0;
                    OutStack(*opr_stack);
                    break;
                case ']':
                    if(EmptyStack(*opr_stack)==1&&TopStack(*opr_stack)!='[')
                        return 0;
                    OutStack(*opr_stack);
                    break;
                case '}':
                    if(EmptyStack(*opr_stack)==1&&TopStack(*opr_stack)!='{')
                        return 0;
                    OutStack(*opr_stack);
                    break;
                default:break;
            }
        }
        i++;     
    } 
    if(EmptyStack(*opr_stack)==1) 
        return 1;
    return 0;
}   

  进行一步运算,返回结果。调用时注意栈是否为空,没有做安全防护

主函数



int main(){
    Stack opr_stack;
    InitList_stack(opr_stack);
    char s[100] = {0};
    gets(s);    
    printf("结果是:%s",CheckMatch(s,&opr_stack)==1?"匹配":"不匹配");
    return 0;
}

结果展示


括号匹配的检验结果截图

附录

相关资料

  1. 顺序栈的各种基本运算

源代码

码文不易,如果帮助到您,希望您可以帮我刷一下点击量,与您无害,与我有益谢谢 支持原创


Stack.h

#include<stdio.h> //EOF,NULL
#include<malloc.h> //malloc()
#include<process.h> //exit()

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef  int  Status;
typedef  double    SElemType;
#define STACK_INIT_SIZE 100 //栈存储空间的初始分配量
#define STACKINCREMENT 10 //存储空间分配增量
typedef struct{
   SElemType  *base;             //存储数据元素的数组
   SElemType  *top;              //栈顶指针
   int stacksize;                   //当前分配的栈空间大小
                                 //(以sizeof(SElemType)为单位)
}Stack;


Status InitList_stack (Stack &s) {
    s.base = (SElemType*)malloc( STACK_INIT_SIZE*sizeof(SElemType));
    if (!s.base )   exit(0);
s.stacksize = STACK_INIT_SIZE;
s.top = s.base;

 return OK;
}// InitList_stack
Status EmptyStack (Stack s) 
{ if(s.base == s.top)  return TRUE;
  else return FALSE;
}//
Status PushStack(Stack &s , SElemType e ){
if(s.stacksize<(s.top-s.base) )return ERROR;
if(s.stacksize==(s.top-s.base) )
s.base = (SElemType*)malloc(( s.stacksize+STACKINCREMENT)*sizeof(SElemType));

        *(s.top) = e;
        s.top++;

    return OK;

}
Status GetLength(Stack s){
    return s.top-s.base;
}
Status DisplayStack(Stack &s){

    while(s.base != s.top){

        printf("%c ",*--(s.top));

    }
    printf("\n");
}
SElemType OutStack(Stack &s ){
 SElemType  e;
    if(s.top != s.base)

 e= *(--s.top);

    return e;
}
SElemType TopStack(Stack &s ){
 SElemType  e;
    if(s.top != s.base)

 e= *(s.top-1);

    return e;
}
Status DestroyStack ( Stack s) 
{      if (!s.base)  return ERROR; 
      free (s.base);    
      s.base = NULL;
      s.top = NULL;
      s.stacksize= 0;
      return OK;
}// DestroyList_Sq 

main.cpp

#include "Stack.h"

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>



int CheckMatch(char *s,Stack* opr_stack){
    int i= 0; 
    int length = strlen(s);
    while(i<length){
        if(s[i]=='('||s[i]==')'||s[i]=='{'||s[i]=='}'||s[i]=='['||s[i]==']'){
  
  //如果当前字符是运算符.
            switch(s[i]){
                case '('://如果是加号.
                    PushStack(*opr_stack,'(');          
                    break;
                case '['://如果是减号.
                    PushStack(*opr_stack,'[');
                    break;
                case '{'://如果是乘号.
                    PushStack(*opr_stack,'{');
                    break;
                case ')'://如果是除号.
                    if(EmptyStack(*opr_stack)==1&&TopStack(*opr_stack)!='(')
                        return 0;
                    OutStack(*opr_stack);
                    break;
                case ']'://如果是除号.
                    if(EmptyStack(*opr_stack)==1&&TopStack(*opr_stack)!='[')
                        return 0;
                    OutStack(*opr_stack);
                    break;
                case '}'://如果是除号.
                    if(EmptyStack(*opr_stack)==1&&TopStack(*opr_stack)!='{')
                        return 0;
                    OutStack(*opr_stack);
                    break;
                default:break;
            }
        }
        i++;     
    } 
    if(EmptyStack(*opr_stack)==1) 
        return 1;
}   


int main(){
    Stack opr_stack;
    InitList_stack(opr_stack);
    char s[100] = {
  
  0};
    gets(s);    
    printf("结果是:%s",CheckMatch(s,&opr_stack)==1?"匹配":"不匹配");
    return 0;
}

码文不易,如果帮助到您,希望您可以帮我刷一下点击量,与您无害,与我有益谢谢 支持原创

今天的文章顺序栈实现括号匹配的检验_用栈实现括号匹配问题[通俗易懂]分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/74074.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注