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:
- Create a new stack
result
to store the sum of the two numbers. - Initialize a variable
remainder
to 0 to keep track of the carry while performing the addition. - Iterate through both stacks
s1
ands2
until either of them becomes empty: a. If boths1
ands2
are not empty, compute the sum of the top elements of both stacks along with theremainder
. b. If eithers1
ors2
becomes empty, consider only the non-empty stack and add it to theremainder
. c. Calculate the digit to be stored in theresult
stack as the sum modulo 10 and update theremainder
as the sum divided by 10. d. Pop the top elements ofs1
ands2
. e. Push the calculated digit into theresult
stack. - After the iteration, if there is any remaining
remainder
, add it to theresult
stack. - Put the elements from the
result
stack back intos1
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
- Create two empty stacks
s1
ands2
. - Push elements into
s1
ands2
. - Create an object of class
Summation
calledtask
. - Perform the following operations:
a. Print the elements of
s1
ands2
using theprintStack()
function of thetask
object. b. Call theaddNumber(s1, s2)
function of thetask
object to add the numbers represented bys1
ands2
. c. Print the result using theprintData(s1)
function of thetask
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).
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