子瑜子墨
2017-05-09 13:31
采纳率: 25%
浏览 5.9k
已采纳

C语言 用栈实现 括号匹配

符号匹配(50分)
题目内容:
判断输入的括号字符串是否匹配,
括号有()、[]、{}、<>四种,
匹配的定义如下:
(1) 空字符串为匹配。
(2) 若S为匹配字符串,则(S)、[S]、{S}、为匹配自串。
(3) 两个匹配字符串串接亦为匹配字符串。

输入格式:
输入第一行为一个数字T,代表测试数据的笔数。
接下来会有T笔测试数据,每一笔测试数据一行。
每一笔测试数据的字符串长度不超过2000字符。
T < 1000

输出格式:
输出一行数字,输出测资中有多少匹配字符串。

输入样例:
5
()
<><>[]

([{[]}])
<()){}

输出样例:
4

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • 君子黎 2017-05-09 16:15
    已采纳

    麻烦楼主采纳一下,谢谢^^

    打赏 评论
  • 君子黎 2017-05-09 13:58
    
     /*** Seqstack.h **/
     #pragma once
    
    #define MAXSIZE 1024
    
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    
    struct SStack
    {
        void* data[MAXSIZE]; //保存数据的数组
        int size;
    };
    
    typedef void* SeqStack;
    
    #ifdef __cplusplus
    extern "C"{
    #endif
    
        //初始化
        SeqStack Init_SeqStack();
        //入栈
        void Push_SeqStack(SeqStack stack,void *data);
        //出栈
        void Pop_SeqStack(SeqStack stack);
        //获得栈顶元素
        void* Top_SeqStack(SeqStack stack);
        //获得栈中元素个数
        int Size_SeqStack(SeqStack stack);
        //销毁栈
        void Destroy_SeqStack(SeqStack stack);
    
    
    #ifdef __cplusplus
    }
    #endif
    
    /***Seqstack.cpp**/
    #include"SeqStack.h"
    
    //初始化
    SeqStack Init_SeqStack()
    {
        //一般情况下,只要开辟内存空间都要初始化
        struct SStack *stack = malloc(sizeof(struct SStack));
        for (int i = 0; i < MAXSIZE;++i)
        {
            stack->data[i] = NULL;
        }
    
        //memset(stack->data, 0, MAXSIZE * sizeof(void *));
    
        stack->size = 0;
    
        return stack;
    }
    //入栈
    void Push_SeqStack(SeqStack stack, void *data)
    {
        if (NULL == stack)
        {
            return;
        }
    
        if (NULL == data)
        {
            return;
        }
    
        struct SStack *s = (struct SStack *)stack;
    
        if (s->size == MAXSIZE)
        {
            return;
        }
    
        s->data[s->size] = data;
        s->size++;
    
    }
    //出栈
    void Pop_SeqStack(SeqStack stack)
    {
        if (NULL == stack)
        {
            return;
        }
    
        struct SStack *s = (struct SStack *)stack;
    
        if (s->size == 0)
        {
            return;
        }
    
        s->size--;
    
    }
    //获得栈顶元素
    void* Top_SeqStack(SeqStack stack)
    {
        if (NULL == stack)
        {
            return NULL;
        }
    
        struct SStack *s = (struct SStack *)stack;
    
        if (s->size == 0)
        {
            return NULL;
        }
    
        return s->data[s->size - 1];
    
    }
    //获得栈中元素个数
    int Size_SeqStack(SeqStack stack)
    {
        if (NULL == stack)
        {
            return -1;
        }
    
        struct SStack *s = (struct SStack *)stack;
    
        return s->size;
    }
    //销毁栈
    void Destroy_SeqStack(SeqStack stack)
    {
        if (NULL == stack)
        {
            return;
        }
    
        free(stack);
        stack = NULL;
    }
    
    /****main.c*****/
    #define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include"SeqStack.h"
    
    int IsLeft(char ch)
    {
        return ch == '(';
    }
    
    int IsRight(char ch)
    {
        return ch == ')';
    }
    
    void printError(const char *str, char *pos)
    {
        printf("%s\n",str);
        int dis = pos - str;
        for (int i = 0; i < dis; ++i)
        {
            printf(" ");
        }
        printf("A\n");
    
    }
    
    void test()
    {
        const char *str = "5+5*(6)+9/3(*1)-(1)+3()";
    
    
        char *p = (char *)str;
    
        //创建栈
        SeqStack stack = Init_SeqStack();
    
        while (*p != '\0')
        {
    
            //如果是左括号,入栈
            if (IsLeft(*p))
            {
                Push_SeqStack(stack, p);
            }
    
            //如果是右括号
            if (IsRight(*p))
            {
    
                if (Size_SeqStack(stack) > 0)
                {
                    Pop_SeqStack(stack);
                }
                else
                {
                    //printf("没有匹配的左括号!\n");
                    printError(str, p);
                }
    
            }
    
            ++p;
        }
    
    
        //如果栈不为空,栈中剩下的是左括号
        while (Size_SeqStack(stack) > 0)
        {
            //printf("左括号没有匹配的右括号!\n");
            printError(str,  (char *)Top_SeqStack(stack) );
            Pop_SeqStack(stack);
        }
    
        //销毁栈
        Destroy_SeqStack(stack);
    
    }
    
    int main(){
    
        test();
    
        system("pause");
        return EXIT_SUCCESS;
    }
    
    打赏 评论
  • 君子黎 2017-05-09 14:00

    楼主你自己根据我写的函数类似写出另外几个括号就可以了

    
    
    打赏 评论

相关推荐 更多相似问题