Question

Let us define a multiplication operation on three symbols $\mathbf{a}\mathbf{,}\mathbf{b}\mathbf{,}\mathbf{c}\mathbf{}$according to the following table; thus $\mathbf{}\mathbf{ab}\mathbf{}\mathbf{=}\mathbf{}\mathbf{b}\mathbf{,}\mathbf{ba}\mathbf{}\mathbf{=}\mathbf{}\mathbf{c}$, and so on. Notice that the multiplication operation defined by the table is neither associative nor commutative.

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 . For example, on input $\mathit{b}\mathit{b}\mathit{b}\mathit{b}\mathit{a}\mathit{c}$your algorithm should return yes because$\mathbf{\left(}\mathbf{\right(}\mathit{b}\mathbf{\left(}\mathit{b}\mathit{b}\mathbf{\right)}\mathbf{\left)}\mathbf{\right(}\mathit{b}\mathit{a}\mathbf{\left)}\mathbf{\right)}\mathit{c}\mathbf{}\mathbf{=}\mathbf{}\mathit{a}$.

Short answer

We are going to use Dynamic Programming approach to examine the string and check if the strings can be parenthesize. In any dynamic programming, first approach is to create a sub-problem and the call it recursively.

Step-by-step solution

Defining the subproblem

Let us assume that$s[1\dots n]$be original string that appear in any order

Let $f(i,j)=setofallpossiblevaluesofthesubstrings[i\dots j]for1\le i\le j\le n$

Here, i and j are starting and ending position of a string and length of string would be $(j-i).$

If a belongs to$f(i,j)$, then our algorithm will return true, else false.

Thus, if our output ‘a’ belongs to $f(1,n)$that means there we can parenthesize the string.

Recursion Expressiona

Let us assume a variable ‘j’ is use to find the position where the string $s[i\dots \dots i+p]$is separated.

Now, because of ‘j’ we know about the split position of the string into two sub-result, and we can compute the result by taking union of the sub-results.

Thus we have,

localid="1657276451955" $\mathbf{f}\mathbf{(}\mathbf{i}\mathbf{,}\mathbf{i}\mathbf{+}\mathbf{k}\mathbf{)}\mathbf{=}\underset{\mathbf{i}\mathbf{\le }\mathbf{j}\mathbf{\le }\mathbf{i}\mathbf{+}\mathbf{k}}{\mathbf{\cup }}\left\{mn:m∊f(i,j),n∊f(j+1,i+k)\right\}$

Now for$i=j$

There would be only one character in entire$s[1\dots .n]$, which would be

• If$f(i,i,x)=TRUE$

Then$s\left[i\right]=x$

Else$FALSE$

• localid="1657277053120" $$\begin{gathered} Iff(i,i,x)=TRUE \\ Thens\left[i\right]=x \end{gathered}$$

Else localid="1657275948758" $FALSE$

Now if $i>j$, this means our substring $s[i\dots .j]$comprises of more than one character.

In this case if $s[i\dots .j]$can be split into two parts, then$f(i,j,x)=TRUE$.

Implementing Algorithm

We have matrix f() which will be storing value of ‘f’

Initiate$f(n,n,3)$

$$\begin{gathered} for(i=1ton) \\ for(j=1ton) \\ for(k∊a,b,c) \\ if(i==jANDp[i]==k) \\ f(i,j,k)=1 \\ else \\ f(i,j,k)=-1 \end{gathered}$$

function valid$(i,j,m)$

$if\left(f\right(i,j,m)\ne -1)$

return $f(i,j,m)$

Now in this if our program return value of matrix $f(i,j,m)$, this means the string would be parenthesize, and resulting expression will return ‘a’.