# Check for balanced parentheses by using Stacks (C++ program)

Here, we are going to learn **how to check for balanced parentheses by using stack using C++ program implementation?**

Submitted by **Shivi Saxena**, on July 05, 2019

**Problem Statement:**

Mathematical calculations can sometimes give incorrect and varied results. To overcome this problem we should use balanced brackets.

**Balanced brackets** are those who have a closing bracket corresponding to each of its opening bracket and in respective order. Here, I am considering square brackets **[ ]**, circular brackets **( )** and curly braces **{ }** as parentheses.

The stack is a type of data structure in which any data inserted is considered to be added on top of first entered data and any data deleted or removed from the data layer structure is deleted from the top only; thus this data structure works on the principle of **LIFO** (Last In First Out).

First, we make the user enter the number of test cases.Then for each corresponding test case we, call a function named balanced **parentheses()**. This function allows declaring a stack which can store datatype char. Then, the user is made to enter a string, and then it iterates by the length of string and whenever it approaches an opening bracket, that bracket is inserted (pushed i.e. push function)to the top of the stack. Whenever it comes across a closing bracket, the top element of the stack is deleted( or popped i.e pop function) with a corresponding opening bracket(as one opening and one corresponding closing bracket give empty Stack). While iterating through the length of the string, if it encounters any character other than the brackets(either opening or closing), then it won't affect our stack in any way.

In the end, the whole string has been iterated by its length times, then for the correct case our stack must be empty if it is not, then the brackets in the string entered are not balanced.

**Remeber the following examples:**

( ) :balanced brackets) ( :unbalanced brackets{ ( ) ( ) } :balanced brackets

See, in expression **[(3+5)(12)]** the brackets are correctly placed and give the result as **96**.

Whereas in **{[65-1))]2}** the two closing brackets aren't balanced with corresponding opening circular brackets and use of such terms should be taken care of while solving complex mathematical equations.

## C++ program to check balanced parentheses

//Updated by Anshuman Singh #include <iostream> //main header file #include <stack> using namespace std; void balance_parentheses(); int main() { int t; cout << "Enter number of test cases:"; cin >> t; for (int i = 0; i < t; i++) { //calling of function for checking of brackets balance_parentheses(); } return 0; } void balance_parentheses() { stack<char> a; string s; cout << "Enter string may or may not containing parentheses:"; cin >> s; int flag = 0; //flag is an arbitrary variable for (int i = 0; i < s.length(); i++) //for length of the string calculated by number of letters { if (s[i] == '{' || s[i] == '[' || s[i] == '(') { //push function to enter terms in a stack a.push(s[i]); flag = 1; } if (!a.empty()) { if (s[i] == '}') { if (a.top() == '{') // top of the stack { a.pop(); //pop function to delete terms from the top of array continue; } else break; } if (s[i] == ']') { if (a.top() == '[') { a.pop(); continue; } else break; } if (s[i] == ')') { if (a.top() == '(') { a.pop(); continue; } else break; } } else { break; } } if ((a.empty()) && (flag == 1)) cout << "YES" << endl; else cout << "NO" << endl; }

**Output**

Enter number of test cases:2 Enter string may or may not containing parentheses:}[])] NO Enter string may or may not containing parentheses:[]{}() YES

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions