Brainfuck语言实战

Brainfuck语言入门 https://blog.csdn.net/nameofcsdn/article/details/1102317301，加法用BF语言做加法，输入a+b，计算a+b=c，并输出c，假设a b c都是一位数（下同）看了百度百科上的代码：,>++++++[<-------->-],,[<+>-],<.>.感觉对于换行符的处理不太对，

csuzhucong

3910人浏览 · 2020-11-29 02:41:40

csuzhucong · 2020-11-29 02:41:40 发布

一，加减乘除

二，逻辑运算

三，SPOJ TEST

一，加减乘除

1，加法

用BF语言做加法，输入a+b，计算a+b=c，并输出c，假设a b c都是一位数（下同）

看了百度百科上的代码：

,>++++++[<-------->-],,[<+>-],<.>.

我最开始写的解释器是用cin接收一个字符，接收不了换行符，所以略改之后变成：

,>++++++[<-------->-],,[<+>-]<.>

运行示例：

后来觉得还是应该能输入换行符才对，这样才是完备的，所以又在末尾补上 ,. 得到

,>++++++[<-------->-],,[<+>-]<.>,.

改了解释器之后，运行：

2，减法

原理和加法一样

,>,,>++++++[<-------->-]<[<->-]<.>

运行示例：

改了解释器之后，运行,>,,>++++++[<-------->-]<[<->-]<.> ,.

3，乘法

,>,,>++++++++[<------<------>>-]<<
[>[>+>+<<-]>>[<<+>>-]<<<-]
>>>++++++[<++++++++>-]<.,.

4，除法

除法果然比乘法复杂很多很多，暂时不研究这个。

二，逻辑运算

1，整数转化成布尔值

简单版：

,[->[-]+<]>.

可视化版：

,>++++++[-<-------->]<
[->[-]+<]
>>++++++[-<++++++++>]<.

2，或

简单版：

,[->>[-]+<<]
>,[->[-]+<]
>.

可视化版：

,>++++++[-<-------->]<
[->>[-]+<<]
>,>>++++++[-<<-------->>]<<
[->[-]+<]
>>++++++[-<++++++++>]<.

3，且

简单版：

,>,<
[->[->[-]+<]<]
>>.

可视化版：

,>++++++[-<-------->]
,>++++++[-<-------->]
<<
[->[->[-]+<]<]
>>>++++++[-<++++++++>]<.

4，非

简单版：

,>+<
[->[-]<]>.

可视化版：

,>++++++[-<-------->]+<
[->[-]<]>
>++++++[-<++++++++>]<.

三，SPOJ TEST

SPOJ的TEST(题库第一题)

Life, the Universe, and Everything

Your program is to use the brute-force approach in order to find the Answer to Life, the Universe, and Everything. More precisely... rewrite small numbers from input to output. Stop processing input after reading in the number 42. All numbers at input are integers of one or two digits.

Example

Input:
1
2
88
42
99

Output:
1
2
88

Information

In case of any problems with your code, you can take a look in the forum, you'll find the answer, only for this problem, in various languages.

题意：

输入一串数，依次输出，直到42就停止。

思路一：

用乘法，把每相邻的2个字符都减掉48（0的ASCII码）就得到对应的数字值x和y，计算出x*10+y，再判断是不是42即可。

代码：

,>++++++[-<---- ---->]
>+
[
<,>[-]++++++[-<---- ---->]<<
[->>+++++ +++++>>+<<<<]
>[->+<<+>]
>>++++++[-<---- --->]
<[->[-]+<<+>]
<[->+<]
>>>>++++++[-<++++ ++++>]
<<[->.<]>[-]<<]

我在纸上转述了每一行是做什么的，这一行执行完之后指针停留的位置，以及那些格子有数（其他格子一定是0）

其中第8行的描述里面写的（）运算符指的是将整数转化成布尔值，即0变成0，非0变成1

然而提交运行的结果的rouya超时，于是我就肉眼debug + 测试

最后发现‘8’和‘\n’这2个字符的组合会让程序停止。

验证一下，ASCII码分别是56和10，分别减48就是8和-38，按照两位数组合起来就是8 * 10 + (-38) = 42

这也太巧了吧。。。

但是这也不至于导致超时啊，于是我把这个代码翻译成C++提交，果然是Wrong answer

思路二：

分开判断2个数，当相邻两个数分别是4和2的时候才停止

,>>+
[[-]
<,<
[->>+>+<<<]>>>
[-<<<+>>>]<<
[->>+>+<<<]>>>
[-<<<+>>>]<<
---------- ---------- ---------- ---------- ---------- -->
---------- ---------- ---------- ---------- ----------
[->[-]+<]<
[->[-]+<]>
[-<[-]+>]>[-<<[-]+>>]<<
[->+>+<<]>>
[-<<+>>]<
[-<<<.>>>]<<<[-]>
[-<+>]>
]

这次逻辑对了，然而提交的结果依然是超时，不知道为什么。

同样的，我把这个代码翻译成C++提交：

#include <iostream>
using namespace std;

