C++ Balanced expression with replacement

A balanced expression of parentheses is an expression that contains pairs of all sort of parentheses together in a correct order.this means that for every opening parentheses there is a closing parentheses in proper order of parentheses i.e. { }.

let's take a few examples to understand the concept better −

Expression − {([][]{})({}[]{})}

Output − balanced

Explanation − we can see that for every opening parentheses there is a closing parentheses. all the parentheses lying between an opening parentheses and closing parentheses in Pairs.

Output − not balance

Explanation − there are some unordered pairs of parentheses which makes the the expression unbalanced.

In this problem called balance expression with replacement, we are given a string that contains an expression of these brackets ‘{’ , ‘}’ , ‘[’ , ‘]’ , ‘(’ , ‘)’ . there are some places where the brackets are missing and “*” is placed instead of it. And we have to check that weather on replacing all the asterisk symbols with appropriate brackets can the given expression is is able to become a valid expression.

Example

Input  − exp = “{[*(*)]}”

Output  − the expression can be balanced

Explanation  − There are two symbols that need to be replaced. And on replacement will become {[(())]}

Input  − exp = “[(*){}{{}}]”

Output  − the expression cannot be balanced

Explanation − There is one symbol that need to be replaced. And on replacement of * with any of the brackets the expression cannot be balanced.

Now since we have a clear understanding of the problem, we can generate a solution for this problem. To check whether a given parentheses expression will be balanced or not we will use stack data structure to perform our tasks.

The operation that are performed to accomplish this task are −

• Traverse every element of the string expression and do −

• When an opening bracket is encountered in the expression i.e ‘{’ , ‘[’ , ‘(’ , push the element in the stack.

• When a closing bracket is encountered in the expression i.e. ‘}’ , ‘]’ , ‘)’. Pop the element at the top of the stack and check if this is a matching opening for the encountered closing bracket.

  • If both parentheses matched, then move to the next element of the expression (step 1).

  • If both parentheses do not match, then the expression is not balanced.

• When an * is encountered in the expression which can be an opening as well as closing bracket. Then,

  • First treat it as opening bracket and push it into the stack and find a matching closing bracket using recursive call for the next element. If this results in fasle, follow the next step

  • Treat it as closing bracket , it must match the top of stack then pop the top of stack.

  • It the closing value of * does not match an opening return not balanced.

• Print the statement based on the outcome.

Example

Based on this solution let’s create a program

#include <bits/stdc++.h> using namespace std; int isMatching(char a, char b){    if ((a == '{' &amp; b == '}') || (a == '[' &amp; b == ']') || (a == '(' &amp; b == ')') || a == '*')       return 1;    return 0; } int isBalancedexpression(string s, stack<char> ele, int ind){    if (ind == s.length())       return ele.empty();    char topEle;    int res;    if (s[ind] == '{' || s[ind] == '(' || s[ind] == '[') {       ele.push(s[ind]);       return isBalancedexpression(s, ele, ind + 1);    }    else if (s[ind] == '}' || s[ind] == ')' || s[ind] == ']') {       if (ele.empty())          return 0;       topEle = ele.top();       ele.pop();       if (!isMatching(topEle, s[ind]))          return 0;       return isBalancedexpression(s, ele, ind + 1);    }    else if (s[ind] == '*') {       stack<char> tmp = ele;       tmp.push(s[ind]);       res = isBalancedexpression(s, tmp, ind + 1);       if (res)          return 1;       if (ele.empty())          return 0;       ele.pop();       return isBalancedexpression(s, ele, ind + 1);    } } int main(){    string s = "{[*(*)]}";    stack ele;    if (isBalancedexpression(s, ele, 0))       cout << "Balanced";    else       cout << "Not Balanced";    return 0; }

Output

Balanced