star

分类

随机文章

最新留言

最新评论

搜索

RSS

RSS Link

计数器

139722

BrainFuck解释器

2011年2月01日 08:57 | Comments(19) | Category:C语言 | Tags:c BrainFuck 解释器

无注释版本：

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

#define SIZE 5000

char data[SIZE], code[SIZE]; 
int  ptr, flag;

void interpreter(char *ip)
{
	char* re;
	
	while (*ip)
	{
		switch(*ip++)
		{
			case '<': --ptr;  break;
			case '>': ++ptr;  break;
			case '+': ++data[ptr]; break;
			case '-': --data[ptr]; break;
			case '.': putchar(data[ptr]);    fflush(stdout); break;
			case ',': data[ptr] = getchar(); fflush(stdout); break;
			case '[': for (flag=1,re=ip; flag && *ip; ++ip)
							flag += *ip=='[', flag -= *ip==']';
				  	  if(!flag)
				  	  {
				  	  		ip[-1] = 0;
				  	  		while (data[ptr])
				  	  			interpreter(re);
			  	  			ip[-1] = ']';
			  	  			break;
				  	  }
			case ']': puts("Unbalancded brackets!"), exit(-3);
			default : ;//SKIP
		}
		if (ptr < 0 || ptr > 100)
			puts("Out of Range"), exit(-4);
	}
}
 
int main(int argc, char *argv[])
{
	FILE *fin;
	int codelength;
	
	if (argc != 2)
		return puts("BrainFuck Interpreter v 0.1\nStar\nUsage:BFI filename"), 0;
	if ((fin = fopen(argv[1], "r")) == NULL)
		return puts("Cannot open file!"), -1;
	fseek(fin, 0, SEEK_END);
	if ((codelength = ftell(fin)) > SIZE)
		return puts("The program is too large."), -2;
	fseek(fin, 0, SEEK_SET);
	fread(code, codelength, 1, fin);
	code[codelength] = '\0';
	interpreter(code);
	return 0;
}

 

栈与队列的三个例子

2010年10月05日 04:07 | Comments(31) | Category:C语言 | Tags:栈 队列 应用

1.小括号匹配

#define FORMATSTR "%c "
typedef char ElemType;
#define BufSize 128

#include "Stack.h"

int CheckBracket(char *str, int len)
{
	int     i = 0;
	SQSTACK S;
	char    ch;
	InitSqstack(&S, len);
	while(str[i])
	{
		ch = str[i];
		if(ch == '(')
			PushS(&S, ch);
		else if(ch == ')')
			if(!PopS(&S, &ch))
			{
				DestroySqstack(&S);
				return 0;
			}
		++i;
	}
	if(IsSqstackEmpty(S))
		;
	else
		i = 0;
	DestroySqstack(&S);
	return i;
}

int main(void)
{
	//栈示例 - 括号匹配 
	char string[BufSize];
	
	gets(string);
	if(CheckBracket(string, strlen(string)))
		puts("Match!");
	else
		puts("Mismatch!");
		
	return 0;
}

2.迷宫求解

#define FORMATSTR
typedef struct
{
	int x, y, v;	//坐标与方向 
}ElemType;
#include "Stack.h"

int Map[10][10] = 
{
1,1,1,1,1,1,1,1,1,1,
1,0,0,1,0,0,0,1,0,1,
1,0,0,1,0,0,0,1,0,1,
1,0,0,0,0,1,1,0,0,1,
1,0,1,1,1,0,0,0,0,1,
1,0,0,0,1,0,0,0,0,1,
1,0,1,0,0,0,1,0,0,1,
1,0,1,1,1,0,1,1,0,1,
1,1,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1,	
};

int tox[5] = {0, 0,1,0,-1};	//偏正方向 
int toy[5] = {0,-1,0,1, 0};	//偏正方向 

