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.
- Initialize a string s, a stack of character type, and a variable to store the current index as 0.
- If the length of the string is equal to the current index, return 1 if the stack is empty else 0.
- 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.
- 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.
- 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.
- Create a variable res. Make a recursive call with the current index as current index+1 and temporary stack. Store its result in res.
- If res is equal to 1, return 1.
- If the old stack is empty, return 0.
- 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.