使用堆栈将十进制转换为二进制，但不确定输入本身应该如何是堆栈

Question

我不明白如何从堆栈中弹出整数并将其转换为二进制的概念。

我成功创建了一个程序，它可以接受一个整数，并通过使用堆栈将其推入数组来将其转换为二进制，但我不确定如何使我的输入本身成为一个堆栈，我可以在堆栈中弹出每个整数，然后将它们推入数组以将其更改为二进制。

class ArrayStack: #puts in and removes from the top only
    def __init__(self):
        self._data = [ ]

    def __len__(self):
        return len(self._data)
    
    def is_empty(self):
        return len(self._data) == 0
    
    def push(self, e):
        self._data.append(e)

    def top(self):
        if self.is_empty( ):
            raise Exception("No Elements in Stack")
        return self._data[-1]
    
    def pop(self):
        if self.is_empty( ):
            raise Exception("No Elements in Stack")
        return self._data.pop() 
    

def decToBin(num):
    stack = ArrayStack()
    while num > 0:
        remainder = num % 2
        stack.push(remainder)
        num = num // 2

    _str = ''
    while not stack.is_empty():
        Bin = stack.pop()
        _str = _str + str(Bin)
    return int(_str)

if __name__ == "__main__":
    print(decToBin(65536))

Answer 1

看起来您想使用堆栈来解决顺序相反的问题：您的第一个循环按从最低有效位到最高有效位的顺序获取位，而最简单的方法是用最高有效位中的数字构建结果数- 从显着到最不显着。我猜你随后想到了堆栈...

您不需要为此使用堆栈。

相反，请跟踪您希望输入中的当前位表示的 10 次方。例如，如果输入是 11，二进制为 1011，则翻译如下：

    1011    power
    │││└─ * 1    =    1
    ││└── * 10   =   10   
    │└─── * 100  =    0
    └──── * 1000 = 1000
                       ────── +
                       1011

您的第一个循环将从右到左访问位，即如果我们查看此可视化的右侧，则从上到下访问位。您会注意到，您只需要在第一个循环中保持更新 power 并在当前位为 1 时将其添加到结果中。

不是你的问题，而是：

• 我发现这个名字

  decToBin

  令人困惑。输入没有任何小数。输入是一个整数。如何表示是另一回事，但它并不是“本质上”的十进制整数。我会建议一个更好的名字，比如也许bitsToPowersOf10：

您的解决方案将数字转换为字符串（使用
• str()

  ），然后再转换回数字（使用

  int()

  ）。但是，如果您允许在该过程中涉及字符串，那么您就不需要循环，并且可以在您的函数中使用这个单行代码：return int(bin(num)[2:])

  但我猜练习的目的是在不转换为字符串的情况下实现它。

以下是如何实现上面给出的模式：

def bitsToPowersOf10(num):
    result = 0
    power_of_10 = 1
    while num > 0:
        if num % 2:
            result += power_of_10
        power_of_10 *= 10  # The essence!
        num //= 2
    return result
    
print(bitsToPowersOf10(11))  # 1011