Как вы рекурсивно заменяете вхождения строки в массиве

Question

Итак, рассмотрим класс A с двумя строковыми переменными "name" и "value"

класс B содержит переменную Set of A

Set<A> allVariables 

это набор, который будет выглядеть так

A.name="$var1"
A.value = "x+10>2"

A.name="$var2"
A.value="11+y%10==0"

A.name="$var3"
A.value="$var1 && $var2"

Что мне нужно сделать, это оценить эти выражения. Я использую jexl для этого. Мне нужно перебрать Set и заменить имена этих переменных их соответствующими значениями.

В этом случае объект с именем $var3 необходимо заменить на "x+10>2 && 11+y%10==0"

Как мне это сделать?

Answer 1

Вы создаете 2 Hashmap, translated а также toTranslate,

Вы анализируете свой набор.

Для каждого A в вашем наборе вы смотрите на значение. Если значение содержит любое количество $element (начато $ знак), вы ищете это $element в ваших переведенных ключах Hashmap.

Если это там, вы заменяете вхождения $element по значению, найденному в вашей переведенной хэш-карте.

Вы делаете это для каждого другого $element Вы нашли в своем объекте.

Я упал $element Вы добавили свой объект А в translated hashmap (ключ = имя, значение = значение).

Иначе, вы добавляете его в свой toTranslate HashMap.

После того, как весь ваш сет проанализирован, у вас есть 2 хэш-карты.

Вы создаете цикл while: while toTranslate hashmap не пустой, вы берете каждое значение и пытаетесь перевести $element в нем те, кто в вашем translate HashMap.

Будьте осторожны, вы можете закончить бесконечным циклом. Хорошо бы убедиться, что каждый раз, когда вы включаете toTranslate hashmap, количество его элементов сокращено. Если нет, то вы в бесконечном цикле.

Answer 2

Я не думаю, что это должно быть рекурсивным. Я думаю, что только это будет работать:

bool madeReplacement;

делать:

bool madeReplacement = false

Для каждого члена набора X:

Для каждого другого члена набора Y:

Замените все экземпляры Y.name на Y.value в X.value. Если вы заменили что-либо, madeReplacement = true.

while (madeReplacement)

---

Пример:

$ var1 - это значение 1

$var2 - это значение $ var1

$ var3 - это значение $var2 + 2

$ var3.value содержит $var2, замените $var2 на $ var1 -> $ var1 + 2

$var2.value содержит $ var1, замените $ var1 на 1 -> 1

$ var3.value содержит $ var1, замените $ var1 на 1 -> 1 + 2

Никакое значение не содержит никакого другого имени, выполнение завершено.

---

Даже если мы "оценили не по порядку", мы все равно получили правильный ответ. Тем не менее, этот алгоритм может быть O(n^3) в худшем случае (представьте, если у вас было n переменных, которые ссылались друг на друга в длинной цепочке, и вы начали замену не с того конца). Один из способов решения этой проблемы заключается в том, чтобы, когда X.value содержит Y.name, сначала рекурсивно оценивать Y.value (выполняя тот же цикл над остальным набором). Это делает O(n^2) наихудшим случаем, поэтому ваше подозрение в правильности рекурсивного подхода может быть правильным;)

(Я не был уверен, что имена переменных гарантированно начинаются с $, поэтому я написал это, чтобы это не имело значения)