int main(void)
{
	//链式栈示例 - 迷宫求解，给定的迷宫，输出所有解。 
	LINKSTACK S;
	ElemType  e;
	int x, y, v;	//当前坐标 
	int ox, oy;		//修正坐标 
	int i, j, k = 0;
	e.x = 1; e.y = 1;	//出发点 
	e.v = 0;			//方向
		 
	InitLinkstack(&S);
	PushL(S, e);
	Map[1][1] = 8;
	while(!IsLinkstackEmpty(S))
	{
		PopL(S, &e);
		x = e.x; y = e.y; v = e.v + 1;
		//back from here
			if(e.v > 0)
				Map[y+toy[e.v]][x+tox[e.v]] = 0;
		while(v <= 4)
		{
			ox = x + tox[v];
			oy = y + toy[v];
			if(ox == 8 && oy == 9)	//终点
			{
				printf("Answer %d:\n", ++k);
				for(i = 0; i < 10; ++i)
				{
					for(j = 0; j < 10; ++j)
						printf("%d ", Map[i][j]);
					putchar(10);
				}
				++v;
			}
			else if(ox > 0 && oy > 0 && !Map[oy][ox])
			{
				e.x = x; e.y = y; e.v = v;
				PushL(S, e);
				x = ox, y = oy; v = 1;
				Map[y][x] = 8;
			}
			else
				++v;
		}
	}
	
	DestroyLinkstack(&S);
	return 0;
}

3.最短路径

#define FORMATSTR
typedef struct
{
	int x, y, pre;	//坐标与方向 
}ElemType;
#include "Queue.h"

int Map[10][10] = 
{
1,1,1,1,1,1,1,1,1,1,
1,0,0,1,0,0,0,1,0,1,
1,0,0,1,0,0,0,1,0,1,
1,0,0,0,0,1,1,0,0,1,
1,0,1,1,1,0,0,0,0,1,
1,0,0,0,1,0,0,0,0,1,
1,0,1,0,0,0,1,0,0,1,
1,0,1,1,1,0,1,1,0,1,
1,1,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1,	
};

int tox[5] = {0, 0,1,0,-1};	//偏正方向 
int toy[5] = {0,-1,0,1, 0};	//偏正方向 

int main(void)
{
	//队列示例 - 迷宫的最短路径 
	SQQUEUE   Q;
	ElemType  e;
	int x, y, v;	//当前坐标 
	int ox, oy;		//修正坐标 
	int i, j, k = 0, step = 2;		//从02开始 
	e.x = 1; e.y = 1;	//出发点 
	e.pre = 2;			//前驱 
		 
	InitSqqueue(&Q, 10*10);
	EnSqqueue(&Q, e);
	Map[1][1] = step;
	while(!IsSqqueueEmpty(Q))		//BFS 
	{
		DeSqqueue(&Q, &e);
		x = e.x; y = e.y; v = e.pre += 1;
		for(i = 1; i <= 4; ++i)
		{
			e.x = x + tox[i];	e.y = y + toy[i];
			if(Map[e.y][e.x] == 0)
			{
				EnSqqueue(&Q, e);
				Map[e.y][e.x] = e.pre;
				if(e.x == 8 && e.y == 8)	//终点 
				{
					printf("The Shortest Path is:\n");
					for(i = 0; i < 10; ++i)
					{
						for(j = 0; j < 10; ++j)
							printf("%02d ", Map[i][j]);
						putchar(10);
					}
					DestroySqqueue(&Q);
					return 0;			//找到就停 
				}
			}
		}
	}
	
	DestroySqqueue(&Q);
	return 0;
}

队列的头文件

2010年10月05日 04:02 | Comments(1) | Category:C语言 | Tags:数据结构 循环队列 链式队列 

/* 数据结构 队列的实现 Queue.h
 * author : star
 */
 
//防止重复定义
#ifndef QUEUE_H
#define QUEUE_H

#include "defs.h"

