判断括号是否匹配

54 阅读 0 评论 36 点赞

我是靠谱客的博主怕黑学姐，最近开发中收集的这篇文章主要介绍判断括号是否匹配，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

/***********************************

作者：trieagle(让你望见影子的墙）

日期：2009.6.20

注：转载请保留此信息

************************************/

问题：设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch和link，其中ch域为字符类型。

1、思路：根据括号的特点( ( ) )，进行匹配的时候，第一个做括号最后一个匹配，最后一个左括号与第一个右括号相匹配，恰好可以使用栈来进行存储。

2、方法：先把表达式放在链表中，然后读取链表，当遇见左括号时，把“（”入栈，遇见

“）”时进行出栈，直到栈空或者链表结束。

3、在进行检测括号是否匹配的时候，需要考虑到各种情况：

1）、匹配。例如：（（））

2）、左括号不匹配。例如：（（）

3）、右括号不匹配。例如：（））

4、判断上述几种情况的方式：

1）左括号不匹配：当链表读取结束的时候，检测栈为不为空。

2）右括号不匹配：当栈为空，而链表中还存在“）”。

3）括号匹配：当栈为空，并且读取链表结束。

5、建立链表需要注意的问题：

在本题中采用循环链表，判断循环链表是否结束的条件是：末指针是否等于头指针。

为了防止在表达式中的最后一个字符是

“）”而导致程序出现意外情况，再建立循环链表的时候，在末节点增加一个填充节点。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{ char data;
struct node *next;
}Node;
typedef struct stack
{
char data;
struct stack *next;
}Stack;
Node* initNode()
{
Node *head,*q,*p;
char c;
head=(Node*)malloc(sizeof(Node));

if(head)
q=head;

printf("Please input the expression:/n");
while((c=getchar())!=';')
{
    p=(Node*) malloc(sizeof(Node));
    p->data=c;
    q->next=p;
    q=p;
}
    p=(Node*) malloc(sizeof(Node));
    p->data='?';
    q->next=p;
    q=p;

q->next=head;
return head;
}
Stack* initStack()
{
Stack *top;
top=(Stack *) malloc(sizeof(Stack));
if (top)
return top;
else
printf("初始化栈失败");
}
Stack *pushstack(Stack *top,char c)
{

Stack *p;
p=(Stack *)malloc(sizeof(Stack));
p->data=c;
p->next=top;
top=p;

return top;
}
Stack *popstack(Stack *top)
{
Stack * p;
p=top;
p->data=top->data;
top=top->next;
free(p);

return top;
}

int main(int argc, char *argv[])
{
Node *pNode,*p;
Stack *pStack,*Stacktop;
pNode=initNode();
pStack=initStack();
if (pNode)
p=pNode;
if(pStack)
Stacktop=pStack;

while(p && p->next!=pNode)
{
    if(p->data=='(')
      {
       pStack=pushstack(pStack,pNode->data);

       }
    if(p->data==')')
      {

        if(pStack!=Stacktop)
            pStack=popstack(pStack);
        else
            break;
       }
    p=p->next;
}
printf("匹配结束，结果为/n");
if(pStack!=Stacktop)
     printf("左括号不匹配/n");
else
     if(p->next!=pNode)
        printf("右括号不匹配/n");
     else
        printf("括号匹配/n");