Stack: Check if concatenation of two strings is balanced or not

You are given 2 bracket sequence S1 and S2.

You need to check if the string obtained by concatenating both sequence is balanced or not.

Input: s1 = “)()(())))”, s2 = “(()(()(” 

Output: Balanced

Sequence: “(()(()()()(())))”

We will use stack for the solution.

We will concatenate both sequences and check if the resultant sequence is balanced or not.

First check s1 + s2 is balanced if not check s2 + s1 is balanced or not.

Steps for solution:

1. Take a temp stack, call it as S

2. Traverse the expression, call it as exp

1. If the current character is a starting bracket then push into the stack.

2. If the current character is closing bracket, then pop form the stack.

If the popped character is matching then they are balanced, else they are not balanced.

3. Share the result

Time Complexity: O(n)

Space Complexity: O(n)

#include <iostream>
#include <stack>
#include <vector>
#include <bits/stdc++.h>
using namespace std;


bool checkIsBalanced(string s)
{

	stack<char> st;

	int n = s.length();

	for (int i = 0; i < n; i++) 
	{

		if (s[i] == '(')
			st.push(s[i]);

		else 
		{
			if (st.empty()) 
			{
				return false;
			}

			else
				st.pop();
		}
	}

	if (!st.empty())
		return false;

	return true;
}


bool solution(string s1, string s2)
{

	// check for s1 + s2 is balanced or not.
	if (checkIsBalanced(s1 + s2))
		return true;

	// Check for s2 + s1 is balanced or not.
	return checkIsBalanced(s2 + s1);
}

int main()
{
	string s1 = ")()(())))";
	string s2 = "(()(()(";

	if (solution(s1, s2))
		cout << "Balanced";
	else
		cout << "Not Balanced";

	return 0;
}

Output

Balanced