c - 使用类似堆栈的数组将两个数字相加

Question

例如，如果我想添加 20 + 15，我需要有两个数组:

a = {2, 0}
b = {1, 5}

我应该得到以下数组作为结果:

outcome = {3, 5} // or {5, 3} and read it in reverse order

困难的部分是我只能使用这些数组的第一个元素，以便它们表现得像堆栈。

在我的示例中，它相对容易，但如果有像 {1, 0, 0, 0} + {5} 这样的数字怎么办？或者 {9, 9} + {9, 9}？

我真的找不到一种特定的方法来执行此操作，更不用说我找不到任何方法来解决 {1, 0, 0, 0} + {5}。

C 标签在这里是因为我实际上需要用 C 语言编写这个东西，但是欢迎任何关于解决方案的想法(我的意思是描述，不一定是 C 程序)。

Answer 1

反转数字，使最低有效数字在前，最高有效数字在最后。加法算法从最低到最高有效。

a = {0, 0, 0, 1}
b = {5}

添加这些数字现在应该很简单了。从每个中弹出一个数字，将它们相加，并将结果插入结果堆栈。

a = {9, 9}
b = {9, 9}

要处理 99 + 99，您需要跟踪进位。那将是您存储的一个额外变量，它不会进入任何一个堆栈。弹出 9 和 9，将它们相加得到 18。将 8 压入结果堆栈并存储进位。

a = {9}
b = {9}
outcome = {8}
carry = 1

现在弹出接下来的两位数字 9 和 9，并将它们相加得到 18。加上进位数字得到 19。将 9 压入结果堆栈并再次跟踪进位。

a = {}
b = {}
outcome = {9, 8}
carry = 1

现在输入堆栈上没有数字了，所以最后将最后一个进位数字压入输出堆栈。

outcome = {1, 9, 8}