judge.h

定义和实现了一个栈及其操作编译的时候只要用TC2.0或者WinTC打开Main.c文件进行编译就好了。如发现有Bug请在这里贴出来或者把修改后的代码跟帖在这里:)总之

#include "stdio.h"
#include "stdlib.h"
#define TRUE 1
#define FALSE 0

//算符优先关系表：
char O_Table[O_NUMBER][O_NUMBER] = {
	{'>','>','<','<','<','>','<','>'},
	{'>','>','<','<','<','>','<','>'},
	{'>','>','>','>','<','>','<','>'},
	{'>','>','>','>','<','>','<','>'},
	{'<','<','<','<','<','=','<','-'},
	{'>','>','>','>','-','>','-','>'},
	{'>','>','>','>','-','>','-','>'},
	{'<','<','<','<','<','-','<','='}
	};	//优先关系表：八个字符分别是+-*/()i#,其中'-'表示出错

//文法：
#define OG_NUMBER 6	//文法个数
char OG[OG_NUMBER][4] = {"E+E","E-E","E*E","E/E","(E)","i"};	//文法右部

//堆栈：由专门的函数操作（PopUp(),Push(),…）
#define STACK_MAX_SIZE 1000	//堆栈最大存储量
SToken Stack[STACK_MAX_SIZE];	//堆栈
int ipStack = 0;		//堆栈指针，指向栈顶（下一个空位置）

//函数声明：
bool Judge(); //利用算符优先关系表判断单词序列是否正确
int GuiYue(); //规约，并判断是否完成
bool IsOK(); //判断规约是否全部完成
bool GuiYueN(int n); //将堆栈中0~n单词规约
int FindPriorOp(int Begin); //在堆栈中，从Begin开始，查找前一个终结符位置
int MoveIn(); //移进，并判断是否需要规约
void JudgeInit(); //（利用算符优先关系表判断单词序列是否正确）判断前的初始化
SToken Peek(int n); //窥视堆栈
bool PopUp(int n); //弹出堆栈
void PushToken(char ch, int O_No); //压栈（以字符形式）
void Push(SToken Token); //压栈

//（利用算符优先关系表判断单词序列是否正确）判断前的初始化
//由于多个表达式需要依次判断，因此对每个表达式判断前都需要初始化
void JudgeInit()
{
	ipStack = 0; //堆栈初始化（如果有专门的StackClear()函数则更好）

	ipToken = 0; //指向首个单词
}

//压栈（以字符形式）
//参数：ch是要压栈的字符（+-*/()i#E 之一），O_No运算符序号
//调用：Push()
void PushToken(char ch, int O_No)
{
	SToken Token;
	Token.ch = ch;
	Token.No = O_No;
	Push(Token);
}

//利用算符优先关系表判断单词序列是否正确
//返回：TRUE正确；FALSE错误，且错误信息存于ErrMsg
//本函数的实现思路：
//    将单词序列进行“移进-规约”操作，最后判断是否能全部完成
//    使用到：堆栈（SToken Stack[]）、文法（char OG[][]）、算符优先关系表（char O_Table[][]）等
bool Judge()
{
	JudgeInit();
	PushToken('#',O_NUL);	//将“#”号置栈底
	while(TRUE)	//进行“移进-规约”操作
	{
		switch(MoveIn())
		{
		case 1: //需要规约
			switch(GuiYue())//规约
			{
			case 1: //这一步规约成功
				break;
			case 2: //规约全部完成
				return TRUE;
			default: //出错
				ErrMsg = "规约错误。";
				return FALSE;
			}
			break;
		case 2: //需要继续移进
			break;
		default: //出错
			return FALSE;
		}
	}
}

