1.

Write a programme to check whether the pairs and ordering of "", "", "(", ")", "[", "]" in the expression string expression are balanced or not.

Answer»

By balanced string, it is meant that every opening parenthesis should have its corresponding closing braces and there must not be redundant closing braces.

Example :

INPUT :

“[()]{}{[()()]()}” 

OUTPUT :

Balanced

Input:

[[

Output:

Not Balanced

Approach:

We create a character stack and now look through the expression string. If the current character is a beginning bracket ('(', ", or '['), stack it. If the current character is a closing bracket (') or " or ']'), pop from the stack; if the popped character is the matching starting bracket, all is well; otherwise, the BRACKETS are unbalanced. If some starting brackets remain in the stack after traversal, the stack is said to be "unbalanced."

Code:

#include <bits/stdc++.h>using namespace STD;// function to check if the given expression is balanced or notbool checkBalancedExpression(string str){ stack<char> char_stack; char top_element; // Traversing the Expression for (int i = 0; i < str.length(); i++) { if (str[i] == '(' || str[i] == '[' || str[i] == '{') { // We push the character in the stack char_stack.push(str[i]); continue; } // We check if the stack is empty. If it is empty, then it is an unbalanced expression since there must be a corresponding opening bracket before the closing one. if (char_stack.empty()) return false; switch (str[i]) { case ')': top_element = char_stack.top(); char_stack.pop(); if (top_element == '{' || top_element == '[') return false; break; case '}': top_element = char_stack.top(); char_stack.pop(); if (top_element == '(' || top_element == '[') return false; break; case ']': top_element = char_stack.top(); char_stack.pop(); if (top_element == '(' || top_element == '{') return false; break; } } // The stack should be empty at this point for a balanced expression return (char_stack.empty());}int main(){ string str = "[]{}()"; if (checkBalancedExpression(str)) cout << "Balanced"; else cout << "Not Balanced"; return 0;}

Output :

Balanced

Explanation:

In the above code, we create a function checkBalancedExpression which takes the input of an expression string and CHECKS whether the string is balanced or not. We start traversing the expression. Whenever we encounter an opening bracket, we push it in the stack. In the case of a closing bracket, we first check if the stack is empty or not. If it is empty, we directly return false otherwise, we check if the top element has the corresponding opening bracket or not. 


Discussion

No Comment Found

Related InterviewSolutions