P2027 bf 题解

CleanIce · 2023-12-06 16:31:14 · 题解

P2027 bf 题解

原题链接。

原题简述

一看就是模拟题，让我们写一个 BF 语言的解释器。给我们提供了容量为 30000 字节的内存，全部初始化为 0。还有内存指针，指向内存开始的位置。

然后说代码的字符集及其含义。这里进行了整理和修改，应该更好理解：

就是这么些简单的字符，实现也非常简单。但 BF 语言并不简单，它甚至达到了高级编程语言的基本标准：图灵完备。这里是题外话就不展开了。

然后说输入的数据格式为：

代码$ 输入流 $

注意空格的位置。输入流与左右两个 $ 符号之间有一个空格，但代码与第一个 $ 之间并没有！读入的时候需要注意。

另外，题目中说到的“代码中有注释”，注释指的是代码中除了上述字符集内字符之外的所有字符（不包括 $）。因此我们需要忽略它们。

下面来想想思路。

做题思路

先设几个变量，方便讲述（为了使使用其他语言的读者看懂，此处不考虑指针操作）：

我们假设内存条越往右地址越大，初始地址为 0。

那么，我们一个个看字符集中的代码该如何处理：

1. > 右移操作符：将当前内存地址增加一。也就是：\text{addr} \gets \text{addr} + 1。
2. < 左移操作符：将当前内存地址减少一。也就是：\text{addr} \gets \text{addr} - 1。
3. + 自增操作符：将存储在当前内存的值加一。也就是：\text{mem} \gets \text{mem} + 1。
4. - 自减操作符：将存储在当前内存的值减一。也就是：\text{mem} \gets \text{mem} - 1。
5. , 输入操作符：从输入流读入一个字符，并存储到当前内存位置。如果输入流没有更多字符，存入 -1。也就是：\text{mem} \gets \begin{cases} \text{input} & \text{input} \ne \varnothing \\ -1 & \text{input} = \varnothing \end{cases}，随后令 \text{input} \gets \text{下一个输入流中的字符}。
6. . 输出操作符：将存储在当前内存的值按照 ASCII 表作为字符输出。也就是输出 \text{mem}。

接下来就是比较难的两个。上面在将字符集的时候说，就是跳到配对的目标括号。如何寻找配对的括号呢？

且看这一段字符：

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

很明显，如果我们要找到第一个 [ 配对的字符，就是第三个 ]，第二个 [ 就是第二个 ]。

只要记录一共遇到了几个 [ 和几个 ] 就行了。也就是说，寻找第一个 [ 配对的符号时，还会遇到两个 [，找到两个 ] 并忽略后，第三个 ] 就是配对的了。寻找第二个 [ 配对的符号时，还会遇到一个 [，找到一个 ] 并忽略后，第二个 ] 就是配对的了。因此，写出伪代码：

// 伪代码
// count 为需要寻找的个数
count <- 1
ch <- #当前字符#
while (count != 0):
    if ch = '[':
        count <- count + 1
    elseif ch = ']':
        count <- count - 1
    ch <- #下一个字符#
ch <- #回退到上一个字符#
// 此时 ch 就是配对的 ]

] 符号同理，不再重复。

代码专区

我提供了现代化 C++ 代码和传统的 OI 代码。对于洛谷少数的程序设计人员（或非竞赛选手），可以看现代化的代码。对于 oiers，可以尝试阅读现代化代码，或者就直接看传统 OI 型的代码。两份代码都给了注释，其中现代化代码还给了技术注释。两份代码效率差不多（现代化的我测了一下可能还快一些）。

现代化代码使用了 C++23 的新特性，因此洛谷上提交不了（可能你也运行不了）。你可以根据我的注释修改为 C++20 以内的代码使用，当然也可以提交。

传统 OI 代码就给你们自己看吧。

由于代码长度比较长，我把它放到剪贴板里了。

代码在这里