Add Two Numbers Represented by Stacks

Approach

We have two stacks, ‘A’ and ‘B’, each with ‘N’ elements. To add two numbers, the least significant digit of the number should be at the bottom of the stack and other elements followed by it in the stack.

After this, we will add two numbers represented by the stack by removing the top elements of the stacks. We will perform the addition until the stacks are empty.

During the addition, we need to take care of the carry. If the sum is greater or equal to 10, we will do sum%10 and make the carry = 1. Remember the formula of addition will be carry + stack1.top() + stack2.top().  We need the declare the carry = 0 before the addition.

We insert the result into the resultant stack each time we get it. Once stacks are empty after the addition, we will check if carry = 0. If the carry is not 0, we will add it to the top of the stack.

Then we will print the resultant stack elements one by one as output.

Algorithm

1. Declare two stacks to store both numbers.
    
2. Extract the top element from both stacks and add it with carry.
    
3. Push the sum into the stack. 
    
4. Store the carry and pop out the recently extracted top elements.
    
5. If we encounter carry at any step, we need to add it to the sum.
    
6. Check if the first stack is not empty and move to the new top element. Check the same with the second stack. 
    
7. Calculate the sum and push it into the answer stack. Repeat this process till the stack becomes empty.
    
8. Return the answer stack.
    
9. Print the elements from the answer stack.

DRY Run

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
/*
    Function to find the sum of two numbers and
    store the result in the stack.
*/
stack<int> Add(stack<int> stack1, stack<int> stack2) {
	stack<int> result;
	int sum = 0;
	int carry = 0;

	while (!stack1.empty() || !stack2.empty()) {
		// Add the top elements of the stacks with carry.
		sum = carry + (!stack1.empty() ? stack1.top() : 0) + 
		(!stack2.empty() ? stack2.top() : 0);

		carry = sum / 10;

		result.push(sum % 10);

		// Pop the top elements
		if (!stack1.empty()) {
			stack1.pop();
		}

		if (!stack2.empty()) {
			stack2.pop();
		}
	}

	// If carry remains
	if (carry != 0) {
		result.push(carry);
	}

	return result;
}

// Function to display the resultant stack
void display(stack<int> &res) {
	while (!res.empty()) {
		int value = res.top();
		cout << value << " ";
		res.pop();
	}
}

// Driver code
int main() {
	stack<int> S1;
	stack<int> S2;
	
	 // Stack1 elements
	 S1.push(3);
	 S1.push(8);
	 S1.push(1);
	 S1.push(3);
	 S1.push(5);
	 
	 // Stack2 elements
	 S2.push(6);
	 S2.push(2);
	 S2.push(4);
	 S2.push(3);
	 S2.push(5);
    
	stack<int> res = Add(S1, S2);
	cout << "Resultant: ";
	display(res);
	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

Stack1 = [3,8,1,3,5]

Stack2 = [6,2,4,3,5]

Output

Must Read Stack Operations

Implementation in Python

# Function to add two numbers represented by stacks.
def Addingstacks(stack1,stack2):
    carry = 0
    output = 0
    resultstack = []
    
    # Adding numbers until stack1 or stack2 is empty.
    # Adding the result in resultstack.
    while(stack1 or stack2):
        output = carry + (stack1.pop() if stack1 else 0)  + (stack2.pop() if stack2 else 0) 
        
        carry = int(output/10)
        
        resultstack.append(output%10)


    # Adding the carry if it is not 0.       
    if carry!=0:
        resultstack.append(carry)
        
    return resultstack
    
# Driver function
if __name__ == '__main__':
    stack1 = []
    stack2 = []
    
    # Stack1 elements
    stack1.append(3)
    stack1.append(8)
    stack1.append(1)
    stack1.append(3)
    stack1.append(5)
    
    # Stack2 elements
    stack2.append(6)
    stack2.append(2)
    stack2.append(4)
    stack2.append(3)
    stack2.append(5)
    
    print("Resultant: ")
    result = Addingstacks(stack1,stack2)
    for i in range(0,len(result)):
        print(result.pop(),end=' ')

You can also try this code with Online Python Compiler

Run Code

Input

Stack1 = [3,8,1,3,5]

Stack2 = [6,2,4,3,5]
 

Output

Complexity Analysis

The time complexity will be O(M + N), where M is the size of stack1 and N is the size of stack2. 

The space complexity will be O(M + N), where M is the size of stack1 and N is the size of stack2.
 

Also check out Addition of Two Numbers in Java here.

Frequently Asked Questions

What is the concept followed by stack?

Stack follows the LIFO idea, which means last in, first out. It is a concept that means the last element inserted will be the first to out from the structure.

How we can access the top element in the stack?

We can access the top element in the stack using the stack.top() method.

What is the time complexity of insertion in the stack?

The time complexity of insertion in the stack is O(1).

What is the stack application?

Stack is used in backtracking algorithms, DFS, and converting infix to postfix expressions.

Can we use stack with other data structures?

Yes, we can use a stack with different data structures. For example, we can use it to reverse an array.

Conclusion

In this blog, we have learned how to add two numbers represented by stacks. We have discussed the approach to the problem with examples. Then we implemented the approach to the problem in C++ and Python.

To learn more about stack-based problems, check out the following links.

• Sort A Stack
• Reverse a String using Stack
• How To Sort A Stack Using Recursion?
• Check if stack elements are pairwise consecutive
• Check if an array is stack sortable
   

You can also consider our Mern Stack Course to give your career an edge over others.

Happy Coding!