Problems based on stacks are frequently asked in various big-name companies during the coding rounds. When preparing for a coding interview, you must solve the problems based on stacks as much as possible.

In this blog, we will discuss one of the popular problems based on the stack data structure. This problem got asked in various coding interviews despite being a simple problem. Let's discuss the problem statement.

Problem Statement

We need to add two numbers represented by stacks. There are two stacks, â€˜Aâ€™ and â€˜Bâ€™; each has â€˜Nâ€™ elements. We aim to determine the sum of those â€˜Nâ€™ elements represented as one big number.

The sum of the numbers should be less than 10. If it is 10 or more than 10 then we need to take the carry of the sum and add it in the next addition operation.

Example:

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

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

38135 + 62435 = 100570

Now we have discussed the problem statement, let's discuss the approach add two numbers represented by the stack.

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

Declare two stacks to store both numbers.

Extract the top element from both stacks and add it with carry.

Push the sum into the stack.

Store the carry and pop out the recently extracted top elements.

If we encounter carry at any step, we need to add it to the sum.

Check if the first stack is not empty and move to the new top element. Check the same with the second stack.

Calculate the sum and push it into the answer stack. Repeat this process till the stack becomes empty.

Return the answer stack.

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

# 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=' ')

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.

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.