上SICP的时候樾哥提到了一个叫图灵完备的概念，啥是图灵完备呢？简单说就是能模拟图灵机的所有操作的语言就可以说是图灵完备的，它的计算能力和图灵机至少是等价的
然后有这么一个很小的语言Brainfuck，它有一个类似射线的有格纸带，一个可以任意移动的指针
规定，"<"、">"、","、"."、"+"、"-"分别表示左移、右移、读入、输出、增加1、减少1，这个做起来是很简单的
然后是"["和"]"，其等价于 while (pointer->value != 0) {do sth...}
要实现这个操作只需要用一个栈记录所有的左括号就可以了。纸带等价于一个双向链表，这些都不是很难写。

特意用C写了这个东西，把自己实现的stack和list放在了两个.h文件里，学到很多.jpg
关于.h文件的用法还没有很好的掌握，这里先不管了…

这里附赠几个个小程序，有一些是自己写的，可能有更好的写法

// ,>,[-<+>] // a plus b
// ,>,[-<->] // a minus b
// ,>>,<<[->>[-<+>>+<]>[-<+>]<<<]>. //a times b
// ++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>. // Hello World!


// BFcompiler.c
#include <stdio.h>
#include <string.h>
#include "stack.h"
#include "list.h"

#define MAX_LENGTH 200005

char seq[MAX_LENGTH];

int FindNextPos(char *s, int pos) {
	for (; s[pos] != ']'; ) pos ++;
	return pos;
}

int main(void) {
	scanf("%s", seq);
	int len = strlen(seq);
	Node* current_pointer = (Node*) malloc(sizeof(Node));
	NodeInit(current_pointer);
	Stack* stack = (Stack*) malloc(sizeof(Stack));
	StackInit(stack);
	for (int i = 0; i < len; ++ i) {
		switch (seq[i]) {
			case '+': {
				add(current_pointer, 1);
				break;
			}
			case '-': {
				add(current_pointer, -1);
				break;
			}
			case '>': {
				moveRight(&current_pointer);
				break;
			}
			case '<': {
				moveLeft(&current_pointer);
				break;
			}
			case ',': {
				scanf("%d", &(current_pointer->value));
				break;
			}
			case '.': {
				printf("%d", current_pointer->value);
				break;
			}
			case '[': {
				if (current_pointer->value != 0) {
					StackPush(stack, i);
				} else {
					i = FindNextPos(seq, i);
				}
				break;
			}
			case ']': {
				if (current_pointer->value != 0) {
					i = StackTop(stack);
				} else {
					StackPop(stack);
				}
				break;
			}
		}
	}
	return 0;
}

// stack.h
#ifndef STACK_HEADER_FILE
#define STACK_HEADER_FILE

#include <stddef.h>
#include <stdlib.h>

#define INF 0x3f3f3f3f

typedef struct tmpStackNode {
	struct tmpStackNode *next;
	int value;
} StackNode;

typedef struct {
	StackNode *top;
	int size;
} Stack;

void StackNodeInit(StackNode *p) {
	p->next = NULL;
	p->value = 0;
}

void StackInit(Stack *stack) {
	stack->top = (StackNode*) malloc(sizeof(StackNode*));
	StackNodeInit(stack->top);
	stack->size = 0;
}

void StackPush(Stack *stack, int value) {
	StackNode *tmp = (StackNode*) malloc(sizeof(StackNode));
	StackNodeInit(tmp);
	tmp->value = value;
	tmp->next = stack->top;
	stack->top = tmp;
	stack->size += 1;
}

void StackPop(Stack *stack) {
	if (stack->size < 1) return ;
	StackNode *tmp = stack->top;
	stack->top = stack->top->next;
	stack->size -= 1;
	free(tmp);
	tmp = NULL;
}

int StackTop(Stack *stack) {
	if (stack->size < 1) return INF;
	return stack->top->value;
}

#endif


// list.h
#ifndef LIST_HEADER_FILE
#define LIST_HEADER_FILE

#include <stddef.h>
#include <stdlib.h>

#define INF 0x3f3f3f3f

typedef struct tmpNode {
	struct tmpNode *next, *prev;
	int value;
} Node;

void NodeInit(Node *p) {
	p->next = p->prev = NULL;
	p->value = 0;
}

void add(Node *p, int value) {
	p->value += value;
}

void moveLeft(Node **p) {
	if ((*p)->prev == NULL) return ;
	(*p) = (*p)->prev;
}

void moveRight(Node **p) {
	if ((*p)->next == NULL) {
		(*p)->next = (Node*) malloc(sizeof(Node));
		NodeInit((*p)->next);
		(*p)->next->prev = (*p);
	}
	(*p) = (*p)->next;
}

#endif