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

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

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

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

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

实验环境

• 语言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;
}

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

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