Balanced Expression with Replacement

In Balanced Expression with Replacement problem we have given a string s containing parenthesis i.e. ‘(‘, ‘)’, ‘[‘, ‘]’, ‘{‘, ‘}’. The string also contains x at some places as a replacement of parenthesis. Check if the string can be converted into an expression with valid parenthesis after replacing all the x’s with any of the parentheses.

Example

Input 

s = “{(x[x])}”

Output

 Yes

Input

s = “[{x}(x)]”

Output 

No

Algorithm

Now we know the problem statement of Balanced Expression with Replacement problem. So, we come to the below algorithm for the solution.

1. Initialize a string s, a stack of character type, and a variable to store the current index as 0.
2. If the length of the string is equal to the current index, return 1 if the stack is empty else 0.
3. Check if the character at the current index in the string is an opening parenthesis, push it in a stack, and return a recursive call with the current index as current index+1.
4. Else if character at current index in the string is a closing parenthesis, check if the stack is empty return 0 else check if the top of the stack is not equal to the opening parenthesis to the current character in the string, return 0. Pop the top and return a recursive call with the current index as current index+1.
5. Else if the character at the current index in the string is equal to x, create a temporary stack equal to the old one and push the character into it.
6. Create a variable res. Make a recursive call with the current index as current index+1 and temporary stack. Store its result in res.
7. If res is equal to 1, return 1.
8. If the old stack is empty, return 0.
9. Pop the top from the old stack and return a recursive call with the current index as current index+1 and old stack.

C++ Program for Balanced expression with replacement

#include <bits/stdc++.h> 
using namespace std; 
  
int isMatching(char a, char b){ 
    if((a == '{' && b == '}') || (a == '[' && b == ']') || (a == '(' && b == ')') || a == 'x') 
      return 1; 
    return 0; 
} 
  
int isBalanced(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 isBalanced(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 isBalanced(s, ele, ind + 1); 
    } 
  
    else if(s[ind] == 'x'){ 
        stack<char> tmp = ele; 
        tmp.push(s[ind]); 
        res = isBalanced(s, tmp, ind + 1); 
        if(res){ 
            return 1;
        }
        if(ele.empty()){ 
            return 0; 
        }
        ele.pop();
        
        return isBalanced(s, ele, ind + 1); 
    } 
} 
  
int main(){ 
    string s = "{(x[x])}"; 
    stack<char> ele;
    
    if(isBalanced(s, ele, 0)){  
        cout<<"Yes";   
    }
    
    else{ 
        cout<<"No";
    }
    return 0; 
}

Yes

Java Program for Balanced expression with replacement

import java.util.Stack; 
  
class BalancedExpression{ 
    
    static int isMatching(char a, char b){ 
        if((a == '{' && b == '}') || (a == '[' && b == ']') || (a == '(' && b == ')') || a == 'x'){ 
            return 1; 
        } 
        return 0; 
    } 
  
    static int isBalanced(String s, Stack<Character> ele, int ind){ 
  
        if(ind == s.length()){ 
            if(ele.size() == 0){ 
                return 1; 
            } 
            else{ 
                return 0; 
            } 
        } 
  
        char topEle; 
  
        int res; 
  
        if((s.charAt(ind) == '{') || (s.charAt(ind) == '(') || (s.charAt(ind) == '[')){ 
            ele.push(s.charAt(ind)); 
            return isBalanced(s, ele, ind + 1); 
        } 
        
        else if((s.charAt(ind) == '}') || (s.charAt(ind) == ')') || (s.charAt(ind) == ']')){ 
  
            if(ele.size() == 0){ 
                return 0; 
            } 
  
            topEle = ele.peek(); 
            ele.pop(); 
  
            if(isMatching(topEle, s.charAt(ind)) == 0){ 
                return 0; 
            } 
  
            return isBalanced(s, ele, ind + 1); 
        } 
        
        else if(s.charAt(ind) == 'x'){ 
            Stack<Character> tmp = new Stack<>(); 
            
            tmp.addAll(ele);  
            tmp.push(s.charAt(ind)); 
            res = isBalanced(s, tmp, ind + 1); 
            
            if(res == 1){ 
                return 1; 
            } 
            
            if(ele.size() == 0){ 
                return 0; 
            } 
            
            ele.pop(); 
            return isBalanced(s, ele, ind + 1); 
        } 
        return 1; 
    } 
  
    public static void main(String[] args) { 
  
        String s = "{(x[x])}"; 
        Stack<Character> ele = new Stack<Character>(); 
  
        if(isBalanced(s, ele, 0) != 0){ 
            System.out.println("Yes"); 
        } 
        
        else{ 
            System.out.println("No"); 
        } 
    } 
}

Yes

Complexity Analysis

Time Complexity: O((2^n)*n) where n is the length of the string.

Auxiliary Space: O(n) because we used n extra space in stack.

References