//初始化大小为n的队列
int InitSqqueue(SQQUEUE *Q, int n)
{
	Q->data = (ElemType *)malloc((n+1) * sizeof(ElemType));
	if(Q->data == NULL)
		return 0;
	Q->front = Q->rear = 0;
	Q->size  = n + 1;
	return 1;
}

//销毁队列
void DestroySqqueue(SQQUEUE *Q)
{
	free(Q->data);
	Q->data = NULL;
	Q->front = Q->rear = Q->size = 0;
}

//判断队空还是满
int IsSqqueueEmpty(SQQUEUE Q)
{
	return Q.front == Q.rear;
}

int IsSqqueueFull(SQQUEUE Q)
{
	return Q.front == (Q.rear+1) % Q.size;
}

//入队
int EnSqqueue(SQQUEUE *Q, ElemType e)
{
	if(IsSqqueueFull(*Q))
		return 0;
	Q->data[Q->rear] = e;
	Q->rear = (Q->rear+1) % Q->size;\
	return 1;
}

//出队
int DeSqqueue(SQQUEUE *Q, ElemType *e)
{
	if(IsSqqueueFull(*Q))
		return 0;
	*e = Q->data[Q->front];
	Q->front = (Q->front+1) % Q->size;
	return 1;
}

//队列长度
int SqqueueLen(SQQUEUE Q)
{
	return (Q.size + Q.rear + Q.front) % Q.size;
}

//初始化空链式队
void InitLkqueue(LKQUEUE *Q)
{
	Q->front = Q->rear = NULL;
}

//销毁链式队列
void DestroyLkqueue(LKQUEUE *Q)
{
	LQNODEPTR p;
	while(Q->front != NULL)
	{
		p = Q->front;
		Q->front = p->next;
		free(p);
	}
	Q->rear = NULL;
}

//入链队
int EnLkqueue(LKQUEUE *Q, ElemType e)
{
	LQNODEPTR p;
	p = (LQNODEPTR)malloc(sizeof(LQNODE));
	if(p == NULL)
		return 0;
	p->data = e;
	p->next = NULL;
	if(Q->front == NULL)
		Q->front      = Q->rear = p;
	else
		Q->rear->next = Q->rear = p;
	return 1;
}

//出链队
int DeLkqueue(LKQUEUE *Q, ElemType *e)
{
	LQNODEPTR p;
	if(Q->front == NULL)
		return 0;
	p = Q->front;
	Q->front = p->next;
	if(Q->front == NULL)
		Q->rear = NULL;
	*e = p->data;
	free(p);
	return 1;
}

#endif

栈的头文件

2010年10月05日 04:00 | Comments(2) | Category:C语言 | Tags:数据结构 栈 链式栈 

/* 数据结构 栈的实现 Stack.h
 * author : star
 */
 
//防止重复定义
#ifndef STACK_H
#define STACK_H

#include "defs.h"

//初始化大小为n的栈 
int InitSqstack(SQSTACK *S, int n)
{
	S->data = (ElemType *)malloc(n * sizeof(ElemType));
	if(S->data == NULL)
		return 0;
	S->size = n;
	S->top  = -1;
	return 1;
}

//销毁栈
void DestroySqstack(SQSTACK *S)
{
	free(S->data);
	S->data = NULL;
	S->top  = -1;
	S->size = 0;
}

//判断栈空、栈满
int IsSqstackEmpty(SQSTACK S)
{
	return S.top == -1;
}

int IsSqstackFull(SQSTACK S)
{
	return S.top == S.size-1;
}

//入栈
int PushS(SQSTACK *S, ElemType e)
{
	if(IsSqstackFull(*S))
		return 0;
	++S->top;
	S->data[S->top] = e;
	return 1;
}

//出栈
int PopS(SQSTACK *S, ElemType *e)
{
	if(IsSqstackEmpty(*S))
		return 0;
	*e = S->data[S->top];
	--S->top;
	return 1;
}

