论坛 › C\C++交流 › 括号匹配

lemon3 发表于 2018-12-27 13:31:37

括号匹配

请教，如果只有一对匹配的符号的时候，它在截图部分是直接跳过的，求助！！！
#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
        char charz;
        struct node * next;
}NODE;

void Input(NODE * head)
{
        NODE * p;
        p = head;
        char ch;
        while((ch = getchar())!= '\n')
        {
                p->next = (NODE * )malloc(sizeof(NODE));
                p->next->charz = ch;
                p = p->next;
                p->next = NULL;
        }
}
void Target(NODE * head1, NODE * head2)
{
        NODE * p1, * p2;
        p1 = head1->next;
        p2 = head2;
        int t = 0;      //t记录字符对数
        while(p1 != NULL)         //录入所给字符
        {
                if(p1->charz == '(' || p1->charz == ')' || p1->charz == '[' || p1->charz ==']')
                {       
                        t++;
                        p2->next = (NODE * )malloc(sizeof(NODE));
                        p2->next->charz = p1->charz;       
                        p2 = p2->next;
                        p2->next = NULL;
                }
                p1 = p1->next;       
        }
                if(t%2 != 0)
                {
                        printf("Match false!\n");
                        return ;       
                }       
                else
                {
                        NODE * q1, * q2;
                        q1 = head2;
                        while(q1->next != NULL)
                        {
                                q2 = q1->next;
                                while(q2 != NULL)
                                {
                                        if((q1->next->charz == '(' && q2->next->charz == ')') || (q1->next->charz == '[' && q2->next->charz == ']'))
                                        {
                                                t = t-2;
                                                NODE * n1, * n2;
                                                n1 = q1->next;
                                                n2 = q2->next;
                                                if(q1->next->next->next == NULL)
                                                {
                                                        q1->next = NULL;
                                                        q2 = NULL;
                                                }
                                                else if(q1->next->next == q2->next)
                                                {
                                                        q1->next = q2->next->next;
                                                        while(q2->next != NULL)
                                                        {
                                                                q2 = q2->next;
                                                        }
                                                        q2 = q2->next;       
                                                }
                                                else
                                                {
                                                        q1->next = q1->next->next;
                                                        if(q2->next->next != NULL)
                                                        {
                                                                while(q2->next != NULL)
                                                                {
                                                                        q2 = q2->next;
                                                                }
                                                                q2 = q2->next;
                                                        }
                                                        else
                                                        {
                                                                q2 = NULL;
                                                        }
                                                }
                                                free(n1);
                                                free(n2);
                                        }
                                        else
                                        {
                                                q2 = q2->next;
                                        }
                                }
                        }
                }
                if(t == 0)
                        {
                                printf("Match succeed!\n");
                        }
                        else
                        {
                                printf("Match false!\n");       
                        }
}

int main()
{
        NODE * head1, * head2;
        head1 = (NODE * )malloc(sizeof(NODE));
        head2 = (NODE * )malloc(sizeof(NODE));
        Input(head1);
        //Print(head1);
        Target(head1,head2);
        return 0;
}

rencaixiaomeng 发表于 2018-12-27 18:22:19

程序错误太多了，从NODE * q1, * q2;之后，基本需要全部重新改了

rencaixiaomeng 发表于 2018-12-27 19:08:30

#include<stdio.h>
int Target(void)
{
        char s, c;
        int i;
        i = 0;
        while ((c = getchar()) != '\n')
        {
                switch (c)
                {
                case '(':
                case '[':
                        s = c;
                        i++;
                        break;
                case ')':
                        if (i > 0)
                        {
                                i--;
                                if (s != '(')
                                {
                                        return 0;
                                }
                        }
                        else
                        {
                                return 0;
                        }
                        break;
                case ']':
                        if (i > 0)
                        {
                                i--;
                                if (s != '[')
                                {
                                        return 0;
                                }
                        }
                        else
                        {
                                return 0;
                        }
                        break;
                }
        }
        if (i == 0)
        {
                return 1;
        }
        else
        {
                return 0;
        }
}

int main()
{
        if (Target())
        {
                printf("匹配成功！\n");
        }
        else
        {
                printf("匹配失败！\n");
        }
        return 0;
}
这个重新写的，你琢磨着改一下吧

lemon3 发表于 2018-12-28 11:57:25

rencaixiaomeng 发表于 2018-12-27 19:08
#include
int Target(void)
{


谢谢，可以试着用双向链表解决吗？我正在学数据结构这门课，但是自己写的还有一些问题没想明白。

lemon3 发表于 2018-12-28 11:58:17

rencaixiaomeng 发表于 2018-12-27 18:22
程序错误太多了，从NODE * q1, * q2;之后，基本需要全部重新改了

{:5_100:}

lemon3 发表于 2018-12-28 11:59:58

lemon3 发表于 2018-12-28 11:57
谢谢，可以试着用双向链表解决吗？我正在学数据结构这门课，但是自己写的还有一些问题没想明白。

嗯，刚刚说错了，不一定需要双向链表，线性链表就行

rencaixiaomeng 发表于 2018-12-28 12:21:52

数组就是线性表的一种，要用链表的话也可以，括号匹配只要遵循后进选出就可以了

lemon3 发表于 2018-12-28 12:58:40

那不是栈吗？

查看完整版本: 括号匹配