באָאָלעאַן פּאַרענטהעסיזאַטיאָן פּראָבלעם


שוועריקייט לעוועל שווער
אָפט געבעטן אין אַמאַזאָן לינקעדין מייקראָסאָפֿט
דינאַמיש פּראָגראַממינג

פּראָבלעם סטאַטעמענט

"באָאָלעאַן פּאַרענטהעסיזאַטיאָן פּראָבלעם" שטאַטן אַז מיר זענען געגעבן אַ סיקוואַנס פון אמת און פאַלש, און עטלעכע באָאָלעאַן אָפּערייטערז (AND, OR, XOR) צווישן זיי. מיר דאַרפֿן צו געפֿינען די נומער פון וועגן צו קלאַמערן די געגעבן סיקוואַנס אַזוי אַז די גאנצע סיקוואַנס רעזולטאַטן אין אמת. אין דעם געגעבן באָאָלעאַן פּאַרענטהיזאַטיאָן פּראָבלעם, מיר וועלן אָפּשיקן אמת ניצן "T" און "פאַלש" מיט "F".

בייַשפּיל

Symbol Sequence = {T,T}

Operator Sequence = {|}
1

דערקלערונג: דאָס איז אַ נישטיק בייַשפּיל, וואָס איז געוויזן דאָ נאָר צו באַקומען די אָנהייב פון וואָס די פּראָבלעם איז אַלע וועגן. אַזוי, עס איז בלויז אַ איין וועג פון פּאַרענטיזינג די סיקוואַנס. וואָס איז (Y | T).

באָאָלעאַן פּאַרענטהעסיזאַטיאָן פּראָבלעם

Symbol Sequence = {T, F, F}

Operator Sequence = {^, |}
2

דערקלערונג: דאָ מיר קענען קלאַמערן אונדזער געגעבן סימבאָל סיקוואַנס איז צוויי וועגן. די צוויי וועגן זענען (T ^ (F | F)) און ((T ^ F) | F).

צוגאַנג פֿאַר באָאָלעאַן פּאַרענטהעסיזאַטיאָן פּראָבלעם

"באָאָלעאַן פּאַרענטהעסיזאַטיאָן פּראָבלעם" שטאַטן אַז מיר דאַרפֿן צו געפֿינען די נומער פון וועגן צו קלאַמערן די סימבאָל סיקוואַנס ניצן די אָפּערייטערז אַזאַ אַז די סיקוואַנס עוואַלואַטעס עס אין אמת. דעריבער, מיר מאַכן צוויי 2 ד ערייז, איין פֿאַר סטאָרידזש די נומער פון וועגן צו קלאַמערן אַ סיקוואַנס פון סיקוואַנס פון י צו דזש, ריזאַלטינג אין אמת. סימילאַרלי, אן אנדער 2 ד מענגע דינאָוץ די זעלבע אָבער די אָפּשניט רעזולטאַטן אין פאַלש. בשעת סאַלווינג, מיר דאַרפֿן צו סאָלווע די סאַב-פּראָבלעמס קייפל מאָל. אַזוי מיר פּרובירן צו נוצן דינאַמיש פּראָגראַממינג פֿאַר סאַלווינג דעם פּראָבלעם.

די פּראָבלעם איז ענלעך צו די מאַטריץ טשאַין קייפל פּראָבלעם, ווו ערשטער מיר סאָלווע סמאָלער סאַב-פּראָבלעמס (i, e, קלענערער סעגמאַנץ). און קאַמביינינג דער רעזולטאַט, מיר געפֿינען דעם ענטפער צו דער ערשט פּראָבלעם. זינט מיר נוצן אַ דינאַמיש פּראָגראַממינג צוגאַנג, מיר מוזן האָבן עטלעכע באַזע קאַסעס, די באַזע קאַסעס דאָ זענען סעגמאַנץ פון לענג = 1. אַזוי, מיר וועלן פּלאָמבירן די ה מאַטריץ און 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

דזשאַוואַ קאָוד פֿאַר באָאָלעאַן פּאַרענטהעסיזאַטיאָן פּראָבלעם

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

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי: אָ (N ^ 3)

ענלעך צו וואָס מיר זען אין די מאַטריץ טשאַין קייפל פּראָבלעם. זינט די פּראָבלעם איז גאַנץ ענלעך צו דעם, די צייט קאַמפּלעקסיטי איז אויך די זעלבע.

אָרט קאַמפּלעקסיטי: אָ (N ^ 2)

דאָ מיר האָבן געוויינט 2 2 ד דפּ ערייז איינער פֿאַר סטאָרידזש די נומער פון וועגן צו פּאַרענטייז אַ סאַב-אָפּשניט אַזוי אַז עס רעזולטאַטן אין אמת. און די אנדערע פֿאַר פאַלש. אזוי געבן אונדז אַ פּאָלינאָמיאַל פּלאַץ קאַמפּלעקסיטי פון אָ (N ^ 2).