Balanced Expression with Replacement 문제에서는 '(', ')', '[', ']', '{', '}'와 같은 괄호를 포함하는 문자열 s를 제공했습니다. 그만큼 현 또한 괄호 대신 x를 포함합니다. 모든 x를 괄호로 바꾼 후 문자열을 유효한 괄호가있는 표현식으로 변환 할 수 있는지 확인하십시오.
차례
예
입력
s =“{(x [x])}”
산출
가능
입력
s =“[{x} (x)]”
산출
아니
암호알고리즘
이제 우리는 균형 잡힌 표현과 교체 문제의 문제 진술을 알고 있습니다. 그래서 우리는 솔루션에 대한 아래 알고리즘에 왔습니다.
- 문자열 s, 문자 유형 스택 및 변수를 초기화하여 현재 인덱스를 0으로 저장합니다.
- 문자열의 길이가 현재 인덱스와 같으면 스택이 비어 있으면 1을 반환하고 0을 반환합니다.
- 문자열의 현재 인덱스에있는 문자가 여는 괄호인지 확인하고 스택에 푸시 한 다음 현재 인덱스를 현재 인덱스 +1로 사용하여 재귀 호출을 반환합니다.
- 그렇지 않으면 문자열의 현재 인덱스에있는 문자가 닫는 괄호이면 스택이 비어 있는지 확인하고 0을 반환합니다. 그렇지 않으면 스택의 맨 위가 문자열의 현재 문자에 대한 여는 괄호와 같지 않은지 확인하고 0을 반환합니다. top 및 현재 인덱스를 현재 인덱스 +1로 사용하여 재귀 호출을 반환합니다.
- 그렇지 않으면 문자열의 현재 인덱스에있는 문자가 x와 같으면 이전 스택과 동일한 임시 스택을 만들고 그 문자를 밀어 넣습니다.
- 변수 res를 만듭니다. 현재 인덱스를 현재 인덱스 +1 및 임시 스택으로 사용하여 재귀 호출을 수행합니다. 결과를 res에 저장하십시오.
- res가 1이면 1을 반환합니다.
- 이전 스택이 비어 있으면 0을 반환합니다.
- 이전 스택에서 맨 위를 팝하고 현재 인덱스가 현재 인덱스 +1 및 이전 스택 인 재귀 호출을 반환합니다.
대체가있는 균형 잡힌 표현을위한 C ++ 프로그램
#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
균형 잡힌 표현을위한 자바 프로그램 (대체 포함)
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
복잡성 분석
시간 복잡성 : O ((2 ^ n) * n) 여기서 n은 문자열의 길이입니다.
보조 공간 : O (n) 스택에 n 개의 추가 공간을 사용했기 때문입니다.
