Сложите два числа, представленных стеками

Опубликовано: 8 Января, 2022

Учитывая два числа N 1 и N 2, представленные двумя стеками, так что их самые значащие цифры находятся внизу стека, задача состоит в том, чтобы вычислить и вернуть сумму двух чисел в форме стека.

Примеры:

Input: N1={5, 8, 7, 4}, N2={2, 1, 3} 
Output: {6, 0, 8, 7}
Explanation:
Step 1: Popped element from N1(= 4) +  Popped element from N2(= 3) = {7} and rem=0.
Step 2: Popped element from N1(= 7) +  Popped element from N2(= 1) = {7, 8} and rem=0.
Step 3: Popped element from N1(= 8) +  Popped element from N2(= 2) = {7, 8, 0} and rem=1.
Step 4: Popped element from N1(= 5) = {7, 8, 0, 6}
On reverse the stack, the desired arrangement {6,0,8,7} is obtained.

Input: N1={6,4,9,5,7}, N2={213} 
Output:{6, 5, 0, 0, 5}

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: Проблема может быть решена с помощью концепции сложения двух чисел, представленных связными списками. Выполните следующие шаги, чтобы решить проблему.

  1. Создайте новый стек, res для хранения суммы двух стеков.
  2. Инициализируйте переменные rem и sum для хранения сгенерированного переноса и суммы верхних элементов соответственно.
  3. Продолжайте выталкивать верхние элементы обоих стеков, переместите сумму% 10 в res и обновите rem как sum / 10 .
  4. Повторяйте вышеуказанный шаг, пока стопки не станут пустыми. Если rem больше 0 , вставить rem в стек.
  5. Переверните стек res так, чтобы самая значимая цифра находилась внизу стека res.

Below is the implementation of the resultant approach:

C++14

// C++ program to implement 
// the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to return the stack that
// contains the sum of two numbers
stack<int> addStack(stack<int> N1, 
                    stack<int> N2)
{
    stack<int> res;
    int sum = 0, rem = 0;
  
    while (!N1.empty() and !N2.empty()) {
        
      // Calculate the sum of the top
      // elements of both the stacks
        sum = (rem + N1.top() + N2.top());
        
      // Push the sum into the stack
        res.push(sum % 10);
        
      // Store the carry
        rem = sum / 10;
        
      // Pop the top elements
        N1.pop();
        N2.pop();
    }
    
    // If N1 is not empty
    while (!N1.empty()) {
        sum = (rem + N1.top());
        res.push(sum % 10);
        rem = sum / 10;
        N1.pop();
    }
    // If N2 is not empty
    while (!N2.empty()) {
        sum = (rem + N2.top());
        res.push(sum % 10);
        rem = sum / 10;
        N2.pop();
    }
  
    // If carry remains
    while (rem > 0) {
        res.push(rem);
        rem /= 10;
    }
  
    // Reverse the stack.so that
    // most significant digit is
    // at the bottom of the stack
    while (!res.empty()) {
        N1.push(res.top());
        res.pop();
    }
    res = N1;
    return res;
}
  
// Function to display the 
// resultamt stack
void display(stack<int>& res)
{
    int N = res.size();
    string s = "";
    while (!res.empty()) {
        s = to_string(res.top()) + s;
        res.pop();
    }
      
  cout << s << endl;
}
  