//初始化链式栈
int InitLinkstack(LINKSTACK *S)
{
	*S = (LINKSTACK)malloc(sizeof(LSNODE));
	if(*S == NULL)
		return 0;
	(*S)->next = NULL;
	return 1;
}

//销毁链式栈
int DestroyLinkstack(LINKSTACK *S)
{
	LSNODEPTR q, p;
	p = *S;
	while(p)
	{
		q = p;
		p = p->next;
		free(q);
	}
	*S = NULL;
}

//判断链栈空、满
IsLinkstackEmpty(LINKSTACK S)
{
	return S->next == NULL;
}

IsLinkstackFull(LINKSTACK S)
{
	return S->next != NULL;
}

//入链栈 
int PushL(LINKSTACK S, ElemType e)
{
	LSNODEPTR p;
	p = (LSNODEPTR)malloc(sizeof(LSNODE));
	if(p == NULL)
		return 0;
	p->data = e;
	p->next = S->next;
	S->next = p;
	return 1;
}

//出链栈
int PopL(LINKSTACK S, ElemType *e)
{
	LSNODEPTR p;
	p = S->next;
	if(p == NULL)
		return 0;
	S->next = p->next;
	*e = p->data;
	free(p);
	return 1;
}

#endif

数据结构头文件Ver2.0

2010年10月05日 03:57 | Comments(1) | Category:C语言 | Tags:数据结构 链表 栈 队列 

/* 数据结构 全部结构定义文件 defs.h
 * author : star
 */

//引入所有需要的头文件 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//防止重复定义
#ifndef DEF_H
#define DEF_H

//定义执行状态返回结果
 
#define TRUE 		 1  //成功 
#define FALSE 		 0  //失败 

#ifndef FORMATSTR
#define FORMATSTR "%d " //输出格式 

typedef int ElemType;	//基本数据类型 
#endif

//线性表 
typedef struct
{
	ElemType *data;		//数据 
	int		 size;	    //容量 
	int 	 len;	    //长度 
}SQLIST;

//单链表
typedef struct link_node
{
	ElemType          data;		//数据
	struct link_node *next;		//结点 
}NODE, *NODEPTR, *LINKLIST;

//双向链表 
typedef struct dlink_node
{
	ElemType 		   data;			//数据 
	struct dlink_node *next, *prior;	//前后结点 
}DBNODE, *DBNODEPTR, *DBLINKLIST;

//循环单向链表 原理同单链表 
//循环双向链表 原理同双向链表

//静态链表
#define SLEN 512	//静态链表长度 
typedef struct slink_node
{
	ElemType data;	//数据 
	int      next;	//指针 
}SNODE, *SLINKLIST;

/*静态链表是给没有指针的语言写的，C语言有指针，*
 *而且静态链表不实用，定义多而杂，因此不写了   */
 
//广义表
enum{ATOM,LIST};
typedef struct glist_node
{
	int tag;			//ATOM或LIST 
	union
	{
		ElemType           data;	//ATOM 
		struct glist_node *head; 	//LIST 
	}item;
	struct glist_node *next;		//结点 
}GLNODE, *GLIST;

//顺序栈
typedef struct
{
	ElemType *data;		//数据 
	int 	  top;		//栈顶 
	int 	  size;		//容量 
}SQSTACK;

//链式栈
typedef struct stack_node
{
	ElemType 		   data;	//数据 
	struct stack_node *next;	//结点 
}LSNODE, *LSNODEPTR, *LINKSTACK;

//顺序循环队列
typedef struct
{
	ElemType  *data;	//数据 
	int front, rear;	//队首与队尾 
	int size;			//容量 
}SQQUEUE;

//链式队列
typedef struct queue_node	//结点 
{
	ElemType data;
	struct queue_node *next;
}LQNODE, *LQNODEPTR;

typedef struct
{
	LQNODEPTR front, rear;	//队首与队尾 
}LKQUEUE;

#endif