//规约，并判断是否完成
//返回：-1出错，1这一步规约成功，2规约全部完成
int GuiYue()
{
	int n0,n;
	char r; //存优先关系

	n = FindPriorOp(-1); //取得堆栈中第一个终结符
	if(Peek(n).ch == '#') //出错或全部结束
	{
		if(IsOK())
			return 2;
		else
			return -1;
	}
	while(TRUE)
	{
		n0 = n;
		n = FindPriorOp(n0); //前一个终结符的堆栈位置
		if(n - n0 > 2) //出错（多个非终结符相邻）
			return -1;
		r = O_Table[Peek(n).No][Peek(n0).No];
		if(r == '<') //寻找结束
		{
			if(! GuiYueN(n - 1)) //规约（从前一个后的字符开始）规约失败
				return -1;
			else //规约成功，还要判断是否全部完成
			{
				if(IsOK())
					return 2; //规约全部完成
				else
					return 1; //这一步规约成功
			}
		}
		else if(r == '=') //继续向前找
		{
			continue;
		}
		else //出错（r为>或没有关系）
			return -1;
	}
}

//判断规约是否全部完成
//返回：TRUE全部完成；FALSE没有完成
bool IsOK()
{
	//if(Peek(1) == NULL) return FALSE;
	if(Peek(0).ch == 'E'&& Peek(1).ch == '#' && Token[ipToken].ch == '#')
		return TRUE;
	else
		return FALSE;
}

//返回：TRUE成功，FALSE失败
bool GuiYueN(int n) //将堆栈中0~n单词规约
{
	int i,j;
	bool k;
	for(i=0;i<OG_NUMBER;i++) //将规约串和文法右部OG[][]每一个进行比较
	{
		for(j=n,k=FALSE;j>=0;j--)
		{
			if(OG[i][n-j] != Peek(j).ch)
			{
				k = TRUE; //TRUE表示规约串和文法右部不符，
				break;
			}
		}
		if(k) continue; 
		//k==FALSE表示规约串判断完成
		if(OG[i][n+1]=='\0') //文法也判断完成，匹配成功
		{
			PopUp(n + 1); //弹出规约串
			PushToken('E',O_IDENT); //压入左部“E”
			return TRUE;
		}
	}
	return FALSE;
}

//在堆栈中，从Begin开始，查找前一个终结符位置
//如果从开始找，让 Begin = -1
int FindPriorOp(int Begin)
{
	int n;
	n = Begin + 1;
	while(Peek(n).ch == 'E')
	{
		n ++;
	}
	return n;
}

//移进，并判断是否需要规约
//返回：-1出错，1需要规约，2可继续移进
//   1.单词结束（遇到“#”号），无法移进，需要规约，返回：1
//   2.单词没有结束，需判断是否可以移进
//     2-1.堆栈单词<=单词：移进后返回：2
//     2-2.堆栈单词>单词：不能移进，需要规约，返回：1
//     2-3.两单词没有优先关系：出错，返回：-1
int MoveIn()
{
	SToken s,t; //分别存堆栈顶单词和单词序列的第一个单词
	char r; //存放优先关系
	s = Peek(FindPriorOp(-1)); //取得堆栈中第一个终结符位置
	t = Token[ipToken];
	r = O_Table[s.No][t.No];
	if(t.ch == '#') //单词结束，无法移进，需要规约
		return 1;
	else //单词没有结束，需判断是否可以移进
	{
		if(r == '<' || r == '=') //需要移进
		{
			Push(t);
			ipToken ++;
			return 2;
		}
		else if(r == '>') //不能移进，需要规约
			return 1;
		else //没有优先关系，出错
		{
			MakeErr("移进时出现两个没有优先关系的相邻单词。");
			return -1;
		}
	}
}



//窥视堆栈
//参数：n相对栈顶的位置（0开始）
//成功返回：返回单词
//不成功返回：NULL
SToken Peek(int n)
{
	SToken Token;
	if(n > 0 || n < ipStack) 
		Token = Stack[ipStack - n - 1];
	else if(n < 0)
		Token = Stack[ipStack - 1];
	else
		Token = Stack[0];
	return Token;
}

//弹出堆栈
//参数：n弹出单词个数（不能全部弹空，即保留#号）
//不成功返回：FALSE
//成功返回：TRUE
bool PopUp(int n)
{
	if(ipStack < 2) return FALSE; //只剩0个或1个
	if(n > ipStack - 1) n = ipStack - 1;
	ipStack -= n;
	return TRUE;
}



//压栈
//参数：Token是要压栈的SToken结构体类型的单词
//缺点：没有判断堆栈是否满
void Push(SToken Token)
{
	Stack[ipStack ++] = Token;
}