We aim to write a program that checks whether the parentheses in an expression are balanced. This means that the closing symbol should match the most recently seen opening symbol. e.g. {()} is legal, {() ({})} is legal, but {((} and {(}) are not legal.
A string consisting of brackets "{, }, (, ), [, ]" .
The function returns true if the expression is balanced. Otherwise, it returns false.
We will use the built-in stack data structure provided by the C++ library. Remember that the stack is FIFO (First In First Out) data structure. Here are the steps of the algorithm which checks balanced parentheses:
{, [, and ( then push it in the stack.}, ], and ), then pop the recent character from the stack and check if it is the corresponding opening bracket. If it is not the opening bracket, then the input is unbalanced. We can see this here:#include<iostream>#include<stack>using namespace std;bool isBalanced(string expr) {stack <char> s;char ch;for (int i=0; i < expr.length(); i++) { //for each character in the input, we check various possibilitiesif (expr[i] =='('||expr[i]=='['||expr[i]=='{') { //when it is an opening bracket, we push in stacks.push(expr[i]);continue;}if (s.empty()) //no opening bracket, there must be some closing bracket in the beginning so its unbalancedreturn false;switch (expr[i]) {case ')': //for closing parenthesis, pop it and check if opening parenthesis is presentch = s.top();s.pop();if (ch != '(')return false;break;case '}': //for closing braces, pop it and check if opening brace is presentch = s.top();s.pop();if (ch != '{')return false;break;case ']': //for closing square bracket, pop it and check if closing square bracket is presentch = s.top();s.pop();if (ch != '[')return false;break;}}return (s.empty()); //when stack is empty, return true}main() {string expr = "[{}(){()}]";if (isBalanced(expr))cout << "Balanced Parenthesis!!";elsecout << "Not Balanced Parenthesis";}
Free Resources