Stack: Given a string expression, check if it is balanced expression

Problem Statement:

You are given a string that has braces of types “{ }”, “[ ]”, “( )”.

In some places it will be marked as ‘x’.

You need to check if by replacing all ‘x’ with correct bracket, will the string be a valid bracket sequence.

Example:

Input: S = [ x }]
Output: Yes

when you replace ‘x’ with ‘{‘, the expression will become balanced.

Solution Explanation:

Solution is very simple.

We will use stack data structure to solve this problem.

If the braces is a open brace ‘{‘ or ‘(‘ or ‘[‘, then push into the stack.

If the braces is a close brace ‘}’ or ‘]’ or ‘)’, then pop the top element from the stack and check if it is matching with the opening brace or not.

If it matches, then move to the next element in the string, if not, the string is not balanced.

Now, if the current element is ‘x’, then it might be a starting brace or a closing brace.

We assume it as a starting brace, recursive call for the next element by pushing into the stack and check if the string is balanced or not.

Now if the result of recursion is false, then x is a closing brace and check if it matches with the top of the stack and proceed accordingly.

Time Complexity: O((2^n) * n)
Space Complexity: O(N)

Code Solution

#include <iostream>
#include <stack>

using namespace std;


int isMatching(char a, char b)
{
    if ((a == '{' && b == '}') || (a == '[' && b == ']')
        || (a == '(' && b == ')') || a == 'x')
        return 1;
    return 0;
}

int solution(string s, stack<char> ele, int index)
{

    if (index == s.length()) 
        return ele.empty();

    char topElement;

    int res;

    if (s[index] == '{' || s[index] == '(' || s[index] == '[') 
    {
        ele.push(s[index]);
        return solution(s, ele, index + 1);
    }

    else if (s[index] == '}' || s[index] == ')' || s[index] == ']') 
    {

        if (ele.empty()) 
            return 0;

        topElement = ele.top();
        ele.pop();

        if (!isMatching(topElement, s[index])) 
            return 0;
        
        return solution(s, ele, index + 1);
    }

    else if (s[index] == 'x') 
    {
        stack<char> tmp = ele;
        tmp.push(s[index]);
        res = solution(s, tmp, index + 1);
        if (res)
            return 1;
        if (ele.empty())
            return 0;
        ele.pop();
        return solution(s, ele, index + 1);
    }
   return 0;
}

int main()
{
    string s = "[x}]";
    stack<char> ele;
  
    if(s.length()%2==0)
    {
        if (solution(s, ele, 0)) 
            cout << "Balanced";    
        else 
            cout << "Not Balanced"; 
    }
    else
    {
          cout << "Not Balanced"; 
    }
    return 0;
}

Output

Balanced