有趣的算法题之机器人

小码哥与机器人

小码哥新买了一个机器人，但是这个机器人因为很便宜只能做三个动作。

三个动作: 前进 FD ，倒退 BK 和重复 REPEAT 。
FD 后加数字表示前进多少步；
BK 后加数字表示后退多少步；
REPEAT 后加数字再加方括号，表示重复方括号里的命令。
三个动作加的数字均为正整数。

命令的格式：
1. FD 与 BK 命令组合；
2. REPEAT 命令内加 REPEAT 命令与 FD 、BK 组合，且 REPEAT 排在最后。

原题链接：码题集OJ-小码哥与机器人 (matiji.net)

格式

输入格式：一行字符串（长度不超过 200 ）。

输出格式：表示最后得到的步数，表示离起点的距离（非负整数）。

样例

输入：REPEAT 5[ FD 50 REPEAT 10[FD 100]]

输出：5250

问题分析

要计算机器人在给定命令序列下的最终位置，我们需要按照命令的格式进行逐步解析。

假设输入的命令字符串是：FD 5 BK 3 REPEAT 2[FD 2 BK 1]

解析 FD 和 BK 命令

首先，机器人执行 FD 5 ，即前进 5 步。然后，机器人执行 BK 3 ，即后退 3 步。此时，机器人离起点的距离是 5 步（前进的步数）减去 3 步（后退的步数），等于 2 步。我们可以发现，单纯 FD 和 BK 命令的组合时，我们只要简单地对步数想加减就行。

解析 REPEAT 命令

接下来，机器人遇到 REPEAT 2[FD 2 BK 1 ]。这意味着机器人需要重复方括号内的命令两次。

在重复命令中，机器人执行 FD 2 ，前进 2 步，执行 BK 1 ，后退 1 步。因此该重复命令一次执行的步数为前进 1 步，我们在计算后需要存储该值。由于执行了两次，因此我们也需要对该命令的重复步数进行存储。

接着，我们再考虑 REPEAT 命令嵌套 REPEAT 命令的情况，我们可以发现简单地设置变量来存储重复命令的执行已经难以完成。因此，根据 REPEAT 命令的执行过程，我们可以采用递归的方式来进行模拟。这样在递归过程中的方法栈中，我们可以存储重复命令执行一次的步数以及重复命令的重复次数，之后再计算完后进行提交到上一个重复命令处即可。

计算总步数

将 REPEAT 命令内的步数累加到之前的步数上。由于 REPEAT 命令执行了两次，并且每次重复内部命令导致机器人前进了 1 步，因此总步数增加了 2 步。加上之前的 2 步，机器人总共前进了 4 步。因此，最终机器人离起点的距离是 4 步。

代码

java">import java.util.Scanner;
import java.util.*;class Main {static char[] cs; // 命令字符数组static int i = 0; // 命令位置索引// 主函数public static void main(String[] args) {Scanner input = new Scanner(System.in);String s = input.nextLine(); // 输入命令cs = s.toCharArray(); // 将字符串转为字符数组long ans = Math.abs(digui()); // 递归获取结果，对答案进行取绝对值System.out.println(ans);input.close();}// 递归计算public static long digui() {long num = 1; // 该层递归的乘数因子long cout = 0; // 该层命令行走的距离boolean isPost = true; // 确认命令方向的正负while (i < cs.length) {if (cs[i] == ' ') { // 当字符为空时跳过i++;}else if (cs[i] == 'F') { // 当命令为正向时，修改方向i+= 3; // 跳到数字所在的位置isPost = true; // 修改方向为正}else if (cs[i] == 'B') { // 当命令为负向时，修改方向i+= 3; // 跳到数字所在的位置isPost = false; // 修改方向为负}else if (cs[i] == 'R') { // 当命令为重复时，获取该命令要重复几次i+= 7; // 跳到数字所在位置num = getNum(); // 获取命令重复数字}else if (cs[i] == '[') { // 为左括号时，我们需要进入下一层递归来计算这个重复命令的步数和i++; // 跳过这个符号long res = digui(); // 进入下一层递归，获取该重复命令的步数和cout+= num*res; // 计算这个重复命令的总步数和}else if (cs[i] == ']') { // 为右括号时，说明该重复命令走完了，将步数和提交给上一层i++; // 跳过这个符号return cout; // 提交步数和}else if (cs[i] >= '0' && cs[i] <= '9') { // 当为数字时，获取整个数字if (isPost) { // 为正向时就加cout+= getNum();}else { // 为负向时则减cout-= getNum();}}}return cout; // 如果整个命令没有出现重复命令，则计算完后提交}// 获取整个数字的函数public static long getNum() {if (cs[i] >= '0' && cs[i] <= '9') {long num = cs[i] - '0'; // 取出该位数字// 如果后面还有位数，我们就将数字乘十，提高数字的位数while (i+1 < cs.length && cs[i+1] >= '0' && cs[i+1] <= '9') { num*= 10;i++;num+= cs[i] - '0';}i++; // 已经计算完数字，跳过数字的末尾return num; // 返回获取到的数字}else {return 0; // 如果不是数字则返回 1，在重复命令获取乘数因子时可能出现空格符号}}
}