Как добавить большое число со стеком?

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

Вам нужна только одна переменная для продолжения. Пока вы извлекаете числа из ставок и добавляете их, если есть перенос, вы присваиваете это значение дополнительной переменной, которая у вас есть. Это все, что вам нужно на самом деле.

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;
}