부울 괄호 문제


난이도 하드
자주 묻는 질문 아마존 링크드 인 Microsoft
동적 프로그래밍

문제 정책

“부울 괄호 문제”는 참과 거짓의 시퀀스와 그 사이에 부울 연산자 (AND, OR, XOR)가 주어 졌다고 말합니다. 전체 시퀀스가 ​​TRUE가되도록 주어진 시퀀스를 괄호로 묶는 방법의 수를 찾아야합니다. 주어진 부울 괄호 문제에서 "T"를 사용하여 True를, "F"를 사용하여 False를 참조합니다.

Symbol Sequence = {T,T}

Operator Sequence = {|}
1

설명 : 이것은 사소한 예이며, 문제가 무엇인지 시작하기 위해 여기에 표시됩니다. 따라서 시퀀스를 괄호로 묶는 한 가지 방법이 있습니다 (Y | T).

부울 괄호 문제

Symbol Sequence = {T, F, F}

Operator Sequence = {^, |}
2

설명 : 여기서 주어진 심볼 시퀀스는 두 가지 방법으로 괄호로 묶을 수 있습니다. 두 가지 방법은 (T ^ (F | F)) 및 ((T ^ F) | F)입니다.

부울 괄호 문제에 대한 접근 방식

“부울 괄호 문제”는 주어진 연산자를 사용하여 심볼 시퀀스를 괄호로 묶는 방법의 수를 찾아 시퀀스가 ​​참으로 평가해야한다고 말합니다. 따라서이를 위해 i에서 j까지 시퀀스 세그먼트를 괄호로 묶어 true가되는 여러 가지 방법을 저장하는 두 개의 2D 배열을 만듭니다. 마찬가지로, 다른 2D 배열은 동일하지만 세그먼트 결과는 거짓입니다. 해결하는 동안 하위 문제를 여러 번 해결해야합니다. 그래서 우리는 동적 프로그래밍 이 문제를 해결하기 위해.

문제는 다음과 유사합니다. 행렬 연쇄 곱셈 문제, 먼저 작은 하위 문제 (즉, 작은 세그먼트)를 해결합니다. 그리고 결과를 결합하여 초기 문제에 대한 답을 찾습니다. 우리가 사용하고 있기 때문에 동적 프로그래밍 접근 방식에 따라 몇 가지 기본 사례가 있어야합니다. 여기서 기본 사례는 길이 = 1 인 세그먼트입니다. 따라서 이에 따라 T 행렬과 F 행렬을 채울 것입니다. 작은 문제를 결합하여 더 큰 하위 문제를 해결할 때. 우리는 다음과 같은 특정 규칙을 따를 것입니다.

부울 괄호 문제

암호

부울 괄호 문제에 대한 C ++ 코드

#include<bits/stdc++.h>
using namespace std; 

int waysToParenthesize(string symbolSequence, string operatorSequence) 
{
    int n = symbolSequence.size();
  int T[n][n], F[n][n];
  memset(T, 0 ,sizeof T);
  memset(F, 0, sizeof F);
  
  //base case 
  for(int i=0;i<n;i++)
        if(symbolSequence[i] == 'T')
            T[i][i] = 1, F[i][i] = 0;
        else
            T[i][i] = 0, F[i][i] = 1;

    // Now solve the subproblems in bottom up manner
  for(int len=2;len<=n;len++)
  {
    for(int i=0;i<=n-len;i++) 
    {
        int j = i+len-1;
      T[i][j] = F[i][j] = 0;
      
      //Index of placing brackets
      for(int k=i;k<j;k++)
      {
        int waysik = T[i][k] + F[i][k]; 
        int wayskj = T[k+1][j] + F[k+1][j]; 
        if(operatorSequence[k] == '&') 
        { 
          T[i][j] += T[i][k]*T[k+1][j]; 
          F[i][j] += (waysik*wayskj - T[i][k]*T[k+1][j]); 
        } 
        else if(operatorSequence[k] == '|')
        { 
          F[i][j] += F[i][k]*F[k+1][j]; 
          T[i][j] += (waysik*wayskj - F[i][k]*F[k+1][j]); 
        } 
        else if(operatorSequence[k] == '^') 
        { 
          T[i][j] += F[i][k]*T[k+1][j] + T[i][k]*F[k+1][j]; 
          F[i][j] += T[i][k]*T[k+1][j] + F[i][k]*F[k+1][j]; 
        }
      } 
    } 
  }
  return T[0][n-1]; 
} 

int main() 
{
    string symbolSequence="";
    string operatorSequence="";
    cin>>symbolSequence>>operatorSequence;
    cout<<waysToParenthesize(symbolSequence, operatorSequence)<<endl;
} 
TTFT
|&^
4

부울 괄호 문제에 대한 Java 코드

import java.util.*;

class Main{
    
    static int waysToParenthesize(String symbolSequence, String operatorSequence) 
    {
        int n = symbolSequence.length();
    	int T[][] = new int[n][n];
    	int F[][] = new int[n][n];
    	for(int i=0;i<n;i++){
    	    for(int j=0;j<n;j++){
    	        T[i][j] = 0;
    	        F[i][j] = 0;
    	    }
    	}
    	
    	//base case
    	for(int i=0;i<n;i++){
            if(symbolSequence.charAt(i) == 'T'){
                T[i][i] = 1;
                F[i][i] = 0;
            }
            else{
                T[i][i] = 0;
                F[i][i] = 1;   
            }
    	}
    
        // Now solve the subproblems in bottom up manner
    	for(int len=2;len<=n;len++)
    	{
    		for(int i=0;i<=n-len;i++) 
    		{
    		    int j = i+len-1;
    			T[i][j] = 0;
    			F[i][j] = 0;
    			
    			//Index of placing brackets
    			for(int k=i;k<j;k++)
    			{
    				int waysik = T[i][k] + F[i][k]; 
    				int wayskj = T[k+1][j] + F[k+1][j]; 
    				if(operatorSequence.charAt(k) == '&') 
    				{ 
    					T[i][j] += T[i][k]*T[k+1][j]; 
    					F[i][j] += (waysik*wayskj - T[i][k]*T[k+1][j]); 
    				} 
    				else if(operatorSequence.charAt(k) == '|')
    				{ 
    					F[i][j] += F[i][k]*F[k+1][j]; 
    					T[i][j] += (waysik*wayskj - F[i][k]*F[k+1][j]); 
    				} 
    				else if(operatorSequence.charAt(k) == '^') 
    				{ 
    					T[i][j] += F[i][k]*T[k+1][j] + T[i][k]*F[k+1][j]; 
    					F[i][j] += T[i][k]*T[k+1][j] + F[i][k]*F[k+1][j]; 
    				}
    			} 
    		} 
    	}
    	return T[0][n-1]; 
    } 
    
    
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        String symbolSequence = sc.next();
        String operatorSequence = sc.next();
    	int ans = waysToParenthesize(symbolSequence, operatorSequence);
    	System.out.println(ans);
    }
}
TTFT
|&^
4

복잡성 분석

시간 복잡도 : O (N ^ 3)

Matrix Chain Multiplication 문제에서 볼 수있는 것과 유사합니다. 문제가 그 문제와 매우 유사하기 때문에 시간 복잡성도 동일합니다.

공간 복잡성 : O (N ^ 2)

여기서 우리는 2 개의 2D Dp 배열을 사용하여 하위 세그먼트를 괄호로 묶는 여러 가지 방법을 저장했습니다. 그리고 다른 하나는 거짓입니다. 따라서 다항식 공간 복잡도는 O (N ^ 2)입니다.