在 Java 中使用堆栈进行长减法的（递归或非递归）算法的示例是什么？

Question

我以前问过这个问题，但方式更复杂，我想我可能没说清楚。

假设我有两堆整数，每个整数代表一个整数，从一个字符串中解析出来。每个中的第一个是 1 的位置，第二个是 10 的位置，第三个是 100 的位置，等等。我很难解决这个问题，因为我觉得我需要递归地做，递归算法让我困惑，尤其是在这种情况下。感谢您的帮助。

int difference, z;
for (i = 0; i < length; i++)
{
  x = firstNum.pop();
  y = secondNum.pop();
  difference = x - y;
  if (difference < 0)
  {
    z = firstNum.pop();
    firstNum.push(z - 1);
    firstNum.push(x + 10);
  }
  else
  {
    result.push(difference);
  }
}

Answer 1

你不需要递归但是你有一个错误。

int difference, z;
while (!firstNum.isEmpty ())
{
  x = firstNum.pop();
  y = 0;
  if (!secondNum.isEmpty ()) // account for the case when secondNum has less digits
    y = secondNum.pop();
  difference = x - y;
  if (difference < 0)
  {
    z = firstNum.pop();
    firstNum.push(z - 1);
    result.push(difference + 10); // fixed this line, since you want to push the
                                  // difference to the result
  }
  else
  {
    result.push(difference);
  }
}

现在，您应该注意到 result 堆栈中的数字将以相反的顺序排列。在减法结束时，最高有效位将位于堆栈的顶部。

这是一个带有硬编码示例输入的完整方法：

  public static void subtract ()
  {
    Stack<Integer> firstNum = new Stack<Integer>();
    Stack<Integer> secondNum = new Stack<Integer>();
    Stack<Integer> result = new Stack<Integer>();

    // firstNum == 3002
    firstNum.push (3);
    firstNum.push (0);
    firstNum.push (0);
    firstNum.push (2);

    // secondNum == 129
    secondNum.push (1);
    secondNum.push (2);
    secondNum.push (9);

    int difference, z;
    while (!firstNum.isEmpty ())
    {
      int x = firstNum.pop();
      int y = 0;
      if (!secondNum.isEmpty ())
        y = secondNum.pop();
      difference = x - y;
      if (difference < 0)
      {
        z = firstNum.pop();
        firstNum.push(z - 1);
        result.push(difference + 10);
      }
      else
      {
        result.push(difference);
      }
    }
    while (!result.isEmpty ())
      System.out.print (result.pop ());
    System.out.println ();
  }

输出

请注意，此方法假定第一个数字大于第二个数字。对于第一个数字较小的情况，应该添加一些处理。

在 Java 中使用堆栈进行长减法的（递归或非递归）算法的示例是什么？

What would be an example of a (either recursive or not) algorithm used to do long subtraction using stacks in Java?

java

algorithm

recursion

stack