Given an expression containing opening and closing braces, check if it is balanced or not.

For example,

{[{}{}]}[()], {{}{}}, []{}() are balanced expressions.

{()}[), {(}) are not balanced.

The idea is to use a stack to solve this problem. We traverse the given expression and

- If current character in the expression is a opening brace ‘(‘ or ‘{‘ or ‘[‘, we push it to the stack.

- If current character in the expression is a closing brace ‘)’ or ‘}’ or ‘]’, we pop a character from the stack and we return false if the popped character if not an opening brace or it does not pair with current character of the expression. Also if stack is found to be empty, that means the number of opening braces is less than number of closing brace at that point, so expression cannot be balanced.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <bits/stdc++.h> using namespace std; // Function to check if given expression is balanced or not bool balParenthesis(string exp) { // take a empty stack of characters stack<char> stack; // traverse the input expression for (int i = 0; i < exp.length(); i++) { // if current char in the expression is a opening brace, // push it to the stack if (exp[i] == '(' || exp[i] == '{' || exp[i] == '[') stack.push(exp[i]); // if current char in the expression is a closing brace if (exp[i] == ')' || exp[i] == '}' || exp[i] == ']') { // return false if mismatch is found (i.e. if stack is empty, // the number of opening braces is less than number of closing // brace, so expression cannot be balanced) if(stack.empty()) return false; // pop character from the stack char top = stack.top(); stack.pop(); // if the popped character if not an opening brace or does // not pair with current character of the expression if ((top == '(' && exp[i] != ')') || (top == '{' && exp[i] != '}') || (top == '[' && exp[i] != ']')) return false; } } // expression is balanced only if stack is empty at this point return stack.empty(); } // main function int main() { string exp = "{()}[{}]"; if (balParenthesis(exp)) cout << "The expression is balanced"; else cout << "The expression is not balanced"; return 0; } |

**Output: **

The expression is balanced

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n). Here, n is the length of the input expression.

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