利用堆栈实现符号匹配（c语言）

7-6 符号配对 (20 分)  

请编写程序检查C语言源程序中下列符号是否配对：/*与*/、(与)、[与]、{与}。

输入格式:

输入为一个C语言源程序。当读到某一行中只有一个句点.和一个回车的时候，标志着输入结束。程序中需要检查配对的符号不超过100个。

输出格式:

首先，如果所有符号配对正确，则在第一行中输出YES，否则输出NO。然后在第二行中指出第一个不配对的符号：如果缺少左符号，则输出?-右符号；如果缺少右符号，则输出左符号-?。

输入样例1：

void test()
{
    int i, A[10];
    for (i=0; i<10; i++) { /*/
        A[i] = i;
}
.

  输出样例1：

NO
/*-?

  输入样例2：

void test()
{
    int i, A[10];
    for (i=0; i<10; i++) /**/
        A[i] = i;
}]
.

  输出样例2：

NO
?-]

  输入样例3：

void test()
{
    int i
    double A[10];
    for (i=0; i<10; i++) /**/
        A[i] = 0.1*i;
}
.

  输出样例3：

YES


本代码取自陈越《数据结构学习与实验指导》第二版，作者在上面标注注释供自己学习，仅参考


代码

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

#define MAXN 100 //最大的容量
typedef enum{false,true}bool;
typedef enum{ret,lc,lbrc,lbrkt,lpr,rc,rbrc,rbrkt,rpr,others}Token;
//用代号对各个符号命名,l开头的是左类型（{,/*,[,(）,r开头的是右（}，*/，],)）。ret回车，others其它字符，如数字等
typedef Token ElementType;

typedef int Position;
typedef struct SNode* PtrToSNode;
struct SNode{ //堆栈的定义
ElementType *Data;
Position Top;
int MaxSize;
};
typedef PtrToSNode Stack;
//堆栈相关操作
Stack CreateStack(int MaxSize);
bool IsEmpty(Stack S); //判断栈空
void Push(Stack S,ElementType X); //入栈
ElementType Peek(Stack S); //取出栈顶元素
void Pop(Stack S); //出栈
//读取和输出
bool IsEnd(int newline,char *c); //判断是否到行尾
Token GetToken(char c); //
bool IsPaired(Token t1,Token t2); //
void PrintS(Token t); //输出对应的符号，部分符号用了2个字节，专门写一个函数去输出它
int Check(Token* T1,Token* T2); //如果最后栈中不为空，则剩下的是未匹配的

int main(){
Token T1,T2;
int error=Check(&T1,&T2);

if(!error)
printf("YES\n");
else{
printf("NO\n");
switch(error){
case 1:printf("?-");PrintS(T1);break;
case 2:PrintS(T2);printf("-?");break;
default:break;
}
printf("\n");
}
return 0;
}

Stack CreateStack(int MaxSize){
Stack S=(Stack)malloc(sizeof(struct SNode));
S->Data=(ElementType*)malloc(MaxSize* sizeof(ElementType));
S->Top=-1;
S->MaxSize=MaxSize;
return S;
}

bool IsEmpty(Stack S){
return (S->Top==-1);
}

void Push(Stack S,ElementType X){
S->Data[++(S->Top)]=X;
}

ElementType Peek(Stack S){
return (S->Data[S->Top]);
}

void Pop(Stack S){
(S->Top)--;
}

int Check (Token *T1,Token* T2){
Stack S; //检测用的堆栈
char c; //存读入字符
Token t; //存字符转化后的类型
int newline,error; //因为我们题目是有多行的，newline用来标记是否为新行，error标记错误；

S=CreateStack(MAXN);
newline =1;error=0; //无错误，新行
while(1){ //读入所有字符
scanf("%c",&c);
if(IsEnd(newline,&c)) break; //如果到文章尾跳出循环
else{
switch(t=GetToken(c)){
case lc: //如果是左类型
case lbrc:
case lbrkt:
case lpr:
Push(S,t); newline = 0;break; //不是新行，入检测栈
case rc: //如果是右类型
case rbrc:
case rbrkt:
case rpr:
if(IsEmpty(S)) error=1; //栈空了，error为1，即为入栈失败
else if(!IsPaired(t,Peek(S))) error=2; //错误2
else Pop(S); //一切正常消去一对符号
newline=0; //不再是新行；
break;
case ret: newline =1;break; //遇见回车
default: newline =0;break; //其它字符跳过不处理
}
if(error) break; //有错误跳出循环
}
}
if(!error&&!IsEmpty(S)) error=2; //读到结尾栈没空，左半符号有多
(*T1)=t;
(*T2)=Peek(S);

return error;
}

bool IsEnd(int newline,char *c)
{/*判断是否读到结尾*/
if(newline && (*c)=='.'){
scanf("%c",c);
if((*c)=='\n') return true;
else return false;
}
else return false;
}

Token GetToken(char c)
{/*返回字符的类型*/
switch (c) {
case '\n': return ret;
case '{' : return lbrc;
case '[' : return lbrkt;
case '(' : return lpr;
case '/' :
scanf("%c",&c);
if(c=='*') return lc;
else return GetToken(c);
/*如果不是左注释符，还要检查c的类型*/
case '}' : return rbrc;
case ']' : return rbrkt;
case ')' : return rpr;
case '*' :
scanf("%c",&c);
if(c=='/') return rc;
else return GetToken(c);
/*如果不是右注释符，还要检查c的类型*/
default: return others;
}
}

bool IsPaired(Token t1,Token t2)
{
return (t1-t2)==4;
/*t1是右半符，t2是左半符*/
/*如果它们的enum值差4，说明是匹配的*/

}

void PrintS(Token t)
{
switch (t) {
case lc:printf("/*");break;
case lbrc:printf("{");break;
case lbrkt:printf("[");break;
case lpr:printf("(");break;
case rc:printf("*/");break;
case rbrc:printf("}");break;
case rbrkt:printf("]");break;
case rpr:printf(")");break;
default: break;
}
}