Checking Balanced Parentheses in C++

Let's start by understanding the problem statement for this task.

You are given a string of parentheses, your work is to find out whether the string is balanced or not if balanced then print True else False.

Hint:

In this problem, you have to just check whether the brackets which have opened once should have been closed then the string is balanced else it is not balanced. For the concern, one may think to use the stack data structure, which uses the FIFO rule.

Quick Think:

The problem is solved using the stack data structure. The following points must be kept in mind while designing the algorithm.

1. Push all the opening brackets except the closing brackets.
2. When a closing bracket is encountered then pop the topmost element from the stack and compare it with the other closing brackets if it is of the same type itself then continue, else the string is not balanced.
3. And at the end return the empty stack.

Algorithm:

Create a function to compare the brackets from the stack with the arguments of the string and the size of the string and create a stack to store the characters and follow the following steps:-

Step1: Keep pushing the opening brackets into the stack and when a closing bracket is encountered then go to step 2.

Step2: Now check for the closing brackets, i.e., the type of bracket which is opened if that same type of bracket is closed then continue else the string is not balanced.

Step3: Return the empty stack, which indicates that the string was balanced.

Implementation Of The Above Algorithm:

Now let's see the implementation of the above algorithm,

#include <bits/stdc++.h>
using namespace std;
/*Function to check for the balanced string. */
int check(string str, int n)
{
	stack<int> s;
	char x;

	/*Push all the opening brackets into the stack. */
	for (int i = 0; i < n; i++)
	{
		if (str[i] == '(' || str[i] == '{' || str[i] == '[')
		{
			s.push(str[i]);
			continue;
		}

		if (s.empty())
			return 0;

		/*Check whether the closing bracket is of the same kind or not. */
		switch (str[i])
		{
			case ')':
				x = s.top();
				s.pop();
				if (x == '}' || x == ']')
					return 0;
				break;
			case '}':
				x = s.top();
				s.pop();
				if (x == ')' || x == ']')
					return 0;
				break;
			case ']':
				x = s.top();
				s.pop();
				if (x == ')' || x == '}')
					return 0;
				break;
		}
	}

	return (s.empty());
}

/*Driver program to test above function. */
int main()
{
	string str = "{()}[]";
	int n = str.length();

	if (check(str, n) != 0)
		cout << "True";
	else
		cout << "False";
	return 0;
}

Time Complexity Of The Above Algorithm is O(n).

The Output Of The Above Algorithm is: True.

Explanation Of The Above Algorithm:

• In the above algorithm, we see that the string comprises characters and here and the first opening bracket is pushed into the stack as shown in the above diagram.

• Next, we see another opening bracket '(' so we push it into the stack as shown in the above diagram.

• Now we see that the next bracket is a closing bracket, so we pop out the first block from the stack i.e., '(' and see that the current bracket is the same as the one that popped out, so we will continue as shown in the figure above.

• Now in the next step we see that the next bracket is also closing, so we pop out the next block and compare it with the current closing bracket and again find it to be the same, so we continue as shown in the above figure.

• Next is an opening bracket, so we will push it into the stack as shown in the above figure.

• And in the next step, the same closing bracket is found, so we will pop out the current block and return the empty stack denoted ‘True’ condition as shown in the above diagram.
• Hence, this way, we will find the final output of the given string of brackets.