Given an string containing opening and closing braces, check if it represents a balanced expression or not.
For example,
{[{}{}]}[()], {{}{}}, []{}() are balanced expressions.
{()}[), {(}) are not balanced.
We can 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++
|
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 57 58 59 60 |
#include <iostream> #include <stack> 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; } |
Java
|
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 57 58 59 60 |
import java.util.Stack; class BalParenthesis { // Function to check if given expression is balanced or not public static boolean balParenthesis(String exp) { // take a empty stack of characters Stack<Character> stack = new 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.charAt(i) == '(' || exp.charAt(i) == '{' || exp.charAt(i) == '[') { stack.push(exp.charAt(i)); } // if current char in the expression is a closing brace if (exp.charAt(i) == ')' || exp.charAt(i) == '}' || exp.charAt(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 Character 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.charAt(i) != ')') || (top == '{' && exp.charAt(i) != '}') || (top == '[' && exp.charAt(i) != ']')) { return false; } } } // expression is balanced only if stack is empty at this point return stack.empty(); } public static void main(String[] args) { String exp = "{()}[{}]"; if (balParenthesis(exp)) { System.out.println("The expression is balanced"); } else { System.out.println("The expression is not balanced"); } } } |
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.
(3 votes, average: 5.00 out of 5)
Loading...
Thanks for reading.
Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply