bracketmatching.cpp

这个是编译原理课程的词法分析器

//
// 使用栈来实现括号是否匹配.
//

#include "stdlib.h"
#include "stdio.h"

// 栈中最多保存的元素个数
#define MAXSTACK 100			

// 定义栈,采用静态分配的顺序存储空间.
typedef char StackEntry;

typedef struct Stack {
	// 程序中约定top指向栈顶元素的下一个位置
	int top;            
	// 栈中元素保存在entry数组中
	StackEntry entry[MAXSTACK]; 
} Stack;

/*
 * 出错时调用error,以显示错误的提示信息.
 */
void error(char *s){
	fprintf(stderr,"%s\n",s);
	exit(1);
}

/*
 * 栈初始化操作.
 */
void initStack(Stack *s){
 	s->top=0;
}

/*
 * 判断栈是否为空,为空返回TRUE,否则返回FALSE.
 */
bool isEmpty(Stack *s){
	return s->top<=0;
}

/*
 * 判断栈是否为满,为满返回TRUE,否则返回FALSE.
 */
bool isFull(Stack *s){
	return s->top>=MAXSTACK;
}

/*
 * 入栈操作,在s的栈顶插入一个元素item.
 */
void push(Stack *s,StackEntry item){
	if(isFull(s))
		error("Stack is full");
	else{   
		s->entry[s->top++]=item;
	}
}

/*
 * 出栈操作,在s的栈顶删除一个元素,并用item保存删除的元素.
 */
void pop(Stack *s,StackEntry *item){
	if(isEmpty(s))
		error("Stack is empty");
	else{
		*item=s->entry[--s->top];
	}
}

/*
 * 取栈顶元素,用item保存栈顶元素的值.
 */
void top(Stack *s,StackEntry *item){
	if(isEmpty(s))
		error("Stack is empty");
	else{	
		*item=s->entry[s->top-1];
	}
}

/*
 * 按照从栈底到栈顶的次序显示栈中的所有元素.
 */
void outputStack(Stack *s){
	int i=0;
	if(isEmpty(s))
		error("Stack is Empty");
	else
		while(i<s->top)
		printf("%c",s->entry[i++]);
	printf("\n");
}

/*
 * 主程序
 */
int main() {
	char input,item;
	Stack s;
	initStack(&s);
	printf("请输入要进行匹配的括号串:");	
	// 输入回车时表示输入完成	
	while((input=getchar())!='\n'){							
		// 该句使得程序可以处理夹杂在各种字符中的括号的匹配问题
		if(input=='['||input==']'||input=='('||input==')'){	
			if(isEmpty(&s)) 
				push(&s,input);	      
			else{
				top(&s,&item);
				if((item=='['&&input==']')||(item=='('&&input==')'))
					pop(&s,&item);
				else 
					push(&s,input); 
			}
		}
		// 下面的语句输出在匹配过程中栈中内容的变化
		if(isEmpty(&s))	 
			printf("stack is empty\n");
		else 
			outputStack(&s);							
	}	
	
	// 根据栈中的情况判定括号是否匹配
	if(isEmpty(&s))
		printf("此次输入匹配成功.\n");
	else 
		printf("此次输入匹配失败.\n");
	return 0;
}