// Driver Code
int main()
{
    stack<int> N1;
    N1.push(5);
    N1.push(8);
    N1.push(7);
    N1.push(4);
  
    stack<int> N2;
    N2.push(2);
    N2.push(1);
    N2.push(3);
  
    stack<int> res = addStack(N1, N2);
  
    display(res);
    
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.Stack;
class GFG{
  
    // Function to return the stack that
    // contains the sum of two numbers
    static Stack<Integer> addStack(Stack<Integer> N1,
                                   Stack<Integer> N2)
    {
        Stack<Integer> res = new Stack<Integer>();
        int sum = 0, rem = 0;
        while (!N1.isEmpty() && !N2.isEmpty()) 
        {
  
            // Calculate the sum of the top
            // elements of both the stacks
            sum = (rem + N1.peek() + N2.peek());
  
            // Push the sum into the stack
            res.add(sum % 10);
  
            // Store the carry
            rem = sum / 10;
  
            // Pop the top elements
            N1.pop();
            N2.pop();
        }
  
        // If N1 is not empty
        while (!N1.isEmpty()) 
        {
            sum = (rem + N1.peek());
            res.add(sum % 10);
            rem = sum / 10;
            N1.pop();
        }
          
          // If N2 is not empty
        while (!N2.isEmpty()) 
        {
            sum = (rem + N2.peek());
            res.add(sum % 10);
            rem = sum / 10;
            N2.pop();
        }
  
        // If carry remains
        while (rem > 0) 
        {
            res.add(rem);
            rem /= 10;
        }
  
        // Reverse the stack.so that
        // most significant digit is
        // at the bottom of the stack
        while (!res.isEmpty()) 
        {
            N1.add(res.peek());
            res.pop();
        }
        res = N1;
        return res;
    }
  
    // Function to display the
    // resultamt stack
    static void display(Stack<Integer> res)
    {
        int N = res.size();
        String s = "";
        while (!res.isEmpty()) 
        {
            s = String.valueOf(res.peek()) + s;
            res.pop();
        }
  
        System.out.print(s + " ");
    }
  
    // Driver Code
    public static void main(String[] args)
    {
        Stack<Integer> N1 = new Stack<Integer>();
        N1.add(5);
        N1.add(8);
        N1.add(7);
        N1.add(4);
          Stack<Integer> N2 = new Stack<Integer>();
        N2.add(2);
        N2.add(1);
        N2.add(3);
          Stack<Integer> res = addStack(N1, N2);
          display(res);
    }
}
  
// This code is contributed by shikhasingrajput

Python3

# Python3 program to implement
# the above approach
  
# Function to return the stack that 
# contains the sum of two numbers
def addStack(N1, N2):
  
    res = []
    s = 0
    rem = 0
  
    while (len(N1) != 0 and len(N2) != 0):
  
        # Calculate the sum of the top
        # elements of both the stacks
        s = (rem + N1[-1] + N2[-1])
  
        # Push the sum into the stack
        res.append(s % 10)
  
        # Store the carry
        rem = s // 10
  
        # Pop the top elements
        N1.pop(-1)
        N2.pop(-1)
  
    # If N1 is not empty
    while(len(N1) != 0):
        s = rem + N1[-1]
        res.append(s % 10)
        rem = s // 10
        N1.pop(-1)
  
    # If N2 is not empty
    while(len(N2) != 0):
        s = rem + N2[-1]
        res.append(s % 10)
        rem = s // 10
        N2.pop(-1)
  
    # If carry remains
    while(rem > 0):
        res.append(rem)
        rem //= 10
  
    # Reverse the stack.so that
    # most significant digit is
    # at the bottom of the stack
    res = res[::-1]
  
    return res
  
# Function to display the
# resultamt stack
def display(res):
  
    s = ""
    for i in res:
        s += str(i)
  
    print(s)
  
# Driver Code
N1 = []
N1.append(5)
N1.append(8)
N1.append(7)
N1.append(4)
  
N2 = []
N2.append(2)
N2.append(1)
N2.append(3)
  
# Function call
res = addStack(N1, N2)
  
display(res)
  
# This code is contributed by Shivam Singh

C#

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
  
class GFG{
  
// Function to return the stack that
// contains the sum of two numbers
static Stack<int> PushStack(Stack<int> N1,
                            Stack<int> N2)
{
    Stack<int> res = new Stack<int>();
    int sum = 0, rem = 0;
      
    while (N1.Count != 0 && N2.Count != 0) 
    {
  
        // Calculate the sum of the top
        // elements of both the stacks
        sum = (rem + N1.Peek() + N2.Peek());
  
        // Push the sum into the stack
        res.Push((int)sum % 10);
  
        // Store the carry
        rem = sum / 10;
  
        // Pop the top elements
        N1.Pop();
        N2.Pop();
    }
  
    // If N1 is not empty
    while (N1.Count != 0) 
    {
        sum = (rem + N1.Peek());
        res.Push(sum % 10);
        rem = sum / 10;
        N1.Pop();
    }
      
    // If N2 is not empty
    while (N2.Count != 0) 
    {
        sum = (rem + N2.Peek());
        res.Push(sum % 10);
        rem = sum / 10;
        N2.Pop();
    }
  
    // If carry remains
    while (rem > 0) 
    {
        res.Push(rem);
        rem /= 10;
    }
  
    // Reverse the stack.so that
    // most significant digit is
    // at the bottom of the stack
    while (res.Count != 0) 
    {
        N1.Push(res.Peek());
        res.Pop();
    }
      
    res = N1;
    return res;
}
  
// Function to display the
// resultamt stack
static void display(Stack<int> res)
{
    int N = res.Count;
    String s = "";
      
    while (res.Count != 0) 
    {
        s = String.Join("", res.Peek()) + s;
        res.Pop();
    }
  
    Console.Write(s + " ");
}
  
// Driver Code
public static void Main(String[] args)
{
    Stack<int> N1 = new Stack<int>();
    N1.Push(5);
    N1.Push(8);
    N1.Push(7);
    N1.Push(4);
      
    Stack<int> N2 = new Stack<int>();
    N2.Push(2);
    N2.Push(1);
    N2.Push(3);
      
Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023
Введение в связанный список — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Введение в массивы — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Как подготовиться к ICFP или Международной конференции по функциональному программированию?
12 Декабря, 2022