Заключение строки в скобки так, чтобы выражение имело заданное значение

Следующая задача взята из главы о динамическом программировании Vazirani et. al.

[6.6] Определим операцию умножения (×) на трех символах a; б; c согласно следующей таблице:

Следовательно, a × a = b, a × b = b и т. д.

Найдите эффективный алгоритм, который проверяет строку этих символов, скажем bbbbac, и решает можно ли заключить строку в скобки таким образом, чтобы значение результирующее выражение - это. Например, при вводе bbbbac ваш алгоритм должен возвращать да, потому что ((б (бб)) (ба)) с = а.

Вот мой подход: сопоставьте его с проблемой подсчета числа булевых скобок, как указано здесь . В этой задаче вам дано логическое выражение вида

T или F и T xor T

, и вам нужно найти количество способов заключить это в скобки, чтобы оно было истинным.

Мы можем рассматривать или , и , xor как операторы, которые следуют определенным правилам (T xor F = T и т. Д. ) и воздействовать на операнды, принимающие значения T или F. Для нашей исходной задачи мы можем рассматривать a, b, c как операнды с умножением (x) , как определено данной таблицей как обеспечивающие правила.

Имеет ли смысл описанный выше подход или есть более простой подход?