栈的应用—检验括号序列是否匹配

栈的应用—检验括号序列是否匹配

很久没更新博客了。一直忙于学习Java后端方面的知识,外加复习期末考试的相关科目。趁着操作系统考完的时间更新一篇水文(囧)。

题目描述

检查输入的圆括号串的括号是否配对,若配对输出“OK”,若不配对输出“Error ”。

注:

1. 可判断包含 ( 圆括号 ) 和   [ 方括号  ] 两种括号

2. 括号序列里的包含的非圆括号和方括号之外的字符不影响结果

3. 例如[()]为“OK”    [([]) 为“Error ”

输入

输入一串括号字符信息,以#作为结束标志。

输出

匹配结果

样例输入

((())[)]#

样例输出

Error

实现代码:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXLEN 100
typedef char datatype;
typedef struct stacknode
{
    datatype data[MAXLEN];
    int top;
}SeqStack;
int InitStack(SeqStack *&s)
{
  s=new SeqStack;
  s->top =-1;
  return 1;
}
int Push(SeqStack *&st,datatype x)
{
    if(st->top==MAXLEN-1) return 0;
    else
    {
        st->top++;
        st->data[st->top]=x;
        return 1;
    }
}
int Pop(SeqStack *&st,datatype x)
{
    if(st->top==-1) return 0;
    x=st->data[st->top];
    st->top--;
    return 1;
}
int IsSeqEmpty(SeqStack *st)
{
    if(st->top==-1)
    {
        return 0;
    }
    else
    {
        return 1;
    }
}
datatype ReadTop(SeqStack *s)
{
    return s->data[s->top];
}
int matching(char *exp)
{
    int state=1;
    int i;
    SeqStack *s;
    InitStack(s);
    datatype x;
    for (i = 0; i <strlen(exp); ++i)
    {
        if (exp[i] != '(' &&exp[i] != ')' &&
            exp[i] != '[' && exp[i] != ']')
        {
            continue;
        }
        else
        {
            if ('(' == exp[i] || '[' == exp[i])
            {
                Push(s,exp[i]);
            }
            else
            {
                if(IsSeqEmpty(s)==0)
                {
                    state=0;
                }
                char c =ReadTop(s);
                if (('(' == c && ')' == exp[i])||
                    ('[' == c && ']' == exp[i]))
                {
                    Pop(s,x);
                }
                else
                {
                    state=0;
                }
            }
        }
    }
    if(state==1&&IsSeqEmpty(s)!=1)
    {
      return 1;
    }
    else
    {
      return 0;
    }
}
int main()
{
    datatype n,a[MAXLEN];
    int i=0;
    while(1)
    {
        scanf("%c",&n);
        if(n=='#')break;
        a[i]=n;
        i++;
    }
    if(matching(a)==1)
    {
        printf("OK");
    }
    else
    {
        printf("Error");
    }
    return 1;
}

运行效果:

符号匹配
符号匹配
分享

EvenYan

一90后在读计算专业大学生,擅长各种语言的hello world以及安装各种软件。
guest
0 评论
内联反馈
查看所有评论