Extend and implement the Dynamic Programming Algorithm in the last example of the relevant slides so that it prints a parenthesized expression yielding the goal or "No parenthesization possible." if...

Relevant slide part is added too. Please use c++ as the language. Thanks

Extracted text: Extend and implement the Dynamic Programming Algorithm in the last example of the relevant slides so that it prints a parenthesized expression yielding the goal or "No parenthesization possible." if no such parenthesization exists. Input format (no need to check its validity): The first line contains a positive integer (say n). The symbols: The second line contains at leastn characters (if it contains more, only the first n are relevant). These characters are the symbols of the alphabet. The last symbol is the "goal". The operation: The following n lines contain at least n characters each (if a line contains more characters, only the first n are relevant). This is an nxn matrix containing the results of the operations. Expression: The last line of the input contains a sequence of characters, consisting of the valid symbols for which you have to seek for a parenthesization. A sample input: 3 abc aac baa саа caaccb and corresponding possible outputs (not exhaustive): (C((aa)((cc)b)) (c(a(a((cc)b)))) (((ca)a)((cc)b)) (((ca)a)((cc)b))


Extracted text: • Let us define a binary operation ® on three symbols a, b, c according to the following table; thus a b = b , b® a = c , and so on. Notice that the operation defined by the table is neither associative nor commutative. a b C a b a a Describe 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 p = a. For example, on input bbbbac your algorithm should return yes because ((b® (b® b)) ® (b ® a)) ® c = a.