抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

洛谷P2027 bf

题意简述

编写 brainfuck 语言的解释器。

输入:

  • 给出一个字符串。
  • 字符串包含注释,代码和缓冲区。
  • 程序不会越界。
  • 程序不会死循环。
  • 循环有嵌套。

输出

  • 代码执行结果。

题目分析

代码分为两部分。

一、输入

首先读入代码部分,注意要过滤注释,读到 $ 就停止,过滤空格后读取缓冲区部分,最后过滤缓冲区后面的空格和 $

二、解释

定义 runcode 函数用来执行每个字符,返回值为 int 类型,表示下一个要执行的字符的下标。

首先解决没有循环的情况,这时将代码扫描一遍,将每个字符单独执行即可。

接下来解决循环,遇到字符 [ 时,判断是否结束循环,结束就跳转到对应的 ] 的下一个字符处执行,没结束就继续执行下一个字符。

遇到字符 ] 时,判断是否结束循环,结束就执行下一个字符,没结束就跳转到对应的 [ 处执行。

当然,直接寻找对应的中括号肯定会超时,所以需要预处理对应中括号的位置,这样就能直接跳转。

在输入的时候就可以预处理,用栈记录字符 [ 的位置,如果遇到字符 ] 就记录要跳转到的位置,然后弹出栈顶元素。

详情请见代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 233333;
char code[MAXN]; //储存代码
char tmp[MAXN]; //储存缓冲区内容
char mem[MAXN]; //模拟内存槽
char ch; //辅助读入字符
int s[MAXN]; //用来预处理循环跳转的栈
int l[MAXN]; // ]向左跳到的位置
int r[MAXN]; // [向右跳到的位置
int clen; //代码长度,用于输入
int tlen; //缓冲区长度,用于输入
int tp; //缓冲区指针,表示现在用到了哪
int sp; //栈s栈顶指针,用于预处理循环跳转
int p = 1; //内存槽指针
int runcode(const int &cp)
{
switch (code[cp])
{
case '+':
{
mem[p]++;
break;
} //将指针指向的数值加一
case '-':
{
mem[p]--;
break;
} //将指针指向的数值减一
case '<':
{
p--;
break;
} //指针指向的地址减一
case '>':
{
p++;
break;
} //指针指向的地址加一
case '.':
{
putchar(mem[p]);
break;
} //输出指针指向的数值
case ',':
{
if (tp > tlen) //缓冲区为空送入-1
mem[p] = -1;
else //送入一个字符
mem[p] = tmp[++tp];
break;
} //替换指针指向的数值
case '[':
{
if (mem[p] == 0) //为0就向右跳转,跳出循环
return r[cp] + 1;
break;
}
case ']':
{
if (mem[p] != 0) //指针指向的值不为0,重复执行
return l[cp]; //跳到循环左侧重新开始循环
break;
}
}
return cp + 1; //执行下一个字符的代码
}
int main()
{
ch = ' ';
while (ch != '$')
{
ch = getchar();
if (ch == '.' or ch == ',' or ch == '<' or ch == '>' or
ch == '+' or ch == '-' or ch == '[' or ch == ']')
{
code[++clen] = ch;
}
else
{
continue;
} //过滤注释
if (ch == '[')
{
s[++sp] = clen;
} //如果是[就入栈并记录下标
else if (ch == ']')
{
r[s[sp]] = clen; //记录向右跳到的位置
l[clen] = s[sp]; //记录向左跳到的位置
sp--; //弹出栈顶元素
} //匹配对应的中括号
} //读入代码
ch = getchar(); //过滤第一个$后面的空格
while (ch != '$')
{
ch = getchar();
tmp[++tlen] = ch;
} //读入缓冲区
tmp[tlen--] = 0; //过滤缓冲区后的$
tmp[tlen--] = 0; //过滤缓冲区后的空格
for (int i = 1; i <= clen; i = runcode(i)); //运行代码直到完成
return 0;
}