Question

Can you solve this useing bottom-top approach (Dynamic Programin) if possible

6.6. Let us define a multiplication operation on three symbols a, b, c according to the following table; thus ab = b, ba = c, and so on. Notice that the multiplication operation defined by the table is neither associative nor commutative. b C b b a ba асс Find an efficient algorithm that examines a string of these symbols, say bbbbac, and decides whether or not it is possible to parenthesize the string in such a way that the value of the resulting expression is a. For example, on input bbbbac your algorithm should return yes because ((b(bb))(ba))c = a. ---L-AL WA

Answer 1

bottom-top approaches are more difficult to understand because you have to analyse that well , so due to limited time i'm going to use top- down approach becuase that is more intitutive.

so we will create a recursive function for this which will take two arguments one is string and another required output character.

now main part is that 'a', 'b', 'c' can occur with only 3 combination each so we can check combination of different substring and find wheter particular character can occur.

I've implemented a recursive definition for this have a look:

 #include<iostream> using namespace std; char matrix[3][3]={{'b','b','a'},{'c','b','a'},{'a','c','c'}}; bool charmult(string s,char a) {   int len=s.length();     if(len==0)              return 0;       if(len==1) //base case  {               return s[0]==a; //check if s[0] is character a  }       bool check=0;   for(int i=1;i<len;i++) //iterate the substring from 1 to last        {               string first=s.substr(0,i); //first string from 0 to i          string second=s.substr(i,len-i); //second string from i to last                 switch(a)               {                       case 'a':{ //when we want the combination to be a                               check=check || (charmult(first,'a')&&charmult(second,'c'));                             check=check || (charmult(first,'b')&&charmult(second,'c'));                             check=check || (charmult(first,'c')&&charmult(second,'a'));                             break;                  }                       case 'b':{ //when we want the combination to be b                               check=check || (charmult(first,'a')&&charmult(second,'a'));                             check=check || (charmult(first,'a')&&charmult(second,'b'));                             check=check || (charmult(first,'b')&&charmult(second,'b'));                             break;                  }                       case 'c':{ ////when we want the combination to be c                             check=check || (charmult(first,'b')&&charmult(second,'a'));                             check=check || (charmult(first,'c')&&charmult(second,'b'));                             check=check || (charmult(first,'c')&&charmult(second,'c'));                             break;                  }               }               if(check)                       break;  }       return check; } int main() {    string s="bbbbbbbb";    bool c=charmult(s,'a');         if(c) cout<<"yes"; else cout<<"no"; }

it's very easy to understand we are dynamically checking combinations and this algorithm runs in O( n2 )

I hope this will help you so please give positive ratings:)))