如何使用堆栈添加大数？

Question

    class LargeNumberPb
{
    Stack s1;
    Stack s2;
    Stack res;
    string first;
    string second;

    public LargeNumberPb()
    {
         first = "10";
         second = "11";
         s1 = new Stack();
         s2 = new Stack();
         res = new Stack();
    }

    public void Fill()
    {
        for (int i = 0; i < first.Length; i++)
        {
            s1.Push(first.Substring(i,1));
        }
        for (int i = 0; i < second.Length; i++)
        {
            s2.Push(second.Substring(i,1));
        }
    }

    public Stack Sum()
    {
        for (int i = 0; i < s.Count; i++)
        {
            res.Push(Convert.ToInt32(s1.Pop()) + Convert.ToInt32(s2.Pop()));
        }
        return res;
    }
}

我想使用堆栈解决添加大量数字的问题。但它没有以正确的方式工作，如果两个数字是 100 和 11，那么进位会去哪里？

Answer 1

如果两个数字具有相同的位数，只需修复您的求和函数（仅处理进位，代码未测试）：

public Stack Sum()
{
    int carry = 0;
    int count = s1.Count;
    for (int i = 0; i < count; i++)
    {
        var result = Convert.ToInt32(s1.Pop()) + Convert.ToInt32(s2.Pop()) 
                     + carry;
        res.Push(result%10);
        carry = (result - result % 10)/10;
    }

    var carryStream = carry.ToString();
    for(int i=carryStream.Length-1;i>=0;i--)
    {
         res.push(Convert.ToInt32(carryStream.Substring(i,1);
    }
    return res;
}

编辑： 这是不同长度字符串的编辑版本：

        public Stack Sum()
        {
            int carry = 0;
            int count = Math.Min(s1.Count, s2.Count);
            for (int i = 0; i < count; i++)
            {
                var result = Convert.ToInt32(s1.Pop()) + Convert.ToInt32(s2.Pop())
                             + carry;
                res.Push(result % 10);
                carry = (result - result % 10) / 10;
            }

            var carryStream = carry.ToString();
            var remainedStack = s1.Count > 0 ? s1 : s2;
            carry = 0;
            for (int i = carryStream.Length - 1; i >= 0; i--)
            {
                var result = Convert.ToInt32(carryStream.Substring(i, 1)) 
             + (remainedStack.Count > 0 ? Convert.ToInt32(remainedStack.Pop()) : 0);
                res.Push(result % 10);
                carry = (result - result % 10) / 10;
            }

            if (remainedStack.Count > 0)
            {
                int remainedCount = remainedStack.Count;
                for (int i = 0; i < remainedStack.Count; i++)
                {
                    var result = carry + Convert.ToInt32(remainedStack.Pop());
                    res.Push(result % 10);
                    carry = (result - result % 10) / 10;
                }

            }

            if (carry != 0)
                res.Push(carry);

            return res;
        }

Answer 2

您只需要一个变量即可继续。当您从 stak 中弹出数字并将其相加时，如果有进位，则将该值分配给您拥有的额外变量。这就是你真正需要的。

public Stack Sum()
{
    int carry = 0 ;
    for (int i = 0; i < s.Count; i++)
    {
        int sum = Convert.ToInt32(s1.Pop()) + Convert.ToInt32(s2.Pop()) + carry;
        if(sum > 10) { carry = 1} else {carry = 0;} // you might want to check more than 10 here
         res.push(sum);
    }
    return res;
}