Sea un alfabeto Σ = {a, b, c} con la siguiente "tabla de multiplicación" (donde cada fila corresponde al símbolo izquierdo y cada columna al derecho; por ejemplo, ab = b, ba = c, etc.):
| a | b | c | |
|---|---|---|---|
| a | b | b | a |
| b | c | b | a |
| c | a | c | c |
Nótese que dicha multiplicación no es asociativa ni conmutativa.
Dada una cadena x = x1 x2 … xn de caracteres de Σ, queremos determinar si es posible insertar paréntesis en x de forma que el valor de la expresión resultante sea a. Por ejemplo, si x = bbbba, la respuesta debe ser sí dado que (b(bb))(ba) = (bb)c = bc = a.
La entrada está compuesta por diversos casos de prueba, siendo cada uno de ellos una cadena de entre 1 y 100 caracteres del alfabeto Σ.
Para cada caso de prueba se debe escribir SI si es posible insertar paréntesis para conseguir una a y NO en caso contrario.
bbbba bacb abccba
SI NO SI