# Using STL to verify Brackets or Parentheses Combination in an Expression

Write a program to test whether the pairs and orders of ““, “”, “(“, “)”, “[“, “]” in the expression string exp are correct.

Example:

Input:

given string = " [[[{}()]]]

Output:

Given string of brackets is balanced

## Check for Balanced Brackets in an expression

### 1)Algorithm

• Make an empty character stack and traverse the characters in the string one by one.
• If an open bracket is encountered, it should be pushed into the stack.
• If a close bracket is encountered, match it with its open bracket counterpart at the top of the stack.
• If the match is successful, remove the character from the stack.
• If the match is a failure, RETURN FALSE.
• Return TRUE if the stack is empty; otherwise, return FALSE.

### 2)Check Balanced parentheses

Below is the implementation:

#include <bits/stdc++.h>
using namespace std;
// function which checkOpen brackets
bool checkOpenBracket(char character,
map<char, char> bracketMap)
{
map<char, char>::iterator itr = bracketMap.begin();
// Traverse the bracket map till end of it
while (
itr
!= bracketMap.end()) { // if the value of the given
// key is equal to given
// character then return true
if (itr->second == character) {
return true;
}
// increment the iterator to next key
itr++;
}
return false;
}
// function which checks the balanced bracket
bool checkBalancedBracket(string str)
{ // initializing a stack which stores the characters
stack<char> charstack;
// initializing a map which stores the open and closed
// brackets and parenthesis
map<char, char> parantheses_map;
// initalizing the map with open and closed bracket
// characters
parantheses_map['}'] = '{';
parantheses_map[')'] = '(';
parantheses_map[']'] = '[';
// Traverse the string
for (int i = 0; i < str.size(); i++) {
// checking if it is open bracket
if (checkOpenBracket(str[i], parantheses_map))
charstack.push(str[i]);
if (parantheses_map.find(str[i])
!= parantheses_map.end()) {
if (charstack.empty())
// Return false if the character stack is empty
return false;
if (charstack.top()
!= parantheses_map[str[i]]) {
return false;
}
else
charstack.pop();
}
}
if (charstack.size() > 0)
return false;
else
return true;
}
int main()
{ // passing brackets string to checkBalancedBracket
// function
if (checkBalancedBracket("{{[[]]()}}"))
cout << "Given string of brackets is balanced"
<< endl;
else
cout << "Given string og brackets is not balanced"
<< endl;

return 0;
}

Output:

Given string of brackets is balanced

Related Programs: