Posted on by Kalkicode
Code Stack

Add two numbers represented by stack

The task is to add two numbers represented by two stacks. Each stack represents a number in reverse order, i.e., the least significant digit is at the top of the stack.

Problem Statement

Given two stacks s1 and s2, where each stack represents a number, the task is to add these two numbers and store the result in s1.

Example

Consider the following two stacks:

s1:  9 8 9
s2:  4 2 8

The numbers represented by s1 and s2 are 988 and 824, respectively. The result of adding these two numbers is 1812, which will be stored in s1.

Idea to Solve the Problem

To add two numbers represented by two stacks, we can follow the following approach:

  1. Create a new stack result to store the sum of the two numbers.
  2. Initialize a variable remainder to 0 to keep track of the carry while performing the addition.
  3. Iterate through both stacks s1 and s2 until either of them becomes empty: a. If both s1 and s2 are not empty, compute the sum of the top elements of both stacks along with the remainder. b. If either s1 or s2 becomes empty, consider only the non-empty stack and add it to the remainder. c. Calculate the digit to be stored in the result stack as the sum modulo 10 and update the remainder as the sum divided by 10. d. Pop the top elements of s1 and s2. e. Push the calculated digit into the result stack.
  4. After the iteration, if there is any remaining remainder, add it to the result stack.
  5. Put the elements from the result stack back into s1 to store the final result.

Pseudocode

Function addNumber(s1, s2):
    Create an empty stack result
    Initialize remainder as 0
    While s1 and s2 are not empty:
        If s1 and s2 are not empty:
            sum = remainder + s1.peek() + s2.peek()
            s1.pop()
            s2.pop()
        Else:
            If s1 is not empty:
                sum = remainder + s1.peek()
                s1.pop()
            Else:
                sum = remainder + s2.peek()
                s2.pop()
        Push sum % 10 into result
        remainder = sum / 10
    While remainder > 0:
        Push remainder % 10 into result
        remainder = remainder / 10
    While result is not empty:
        Push result.peek() into s1
        result.pop()

Algorithm

  1. Create two empty stacks s1 and s2.
  2. Push elements into s1 and s2.
  3. Create an object of class Summation called task.
  4. Perform the following operations: a. Print the elements of s1 and s2 using the printStack() function of the task object. b. Call the addNumber(s1, s2) function of the task object to add the numbers represented by s1 and s2. c. Print the result using the printData(s1) function of the task object.

Code Solution

/*
    C Program 
    Add two numbers represented by stack
*/
#include <stdio.h>
#include <stdlib.h>

// Define stack node
struct StackNode
{
    int element;
    struct StackNode *next;
};
// Define a custom stack
struct MyStack
{
    struct StackNode *top;
    int size;
};

struct MyStack *newStack()
{
    //Make a stack
    struct MyStack *stack = (struct MyStack *) malloc(sizeof(struct MyStack));
    if (stack != NULL)
    {
        //Set node values
        stack->top = NULL;
        stack->size = 0;
    }
    else
    {
        printf("\nMemory overflow when create new stack\n");
    }
}
// Returns the status of empty or non empty stacks
int isEmpty(struct MyStack *stack)
{
    if (stack->size > 0 && stack->top != NULL)
    {
        return 0;
    }
    else
    {
        return 1;
    }
}
// Add node at the top of stack
void push(struct MyStack *stack, int element)
{

    // Make a new node
    struct StackNode *node = (struct StackNode *) malloc(sizeof(struct StackNode));
    
    if (node == NULL)
    {
        printf("\nMemory overflow when create new stack Node \n");
    }
    else
    {
        node->element = element;
        node->next    = stack->top;
    }

    // Add stack element
    stack->top = node;
    stack->size++;
}
// return top element of stack
int peek(struct MyStack *stack)
{
    return stack->top->element;
}
// Remove top element of stack
void pop(struct MyStack *stack)
{
    if (isEmpty(stack) == 0)
    {
        struct StackNode *temp = stack->top;
        // Change top element of stack
        stack->top = temp->next;
        // remove previous top
        free(temp);
        temp = NULL;
        stack->size--;
    }
}
// Perform of addition of two numbers in stack
void addNumber(struct MyStack*s1,struct MyStack*s2)
{
    // This is backup stack
    struct MyStack *result = newStack();

    int remainder = 0;

    int sum = 0;

    while(isEmpty(s1)==0 || isEmpty(s2) == 0)
    {

        if(isEmpty(s1)==0 && isEmpty(s2) == 0)
        {
            // When both stack element exists
            sum = remainder + peek(s1) + peek(s2);
            pop(s1);
            pop(s2);

           
        }
        else
        {
            if(isEmpty(s1)==0 )
            {
                // When s1 element exists
                sum = remainder + peek(s1);
                pop(s1);
            }
            else
            {
                 // When s2 element exists
                sum = remainder + peek(s2);
                pop(s2);
            }

        }
        // Add sum into stack
        push(result,sum % 10);

        remainder = sum / 10;
    }
    // When remainder value exists
    while(remainder > 0)
    {
        push(result,remainder % 10);

        remainder = remainder / 10;
    }

    // Put result into stack s1
    while(isEmpty(result)==0)
    {
        push(s1,peek(result));

        pop(result);
    }
    
}
// Print stack elements in reverse order
void printData(struct MyStack *s)
{
    if(isEmpty(s)==1)
    {
        return;
    }
    int data = peek(s);
    pop(s);
    printData(s);
    printf("  %d", data);
    push(s,data);
  
   
}
// Handle request to print stack elements
void printStack(struct MyStack*s1,struct MyStack*s2)
{
    printf("\n Stack 1 \n");
    printData(s1);
    printf("\n Stack 2 \n");
    printData(s2);
}
int main()
{   
    // Create two empty stack
    struct MyStack*s1 = newStack();
    struct MyStack*s2 = newStack();

    // First stack
    push(s1,9);
    push(s1,8);
    push(s1,9);
    
    // Second stack
    push(s2,4);
    push(s2,2);
    push(s2,8);

    printStack(s1,s2);
    addNumber(s1,s2);
    printf("\n Result \n");
    printData(s1);
    printf("\n");

    return 0;
}

Output

 Stack 1
  9  8  9
 Stack 2
  4  2  8
 Result
  1  4  1  7
/*
   Java Program for
   Check if two stacks are equal
*/
// Define stack node
class StackNode
{
	public int element;
	public StackNode next;
	public StackNode(int element, StackNode top)
	{
		this.element = element;
		this.next = top;
	}
}
// Define a custom stack
class MyStack
{
	public StackNode top;
	public int size;
	public MyStack()
	{
		//Set node values
		this.top = null;
		this.size = 0;
	}
	// Add node at the top of stack
	public void push(int element)
	{
		this.top = new StackNode(element, this.top);
		this.size++;
	}
	public boolean isEmpty()
	{
		if (this.size > 0 && this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Remove top element of stack
	public void pop()
	{
		if (this.size > 0 && this.top != null)
		{
			StackNode temp = this.top;
			// Change top element of stack
			this.top = temp.next;
			// remove previous top
			temp = null;
			this.size--;
		}
	}
	// return top element of stack
	public int peek()
	{
		if (this.top == null)
		{
			return -1;
		}
		return this.top.element;
	}
}
public class Summation
{
	// Perform of addition of two numbers in stack
	public void addNumber(MyStack s1, MyStack s2)
	{
		// This is backup stack
		MyStack result = new MyStack();
		int remainder = 0;
		int sum = 0;
		while (s1.isEmpty() == false || s2.isEmpty() == false)
		{
			if (s1.isEmpty() == false && s2.isEmpty() == false)
			{
				// When both stack element exists
				sum = remainder + s1.peek() + s2.peek();
				s1.pop();
				s2.pop();
			}
			else
			{
				if (s1.isEmpty() == false)
				{
					// When s1 element exists
					sum = remainder + s1.peek();
					s1.pop();
				}
				else
				{
					// When s2 element exists
					sum = remainder + s2.peek();
					s2.pop();
				}
			}
			// Add sum into stack
			result.push(sum % 10);
			remainder = sum / 10;
		}
		// When remainder value exists
		while (remainder > 0)
		{
			result.push(remainder % 10);
			remainder = remainder / 10;
		}
		// Put result into stack s1
		while (result.isEmpty() == false)
		{
			s1.push(result.peek());
			result.pop();
		}
	}
	// Print stack elements in reverse order
	public void printData(MyStack s)
	{
		if (s.isEmpty() == true)
		{
			return;
		}
		int data = s.peek();
		s.pop();
		printData(s);
		System.out.print(" " + data);
		s.push(data);
	}
	// Handle request to print stack elements
	public void printStack(MyStack s1, MyStack s2)
	{
		System.out.print("\n Stack 1 \n");
		printData(s1);
		System.out.print("\n Stack 2 \n");
		printData(s2);
	}
	public static void main(String[] args)
	{
		// Create two empty stack
		Summation task = new Summation();
		MyStack s1 = new MyStack();
		MyStack s2 = new MyStack();
		// First stack
		s1.push(9);
		s1.push(8);
		s1.push(9);
		// Second stack
		s2.push(4);
		s2.push(2);
		s2.push(8);
		task.printStack(s1, s2);
		task.addNumber(s1, s2);
		System.out.print("\n Result \n");
		task.printData(s1);
		System.out.print("\n");
	}
}

Output

 Stack 1
 9 8 9
 Stack 2
 4 2 8
 Result
 1 4 1 7
// Include header file
#include <iostream>

using namespace std;
/*
   C++ Program for
   Check if two stacks are equal
*/
// Define stack node
class StackNode
{
	public: 
    int element;
	StackNode *next;
	StackNode(int element, StackNode *top)
	{
		this->element = element;
		this->next = top;
	}
};
// Define a custom stack
class MyStack
{
	public: StackNode *top;
	int size;
	MyStack()
	{
		//Set node values
		this->top = NULL;
		this->size = 0;
	}
	// Add node at the top of stack
	void push(int element)
	{
		this->top = new StackNode(element, this->top);
		this->size++;
	}
	bool isEmpty()
	{
		if (this->size > 0 && this->top != NULL)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Remove top element of stack
	void pop()
	{
		if (this->size > 0 && this->top != NULL)
		{
			StackNode *temp = this->top;
			// Change top element of stack
			this->top = temp->next;
			// remove previous top
			temp = NULL;
			this->size--;
		}
	}
	// return top element of stack
	int peek()
	{
		if (this->top == NULL)
		{
			return -1;
		}
		return this->top->element;
	}
};
class Summation
{
	public:
		// Perform of addition of two numbers in stack
		void addNumber(MyStack *s1, MyStack *s2)
		{
			// This is backup stack
			MyStack *result = new MyStack();
			int remainder = 0;
			int sum = 0;
			while (s1->isEmpty() == false || s2->isEmpty() == false)
			{
				if (s1->isEmpty() == false && s2->isEmpty() == false)
				{
					// When both stack element exists
					sum = remainder + s1->peek() + s2->peek();
					s1->pop();
					s2->pop();
				}
				else
				{
					if (s1->isEmpty() == false)
					{
						// When s1 element exists
						sum = remainder + s1->peek();
						s1->pop();
					}
					else
					{
						// When s2 element exists
						sum = remainder + s2->peek();
						s2->pop();
					}
				}
				// Add sum into stack
				result->push(sum % 10);
				remainder = sum / 10;
			}
			// When remainder value exists
			while (remainder > 0)
			{
				result->push(remainder % 10);
				remainder = remainder / 10;
			}
			// Put result into stack s1
			while (result->isEmpty() == false)
			{
				s1->push(result->peek());
				result->pop();
			}
		}
	// Print stack elements in reverse order
	void printData(MyStack s)
	{
		if (s.isEmpty() == true)
		{
			return;
		}
		int data = s.peek();
		s.pop();
		this->printData(s);
		cout << " " << data;
		s.push(data);
	}
	// Handle request to print stack elements
	void printStack(MyStack s1, MyStack s2)
	{
		cout << "\n Stack 1 \n";
		this->printData(s1);
		cout << "\n Stack 2 \n";
		this->printData(s2);
	}
};
int main()
{
	// Create two empty stack
	Summation task = Summation();
	MyStack s1 = MyStack();
	MyStack s2 = MyStack();
	// First stack
	s1.push(9);
	s1.push(8);
	s1.push(9);
	// Second stack
	s2.push(4);
	s2.push(2);
	s2.push(8);
	task.printStack(s1, s2);
	task.addNumber(&s1, &s2);
	cout << "\n Result \n";
	task.printData(s1);
	cout << "\n";
	return 0;
}

Output

 Stack 1
 9 8 9
 Stack 2
 4 2 8
 Result
 1 4 1 7
// Include namespace system
using System;
/*
   C# Program for
   Check if two stacks are equal
*/
// Define stack node
public class StackNode
{
	public int element;
	public StackNode next;
	public StackNode(int element, StackNode top)
	{
		this.element = element;
		this.next = top;
	}
}
// Define a custom stack
public class MyStack
{
	public StackNode top;
	public int size;
	public MyStack()
	{
		//Set node values
		this.top = null;
		this.size = 0;
	}
	// Add node at the top of stack
	public void push(int element)
	{
		this.top = new StackNode(element, this.top);
		this.size++;
	}
	public Boolean isEmpty()
	{
		if (this.size > 0 && this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Remove top element of stack
	public void pop()
	{
		if (this.size > 0 && this.top != null)
		{
			StackNode temp = this.top;
			// Change top element of stack
			this.top = temp.next;
			// remove previous top
			temp = null;
			this.size--;
		}
	}
	// return top element of stack
	public int peek()
	{
		if (this.top == null)
		{
			return -1;
		}
		return this.top.element;
	}
}
public class Summation
{
	// Perform of addition of two numbers in stack
	public void addNumber(MyStack s1, MyStack s2)
	{
		// This is backup stack
		MyStack result = new MyStack();
		int remainder = 0;
		int sum = 0;
		while (s1.isEmpty() == false || s2.isEmpty() == false)
		{
			if (s1.isEmpty() == false && s2.isEmpty() == false)
			{
				// When both stack element exists
				sum = remainder + s1.peek() + s2.peek();
				s1.pop();
				s2.pop();
			}
			else
			{
				if (s1.isEmpty() == false)
				{
					// When s1 element exists
					sum = remainder + s1.peek();
					s1.pop();
				}
				else
				{
					// When s2 element exists
					sum = remainder + s2.peek();
					s2.pop();
				}
			}
			// Add sum into stack
			result.push(sum % 10);
			remainder = sum / 10;
		}
		// When remainder value exists
		while (remainder > 0)
		{
			result.push(remainder % 10);
			remainder = remainder / 10;
		}
		// Put result into stack s1
		while (result.isEmpty() == false)
		{
			s1.push(result.peek());
			result.pop();
		}
	}
	// Print stack elements in reverse order
	public void printData(MyStack s)
	{
		if (s.isEmpty() == true)
		{
			return;
		}
		int data = s.peek();
		s.pop();
		printData(s);
		Console.Write(" " + data);
		s.push(data);
	}
	// Handle request to print stack elements
	public void printStack(MyStack s1, MyStack s2)
	{
		Console.Write("\n Stack 1 \n");
		printData(s1);
		Console.Write("\n Stack 2 \n");
		printData(s2);
	}
	public static void Main(String[] args)
	{
		// Create two empty stack
		Summation task = new Summation();
		MyStack s1 = new MyStack();
		MyStack s2 = new MyStack();
		// First stack
		s1.push(9);
		s1.push(8);
		s1.push(9);
		// Second stack
		s2.push(4);
		s2.push(2);
		s2.push(8);
		task.printStack(s1, s2);
		task.addNumber(s1, s2);
		Console.Write("\n Result \n");
		task.printData(s1);
		Console.Write("\n");
	}
}

Output

 Stack 1
 9 8 9
 Stack 2
 4 2 8
 Result
 1 4 1 7
<?php
/*
   Php Program for
   Check if two stacks are equal
*/
// Define stack node
class StackNode
{
	public $element;
	public $next;

	function __construct($element, $top)
	{
		$this->element = $element;
		$this->next = $top;
	}
}
// Define a custom stack
class MyStack
{
	public $top;
	public $size;

	function __construct()
	{
		//Set node values
		$this->top = null;
		$this->size = 0;
	}
	// Add node at the top of stack
	public	function push($element)
	{
		$this->top = new StackNode($element, $this->top);
		$this->size++;
	}
	public	function isEmpty()
	{
		if ($this->size > 0 && $this->top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Remove top element of stack
	public	function pop()
	{
		if ($this->size > 0 && $this->top != null)
		{
			$temp = $this->top;
			// Change top element of stack
			$this->top = $temp->next;
			// remove previous top
			$temp = null;
			$this->size--;
		}
	}
	// return top element of stack
	public	function peek()
	{
		if ($this->top == null)
		{
			return -1;
		}
		return $this->top->element;
	}
}
class Summation
{
	// Perform of addition of two numbers in stack
	public	function addNumber($s1, $s2)
	{
		// This is backup stack
		$result = new MyStack();
		$remainder = 0;
		$sum = 0;
		while ($s1->isEmpty() == false || $s2->isEmpty() == false)
		{
			if ($s1->isEmpty() == false && $s2->isEmpty() == false)
			{
				// When both stack element exists
				$sum = $remainder + $s1->peek() + $s2->peek();
				$s1->pop();
				$s2->pop();
			}
			else
			{
				if ($s1->isEmpty() == false)
				{
					// When s1 element exists
					$sum = $remainder + $s1->peek();
					$s1->pop();
				}
				else
				{
					// When s2 element exists
					$sum = $remainder + $s2->peek();
					$s2->pop();
				}
			}
			// Add sum into stack
			$result->push($sum % 10);
			$remainder = intval($sum / 10);
		}
		// When remainder value exists
		while ($remainder > 0)
		{
			$result->push($remainder % 10);
			$remainder = intval($remainder / 10);
		}
		// Put result into stack s1
		while ($result->isEmpty() == false)
		{
			$s1->push($result->peek());
			$result->pop();
		}
	}
	// Print stack elements in reverse order
	public	function printData($s)
	{
		if ($s->isEmpty() == true)
		{
			return;
		}
		$data = $s->peek();
		$s->pop();
		$this->printData($s);
		echo " ". $data;
		$s->push($data);
	}
	// Handle request to print stack elements
	public	function printStack($s1, $s2)
	{
		echo "\n Stack 1 \n";
		$this->printData($s1);
		echo "\n Stack 2 \n";
		$this->printData($s2);
	}
}

function main()
{
	// Create two empty stack
	$task = new Summation();
	$s1 = new MyStack();
	$s2 = new MyStack();
	// First stack
	$s1->push(9);
	$s1->push(8);
	$s1->push(9);
	// Second stack
	$s2->push(4);
	$s2->push(2);
	$s2->push(8);
	$task->printStack($s1, $s2);
	$task->addNumber($s1, $s2);
	echo "\n Result \n";
	$task->printData($s1);
	echo "\n";
}
main();

Output

 Stack 1
 9 8 9
 Stack 2
 4 2 8
 Result
 1 4 1 7
/*
   Node Js Program for
   Check if two stacks are equal
*/
// Define stack node
class StackNode
{
	constructor(element, top)
	{
		this.element = element;
		this.next = top;
	}
}
// Define a custom stack
class MyStack
{
	constructor()
	{
		//Set node values
		this.top = null;
		this.size = 0;
	}
	// Add node at the top of stack
	push(element)
	{
		this.top = new StackNode(element, this.top);
		this.size++;
	}
	isEmpty()
	{
		if (this.size > 0 && this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Remove top element of stack
	pop()
	{
		if (this.size > 0 && this.top != null)
		{
			var temp = this.top;
			// Change top element of stack
			this.top = temp.next;
			// remove previous top
			temp = null;
			this.size--;
		}
	}
	// return top element of stack
	peek()
	{
		if (this.top == null)
		{
			return -1;
		}
		return this.top.element;
	}
}
class Summation
{
	// Perform of addition of two numbers in stack
	addNumber(s1, s2)
	{
		// This is backup stack
		var result = new MyStack();
		var remainder = 0;
		var sum = 0;
		while (s1.isEmpty() == false || s2.isEmpty() == false)
		{
			if (s1.isEmpty() == false && s2.isEmpty() == false)
			{
				// When both stack element exists
				sum = remainder + s1.peek() + s2.peek();
				s1.pop();
				s2.pop();
			}
			else
			{
				if (s1.isEmpty() == false)
				{
					// When s1 element exists
					sum = remainder + s1.peek();
					s1.pop();
				}
				else
				{
					// When s2 element exists
					sum = remainder + s2.peek();
					s2.pop();
				}
			}
			// Add sum into stack
			result.push(sum % 10);
			remainder = parseInt(sum / 10);
		}
		// When remainder value exists
		while (remainder > 0)
		{
			result.push(remainder % 10);
			remainder = parseInt(remainder / 10);
		}
		// Put result into stack s1
		while (result.isEmpty() == false)
		{
			s1.push(result.peek());
			result.pop();
		}
	}
	// Print stack elements in reverse order
	printData(s)
	{
		if (s.isEmpty() == true)
		{
			return;
		}
		var data = s.peek();
		s.pop();
		this.printData(s);
		process.stdout.write(" " + data);
		s.push(data);
	}
	// Handle request to print stack elements
	printStack(s1, s2)
	{
		process.stdout.write("\n Stack 1 \n");
		this.printData(s1);
		process.stdout.write("\n Stack 2 \n");
		this.printData(s2);
	}
}

function main()
{
	// Create two empty stack
	var task = new Summation();
	var s1 = new MyStack();
	var s2 = new MyStack();
	// First stack
	s1.push(9);
	s1.push(8);
	s1.push(9);
	// Second stack
	s2.push(4);
	s2.push(2);
	s2.push(8);
	task.printStack(s1, s2);
	task.addNumber(s1, s2);
	process.stdout.write("\n Result \n");
	task.printData(s1);
	process.stdout.write("\n");
}
main();

Output

 Stack 1
 9 8 9
 Stack 2
 4 2 8
 Result
 1 4 1 7
#  Python 3 Program for
#  Check if two stacks are equal

#  Define stack node
class StackNode :
	
	def __init__(self, element, top) :
		self.element = element
		self.next = top
	

#  Define a custom stack
class MyStack :
	
	def __init__(self) :
		# Set node values
		self.top = None
		self.size = 0
	
	#  Add node at the top of stack
	def push(self, element) :
		self.top = StackNode(element, self.top)
		self.size += 1
	
	def isEmpty(self) :
		if (self.size > 0 and self.top != None) :
			return False
		else :
			return True
		
	
	#  Remove top element of stack
	def pop(self) :
		if (self.size > 0 and self.top != None) :
			temp = self.top
			#  Change top element of stack
			self.top = temp.next
			#  remove previous top
			temp = None
			self.size -= 1
		
	
	#  return top element of stack
	def peek(self) :
		if (self.top == None) :
			return -1
		
		return self.top.element
	

class Summation :
	#  Perform of addition of two numbers in stack
	def addNumber(self, s1, s2) :
		#  This is backup stack
		result = MyStack()
		remainder = 0
		sum = 0
		while (s1.isEmpty() == False or s2.isEmpty() == False) :
			if (s1.isEmpty() == False and s2.isEmpty() == False) :
				#  When both stack element exists
				sum = remainder + s1.peek() + s2.peek()
				s1.pop()
				s2.pop()
			else :
				if (s1.isEmpty() == False) :
					#  When s1 element exists
					sum = remainder + s1.peek()
					s1.pop()
				else :
					#  When s2 element exists
					sum = remainder + s2.peek()
					s2.pop()
				
			
			#  Add sum into stack
			result.push(sum % 10)
			remainder = int(sum / 10)
		
		#  When remainder value exists
		while (remainder > 0) :
			result.push(remainder % 10)
			remainder = int(remainder / 10)
		
		#  Put result into stack s1
		while (result.isEmpty() == False) :
			s1.push(result.peek())
			result.pop()
		
	
	#  Print stack elements in reverse order
	def printData(self, s) :
		if (s.isEmpty() == True) :
			return
		
		data = s.peek()
		s.pop()
		self.printData(s)
		print(" ", data, end = "")
		s.push(data)
	
	#  Handle request to print stack elements
	def printStack(self, s1, s2) :
		print("\n Stack 1 ")
		self.printData(s1)
		print("\n Stack 2 ")
		self.printData(s2)
	

def main() :
	#  Create two empty stack
	task = Summation()
	s1 = MyStack()
	s2 = MyStack()
	#  First stack
	s1.push(9)
	s1.push(8)
	s1.push(9)
	#  Second stack
	s2.push(4)
	s2.push(2)
	s2.push(8)
	task.printStack(s1, s2)
	task.addNumber(s1, s2)
	print("\n Result ")
	task.printData(s1)
	print(end = "\n")

if __name__ == "__main__": main()

Output

 Stack 1
  9  8  9
 Stack 2
  4  2  8
 Result
  1  4  1  7
#  Ruby Program for
#  Check if two stacks are equal

#  Define stack node
class StackNode  
	# Define the accessor and reader of class StackNode  
	attr_reader :element, :next
	attr_accessor :element, :next
 
	
	def initialize(element, top) 
		self.element = element
		self.next = top
	end

end

#  Define a custom stack
class MyStack  
	# Define the accessor and reader of class MyStack  
	attr_reader :top, :size
	attr_accessor :top, :size
 
	
	def initialize() 
		# Set node values
		self.top = nil
		self.size = 0
	end

	#  Add node at the top of stack
	def push(element) 
		self.top = StackNode.new(element, self.top)
		self.size += 1
	end

	def isEmpty() 
		if (self.size > 0 && self.top != nil) 
			return false
		else 
			return true
		end

	end

	#  Remove top element of stack
	def pop() 
		if (self.size > 0 && self.top != nil) 
			temp = self.top
			#  Change top element of stack
			self.top = temp.next
			#  remove previous top
			temp = nil
			self.size -= 1
		end

	end

	#  return top element of stack
	def peek() 
		if (self.top == nil) 
			return -1
		end

		return self.top.element
	end

end

class Summation 
	#  Perform of addition of two numbers in stack
	def addNumber(s1, s2) 
		#  This is backup stack
		result = MyStack.new()
		remainder = 0
		sum = 0
		while (s1.isEmpty() == false || s2.isEmpty() == false) 
			if (s1.isEmpty() == false && s2.isEmpty() == false) 
				#  When both stack element exists
				sum = remainder + s1.peek() + s2.peek()
				s1.pop()
				s2.pop()
			else 
				if (s1.isEmpty() == false) 
					#  When s1 element exists
					sum = remainder + s1.peek()
					s1.pop()
				else 
					#  When s2 element exists
					sum = remainder + s2.peek()
					s2.pop()
				end

			end

			#  Add sum into stack
			result.push(sum % 10)
			remainder = sum / 10
		end

		#  When remainder value exists
		while (remainder > 0) 
			result.push(remainder % 10)
			remainder = remainder / 10
		end

		#  Put result into stack s1
		while (result.isEmpty() == false) 
			s1.push(result.peek())
			result.pop()
		end

	end

	#  Print stack elements in reverse order
	def printData(s) 
		if (s.isEmpty() == true) 
			return
		end

		data = s.peek()
		s.pop()
		self.printData(s)
		print(" ", data)
		s.push(data)
	end

	#  Handle request to print stack elements
	def printStack(s1, s2) 
		print("\n Stack 1 \n")
		self.printData(s1)
		print("\n Stack 2 \n")
		self.printData(s2)
	end

end

def main() 
	#  Create two empty stack
	task = Summation.new()
	s1 = MyStack.new()
	s2 = MyStack.new()
	#  First stack
	s1.push(9)
	s1.push(8)
	s1.push(9)
	#  Second stack
	s2.push(4)
	s2.push(2)
	s2.push(8)
	task.printStack(s1, s2)
	task.addNumber(s1, s2)
	print("\n Result \n")
	task.printData(s1)
	print("\n")
end

main()

Output

 Stack 1 
 9 8 9
 Stack 2 
 4 2 8
 Result 
 1 4 1 7

/*
   Scala Program for
   Check if two stacks are equal
*/
// Define stack node
class StackNode(var element: Int , var next: StackNode);
// Define a custom stack
class MyStack(var top: StackNode , var size: Int)
{
	def this()
	{
		this(null, 0);
	}
	// Add node at the top of stack
	def push(element: Int): Unit = {
		this.top = new StackNode(element, this.top);
		this.size += 1;
	}
	def isEmpty(): Boolean = {
		if (this.size > 0 && this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Remove top element of stack
	def pop(): Unit = {
		if (this.size > 0 && this.top != null)
		{
			var temp: StackNode = this.top;
			// Change top element of stack
			this.top = temp.next;
			// remove previous top
			temp = null;
			this.size -= 1;
		}
	}
	// return top element of stack
	def peek(): Int = {
		if (this.top == null)
		{
			return -1;
		}
		return this.top.element;
	}
}
class Summation
{
	// Perform of addition of two numbers in stack
	def addNumber(s1: MyStack, s2: MyStack): Unit = {
		// This is backup stack
		var result: MyStack = new MyStack();
		var remainder: Int = 0;
		var sum: Int = 0;
		while (s1.isEmpty() == false || s2.isEmpty() == false)
		{
			if (s1.isEmpty() == false && s2.isEmpty() == false)
			{
				// When both stack element exists
				sum = remainder + s1.peek() + s2.peek();
				s1.pop();
				s2.pop();
			}
			else
			{
				if (s1.isEmpty() == false)
				{
					// When s1 element exists
					sum = remainder + s1.peek();
					s1.pop();
				}
				else
				{
					// When s2 element exists
					sum = remainder + s2.peek();
					s2.pop();
				}
			}
			// Add sum into stack
			result.push(sum % 10);
			remainder = (sum / 10).toInt;
		}
		// When remainder value exists
		while (remainder > 0)
		{
			result.push(remainder % 10);
			remainder = (remainder / 10).toInt;
		}
		// Put result into stack s1
		while (result.isEmpty() == false)
		{
			s1.push(result.peek());
			result.pop();
		}
	}
	// Print stack elements in reverse order
	def printData(s: MyStack): Unit = {
		if (s.isEmpty() == true)
		{
			return;
		}
		var data: Int = s.peek();
		s.pop();
		this.printData(s);
		print(" " + data);
		s.push(data);
	}
	// Handle request to print stack elements
	def printStack(s1: MyStack, s2: MyStack): Unit = {
		print("\n Stack 1 \n");
		this.printData(s1);
		print("\n Stack 2 \n");
		this.printData(s2);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Create two empty stack
		var task: Summation = new Summation();
		var s1: MyStack = new MyStack();
		var s2: MyStack = new MyStack();
		// First stack
		s1.push(9);
		s1.push(8);
		s1.push(9);
		// Second stack
		s2.push(4);
		s2.push(2);
		s2.push(8);
		task.printStack(s1, s2);
		task.addNumber(s1, s2);
		print("\n Result \n");
		task.printData(s1);
		print("\n");
	}
}

Output

 Stack 1
 9 8 9
 Stack 2
 4 2 8
 Result
 1 4 1 7
/*
   Swift 4 Program for
   Check if two stacks are equal
*/
// Define stack node
class StackNode
{
	var element: Int;
	var next: StackNode? ;
	init(_ element: Int, _ top: StackNode? )
	{
		self.element = element;
		self.next = top;
	}
}
// Define a custom stack
class MyStack
{
	var top: StackNode? ;
	var size: Int;
	init()
	{
		//Set node values
		self.top = nil;
		self.size = 0;
	}
	// Add node at the top of stack
	func push(_ element: Int)
	{
		self.top = StackNode(element, self.top);
		self.size += 1;
	}
	func isEmpty()->Bool
	{
		if (self.size > 0 && self.top  != nil)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Remove top element of stack
	func pop()
	{
		if (self.size > 0 && self.top  != nil)
		{
			var temp: StackNode? = self.top;
			// Change top element of stack
			self.top = temp!.next;
			// remove previous top
			temp = nil;
			self.size -= 1;
		}
	}
	// return top element of stack
	func peek()->Int
	{
		if (self.top == nil)
		{
			return -1;
		}
		return self.top!.element;
	}
}
class Summation
{
	// Perform of addition of two numbers in stack
	func addNumber(_ s1: MyStack, _ s2: MyStack)
	{
		// This is backup stack
		let result: MyStack = MyStack();
		var remainder: Int = 0;
		var sum: Int = 0;
		while (s1.isEmpty() == false || s2.isEmpty() == false)
		{
			if (s1.isEmpty() == false && s2.isEmpty() == false)
			{
				// When both stack element exists
				sum = remainder + s1.peek() + s2.peek();
				s1.pop();
				s2.pop();
			}
			else
			{
				if (s1.isEmpty() == false)
				{
					// When s1 element exists
					sum = remainder + s1.peek();
					s1.pop();
				}
				else
				{
					// When s2 element exists
					sum = remainder + s2.peek();
					s2.pop();
				}
			}
			// Add sum into stack
			result.push(sum % 10);
			remainder = sum / 10;
		}
		// When remainder value exists
		while (remainder > 0)
		{
			result.push(remainder % 10);
			remainder = remainder / 10;
		}
		// Put result into stack s1
		while (result.isEmpty() == false)
		{
			s1.push(result.peek());
			result.pop();
		}
	}
	// Print stack elements in reverse order
	func printData(_ s: MyStack)
	{
		if (s.isEmpty() == true)
		{
			return;
		}
		let data: Int = s.peek();
		s.pop();
		self.printData(s);
		print(" ", data, terminator: "");
		s.push(data);
	}
	// Handle request to print stack elements
	func printStack(_ s1: MyStack , _ s2 : MyStack)
	{
		print("\n Stack 1 ");
		self.printData(s1);
		print("\n Stack 2 ");
		self.printData(s2);
	}
}
func main()
{
	// Create two empty stack
	let task: Summation = Summation();
	let s1: MyStack = MyStack();
	let s2: MyStack = MyStack();
	// First stack
	s1.push(9);
	s1.push(8);
	s1.push(9);
	// Second stack
	s2.push(4);
	s2.push(2);
	s2.push(8);
	task.printStack(s1, s2);
	task.addNumber(s1, s2);
	print("\n Result ");
	task.printData(s1);
	print(terminator: "\n");
}
main();

Output

 Stack 1
  9  8  9
 Stack 2
  4  2  8
 Result
  1  4  1  7
/*
   Kotlin Program for
   Check if two stacks are equal
*/
// Define stack node
class StackNode
{
	var element: Int;
	var next: StackNode ? ;
	constructor(element: Int, top: StackNode ? )
	{
		this.element = element;
		this.next = top;
	}
}
// Define a custom stack
class MyStack
{
	var top: StackNode ? ;
	var size: Int;
	constructor()
	{
		//Set node values
		this.top = null;
		this.size = 0;
	}
	// Add node at the top of stack
	fun push(element: Int): Unit
	{
		this.top = StackNode(element, this.top);
		this.size += 1;
	}
	fun isEmpty(): Boolean
	{
		if (this.size > 0 && this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Remove top element of stack
	fun pop(): Unit
	{
		if (this.size > 0 && this.top != null)
		{
			var temp: StackNode ? = this.top;
			// Change top element of stack
			this.top = temp?.next;
			this.size -= 1;
		}
	}
	// return top element of stack
	fun peek(): Int
	{
		if (this.top == null)
		{
			return -1;
		}
		return this.top!!.element;
	}
}
class Summation
{
	// Perform of addition of two numbers in stack
	fun addNumber(s1: MyStack, s2 : MyStack): Unit
	{
		// This is backup stack
		var result: MyStack = MyStack();
		var remainder: Int = 0;
		var sum: Int ;
		while (s1.isEmpty() == false || s2.isEmpty() == false)
		{
			if (s1.isEmpty() == false && s2.isEmpty() == false)
			{
				// When both stack element exists
				sum = remainder + s1.peek() + s2.peek();
				s1.pop();
				s2.pop();
			}
			else
			{
				if (s1.isEmpty() == false)
				{
					// When s1 element exists
					sum = remainder + s1.peek();
					s1.pop();
				}
				else
				{
					// When s2 element exists
					sum = remainder + s2.peek();
					s2.pop();
				}
			}
			// Add sum into stack
			result.push(sum % 10);
			remainder = sum / 10;
		}
		// When remainder value exists
		while (remainder > 0)
		{
			result.push(remainder % 10);
			remainder = remainder / 10;
		}
		// Put result into stack s1
		while (result.isEmpty() == false)
		{
			s1.push(result.peek());
			result.pop();
		}
	}
	// Print stack elements in reverse order
	fun printData(s: MyStack): Unit
	{
		if (s.isEmpty() == true)
		{
			return;
		}
		var data: Int = s.peek();
		s.pop();
		this.printData(s);
		print(" " + data);
		s.push(data);
	}
	// Handle request to print stack elements
	fun printStack(s1: MyStack, s2 : MyStack): Unit
	{
		print("\n Stack 1 \n");
		this.printData(s1);
		print("\n Stack 2 \n");
		this.printData(s2);
	}
}
fun main(args: Array < String > ): Unit
{
	// Create two empty stack
	var task: Summation = Summation();
	var s1: MyStack = MyStack();
	var s2: MyStack = MyStack();
	// First stack
	s1.push(9);
	s1.push(8);
	s1.push(9);
	// Second stack
	s2.push(4);
	s2.push(2);
	s2.push(8);
	task.printStack(s1, s2);
	task.addNumber(s1, s2);
	print("\n Result \n");
	task.printData(s1);
	print("\n");
}

Output

 Stack 1
 9 8 9
 Stack 2
 4 2 8
 Result
 1 4 1 7

Time Complexity

The time complexity of adding two numbers represented by two stacks is O(n), where n is the number of digits in the larger number. The function iterates through both stacks once and performs constant-time operations for each element. Therefore, the overall time complexity of the algorithm is O(n).

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment





Categories
Relative Post