使用递归将二进制数字字符串转换为十进制数

Question

计算机科学教授在我们的作业中给了我们一个问题...我不确定该如何继续下去，我写的代码似乎非常失败。以下是问题描述：

---

(二进制转十进制)编写一个递归方法，将二进制字符串解析为十进制整数。该方法的头部是:

public static String bin2Dec(String binaryString)

编写一个测试程序，提示用户输入一个二进制字符串，并显示其对应的十进制数。

---

非常感谢任何帮助。以下是我的代码：

import java.util.Scanner;

public class HW04_P5 {
    static int index = 0;
    static int power = 0;
    static int number = 0;
    static boolean exit = false;

    @SuppressWarnings("resource")
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        System.out.print("  Enter a binary number to convert to decimal: ");
        String in = scan.nextLine();
        index = in.length()-1;
        System.out.print("  Binary number converted to decimal:          "+bin2Dec(in));
    }

    public static String bin2Dec(String in)
    {
        if((in.substring(index,index+1).equals("1"))&&(index>0))
        {
            number += Math.pow(2,power);
            System.out.print(number);
            power++;
            index--;
            bin2Dec(in);
        }
        else if((in.substring(index,index+1).equals("0"))&&(index>0))
        {
            power++;
            index--;
            bin2Dec(in);
        }
        System.out.print(number);
        return "";
    }
}

- squeeler642

---

看起来你已经接近成功了，但是为了简化，我建议只需查看字符串的最后一位数字，然后将 in 字符串的子字符串传递给 bin2Dec 函数即可。也就是说，不需要使用 index。 - Scary Wombat

你得到了什么输出或错误信息？ - Scary Wombat

Answer 1

不需要多余的变量索引、幂和p，从右到左处理字符串更简洁。你也不希望在递归函数外跟踪"全局"变量number……这会令人困惑和奇怪。在我看来，你希望所有状态都在递归函数内部传递。即使有这些限制，你仍然可以在基本上两行代码中完成：

public static int bin2Dec(String s) {
  if (s == null || s.isEmpty()) return 0;
  else return s.charAt(s.length()-1)-48+2*bin2Dec(s.substring(0,s.length()-1));
}

这可能不是最清晰的解决方案，但我认为它是最优雅的。通过将else子句分成几行可以提高清晰度。48是Unicode字符0的编号，这也许不是将字符'0'和'1'转换为它们各自的数字的最佳方式。

- Edward Doolittle

---

这个完美地运行了。一开始我有点难以理解这段代码，但这对我理解如何压缩/简化代码非常有帮助。再次感谢你的提示。 - squeeler642

Answer 2

首先：您正在在if条件中打印数字，而且没有使用\n。您得到的输出将会在多个调用中打印数字。

其次，条件index > 0应该是index >= 0，否则您将错过第0个索引的测试。并且该条件应该在&&之前，而不是之后。

第三，从该方法返回number，而不是在那里打印它。

这是带有上述更改的修改后的方法：

public static String bin2Dec(String in) {
    if ((index >= 0) && (in.substring(index, index + 1).equals("1"))) {
      number += Math.pow(2, power);
      power++;
      index--;
      bin2Dec(in);
    } else if ((index >= 0) && (in.substring(index, index + 1).equals("0"))) {
      power++;
      index--;
      bin2Dec(in);
    }
    return "" + number;
}

然而，我仍然看到很多重复的地方。你可以使用String#charAt()方法，而不是substring()，因为你实际上只是检查单个字符。这是你的方法的简化版本：

public static String bin2Dec(String in) {
    if (index < 0) {
      return "" + number;
    }
    if (in.charAt(index) == '1') {
      number += Math.pow(2, power);
    }
    power++;
    index--;
    return bin2Dec(in);
}

- Rohit Jain

Answer 3

首先，定义一个带有位置参数的private版本。

private static int bin2Dec(String in, int p) {
    if (in == null || in.isEmpty() || p >= in.length()) {
        return 0;
    }
    int s = (in.charAt(p) == '1' ? 1 : 0) << in.length() - p - 1;
    return s + bin2Dec(in, p + 1);
}

请注意，我们首先定义一个停止条件，然后确定该位置处的字符是否为1，然后向左移动String的长度（减去该位置和减一，因为Java使用零基索引）。然后递归将该值添加到返回值中。最后，public方法只是这样的。

public static int bin2Dec(String in) {
    return bin2Dec(in, 0);
}

- Elliott Frisch