void run()
{
    char arr[1000]={0};
    char *p = arr;
    *p=getchar();
p++;
p++;
*p = *p + 1;
while(*p){while(*p){*p = *p - 1;
};
p--;
*p=getchar();
p--;
while(*p){*p = *p - 1;
p++;
p++;
*p = *p + 1;
p++;
*p = *p + 1;
p--;
p--;
p--;
};
p++;
p++;
p++;
while(*p){*p = *p - 1;
p--;
p--;
p--;
*p = *p + 1;
p++;
p++;
p++;
};
p--;
p--;
while(*p){*p = *p - 1;
p++;
p++;
*p = *p + 1;
p++;
*p = *p + 1;
p--;
p--;
p--;
};
p++;
p++;
p++;
while(*p){*p = *p - 1;
p--;
p--;
p--;
*p = *p + 1;
p++;
p++;
p++;
};
p--;
p--;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
p++;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
*p = *p - 1;
while(*p){*p = *p - 1;
p++;
while(*p){*p = *p - 1;
};
*p = *p + 1;
p--;
};
p--;
while(*p){*p = *p - 1;
p++;
while(*p){*p = *p - 1;
};
*p = *p + 1;
p--;
};
p++;
while(*p){*p = *p - 1;
p--;
while(*p){*p = *p - 1;
};
*p = *p + 1;
p++;
};
p++;
while(*p){*p = *p - 1;
p--;
p--;
while(*p){*p = *p - 1;
};
*p = *p + 1;
p++;
p++;
};
p--;
p--;
while(*p){*p = *p - 1;
p++;
*p = *p + 1;
p++;
*p = *p + 1;
p--;
p--;
};
p++;
p++;
while(*p){*p = *p - 1;
p--;
p--;
*p = *p + 1;
p++;
p++;
};
p--;
while(*p){*p = *p - 1;
p--;
p--;
p--;
cout<<char(*p);
p++;
p++;
p++;
};
p--;
p--;
p--;
while(*p){*p = *p - 1;
};
p++;
while(*p){*p = *p - 1;
p--;
*p = *p + 1;
p++;
};
p++;
};

}

int main()
{
    run();
    return 0;
}

这个程序就通过了！

难道是我自己写的翻译器会忽略BF代码的隐藏BUG，然后我这个程序偏偏就有这个BUG导致超时，但是我翻译出来的C++代码却抹去了这个BUG？

于是我又自己写了个解释器：Brainfuck语言解释器_csuzhucong的博客-CSDN博客

把我这个代码放进去，运行结果还是好好的，并不会超时啊！

难道我的BF程序、翻译器、解释器都刚好有相配套的BUG？

思路三：

把思路二的逻辑稍微简化了一点：

,>>+
[[-]
<,<
[->>+>+<<<]>>>
[-<<<+>>>]<<
[->>+>+<<<]>>>
[-<<<+>>>]<<
---------- ---------- ---------- ---------- ---------- -->
---------- ---------- ---------- ---------- ---------- <
[->>[-]+<<]>[->[-]+<]>
[-<+<+>>]<
[-<<<.>>>]
<<<[-]>
[-<+>]>
]

居然！又双叒叕超时了，简直快怀疑人生了！

难道我的BF程序（思路二）、BF程序（思路三）、翻译器、解释器都刚好有相配套的BUG？

于是，我又用自己的解释器执行标程：

+[>>----------
[++++++++++<,----------]
>--------------------------------------------------
>----------------------------------------------------
>
[
<++++++++++++++++++++++++++++++++++++++++++++++++++++
<++++++++++++++++++++++++++++++++++++++++++++++++++
[>]<
[.<]++++++++++.---------->
[>]>>
]<
[++++++++++++++++++++++++++++++++++++++++++++++++++++
<++++++++++++++++++++++++++++++++++++++++++++++++++
[>]<
[.<]++++++++++.---------->
[>]>
]<
[>++++++++++++++++++++++++++++++++++++++++++++++++++++
<++++++++++++++++++++++++++++++++++++++++++++++++++
[>]<
[.<]++++++++++.---------->
[>]
]<
]

结果也没啥问题（说明我的档解释器没有明显BUG），但是格式略有差异：

而我的程序是：

到了这一步，无外乎就是四种情况：

（1）输入输出的问题，关于换行或者文件结尾的处理可能有问题

（2）我的BF程序（思路二）、BF程序（思路三）、翻译器、解释器都刚好有相配套的BUG

（3）标程有问题

（4）标程没问题但是OJ的解释器有问题，把我的程序解释错了

接下来，首先测试一下，用文件输入和控制台输入的差异、文件尾有没有换行或空行的差异

本地文件里面放：

测试结果：

我的程序读取控制台或者文件都正常，

标程读取文件运行不正常！

这里面涉及到2个差异：

（1）回车和换行符的差异导，控制台上的是回车键‘\13’文件中的是换行符‘\10’

（2）系统的差异，linux上的换行符LF和windows上的换行符CRLF不一样，所以标程在linux上读取文件应该没问题，在windows上读文件因为多了一个'\r'所以不会停止

这个解释和下面的行为是一致的：

标程好像很厉害，很严格，输入4242、4243、4342都不会停止，唯独输入42才停止。

虽然最终也没能AC，但是还是准备告一段落了，主要是BF语言没找到很标准的解释器，自己写的也不知道有没有BUG，而且SPOJ本来也不熟，之前从来没碰过，虽然听说很厉害但是说不准还是有问题呢？

不对！等一下！我再挣扎一下！

让我最后再看下matrix67的这个题的代码是怎么写的：

>>,>,
< <<++++++[>>--------<<-]>>---- [>>+>]<[<]> <<++++++[>>++++++++<<-]>>++++
> <<++++++[>>--------<<-]>>-- [>+>]<[<]>> <<++++++[>>++++++++<<-]>>++ >
[<<. [-]>[-<+>],>[-]<<
<<++++++[>>--------<<-]>>---- [>>+>]<[<]> <<++++++[>>++++++++<<-]>>++++
><<++++++[>>--------<<-]>>-- [>+>]<[<]>> <<++++++[>>++++++++<<-]>>++ >]

他在博客里面说，这个代码是AC的，然后我贴到自己的解释器里面执行，确实是对的，而且格式和我的一模一样：