1

因此，例如，如果我想添加 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 程序）。

4

3 回答 3

3

颠倒数字，使最不重要的数字在第一位，最重要的数字在最后。加法算法从最不重要到最重要。

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}
于 2013-04-13T15:46:33.770 回答
1

试试这个（未经测试）（更新为处理携带）：

Stack Add(Stack a, Stack b, bool carry) {
  if (a.Empty && b.Empty) return (carry ? a.Push(1) : a);
  int c = (a.Empty ? 0 : a.Pop)
        + (b.Empty ? 0 : b.Pop)
        + (carry ? 1 : 0);
  if (c>=10) 
    return Add(a,b,true).Push(c-10)
  else
    return Add(a,b,false).Push(c);
}

当然，它隐含地使用函数调用堆栈以及a和b。

于 2013-04-13T15:43:32.113 回答
1

我认为您最大的希望是这样的算法：

pop digits from stack a and compute number n1
pop digits from stack b and compute number n2
add n1 and n2 giving n3
push digits from n3 onto stack outcome

如果做不到这一点，您必须知道每个堆栈中有多少个数字，a并且b，以便您可以正确对齐它们。

另一种但不太直观的表示也可以提供帮助：

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

c = { 0, 0, 0, 1 }
d = { 5 }

首先存储最低有效位。现在，您可以根据需要从堆栈的前面开始添加和携带。

于 2013-04-13T15:49:47.320 回答