欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

PTA-括号问题

程序员文章站 2022-10-05 23:18:54
给定一串字符,不超过100个字符,可能包括括号、数字、字母、标点符号、空格,编程检查>这一串字符中的( ) ,[ ],{ }是否匹配。 ......

括号问题

作者: 李廷元
单位: 中国民用航空飞行学院
时间限制: 400 ms
内存限制: 64 mb
代码长度限制: 16 kb

问题描述

给定一串字符,不超过100个字符,可能包括括号、数字、字母、标点符号、空格,编程检查>这一串字符中的( ) ,[ ],{ }是否匹配。

输入格式:

输入在一行中给出一行字符串,不超过100个字符,可能包括括号、数字、字母、标点符号、空格。

输出格式:

如果括号配对,输出yes,否则输出no。

输入样例1:

sin(10+20)

输出样例1:

yes

输入样例2:

{[}]

输出样例2:

no

代码

#include<stdio.h>
#include<stdlib.h>
#define maxsize 100

typedef struct snode* stack;
struct snode {
    char data[maxsize];
    int top;
};

stack create ();
int push (stack s, char x);
char pop (stack s);

int main ()
{
    char str[101];
    stack s = create ();
    int i = 0, flag = 1;
    gets(str);
    while(str[i] != '\0')
    {
        if(str[i] == '(' || str[i] == '[' || str[i] == '{')
            push(s, str[i]);
        else if(str[i] == ')' || str[i] == ']' || str[i] == '}')
        {
            if(s->top == -1)
            {
                flag = 0;
                printf("no\n");
                break;
            }
            if(str[i] == ')')
            {
                if(s->top == -1 || s->data[s->top] != '(')
                {
                    flag = 0;
                    printf("no\n");
                    break;
                }
                else pop(s);
            }
            if(str[i] == ']')
            {
                if(s->top == -1 || s->data[s->top] != '[')
                {
                    flag = 0;
                    printf("no\n");
                    break;
                }
                else pop(s);
            }
            if(str[i] == '}')
            {
                if(s->top == -1 || s->data[s->top] != '{')
                {
                    flag = 0;
                    printf("no\n");
                    break;
                }
                else pop(s);
            }
        }
        i++;
    }
    
    if(flag != 0)
    {
        if(s->top == -1)
            printf("yes\n");
        else
            printf("no\n");
    }
    
    return 0;
}
stack create ()
{
    stack s = (stack)malloc(sizeof(struct snode));
    s->top = -1;
    
    return s;
}
int push (stack s, char x)
{
    if(s->top == 99)
    {
        printf("stack full\n");
        return -1;
    }
    else
    {
        s->data[++(s->top)] = x;
        return 1;
    }
}
char pop (stack s)
{
    if(s->top == -1)
    {
        printf("stack empty\n");
        return -1;
    }
    else
        return (s->data[(s->top)--]);
}

一开始是使用的while((ch = getchar()) != '\n')来读取字符,结果一直超时,个人认为可能是因为调用getchar函数次数过多。