title: Parenthesizing a string so that expression takes a given value
body: <p>The following problem is from the chapter on Dynamic Programming by Vazirani et. al.</p>
  <blockquote>
  <p>[6.6]Let us define a multiplication operation(×) on three symbols a; b; c according to the following table:</p>
  <p><img src="https://i.imgur.com/HcUWS.png" alt="Multiplication table" /></p>
  <p>Therefore, a × a = b , a × b = b etc.</p>
  <p>Find an efficient algorithm that examines a string of these symbols, say <code>bbbbac</code>, and decides
  whether or not it is possible to parenthesize the string in such a way
  that the value of the resulting expression is <code>a</code>. For example, on input <code>bbbbac</code> your algorithm should return <strong>yes</strong> because <code>((b(bb))(ba))c = a</code>.</p>
  </blockquote>
  <h3>Here is my approach:</h3>
  <p>Map it to the problem of counting the number of boolean parenthesizations as given <strong><a href="https://stackoverflow.com/questions/6701812/counting-boolean-parenthesizations-implementation">here</a></strong>. In that problem, you are given a boolean expression of the form</p>
  <p>T <em>or</em> F <em>and</em> T <em>xor</em> T</p>
  <p>and you need to find the number of ways of parenthesizing this so that it evaluates to true.</p>
  <p>We can think of <em>or</em> , <em>and</em> , <em>xor</em> as operators which follow certain rules (T <em>xor</em> F = T etc.) and act on operands taking values T or F.</p>
  <p>For our original problem, we can think of a,b,c as operands with multiplication(x) <em>as defined by the given table</em> as providing the rules.</p>
  <p>Does the above approach make sense or is there a simpler approach ?</p>