Как превратить подстроку вида «min ( a, b )» в «a min b»?

Question

[diqueff]

Как преобразовать все подстроки вида min ( a , b ) в a min b?
На месте a и b может быть что угодно: числа, выражения, выражения с min (которые тоже нужно привести к необходимому виду)

Делаю все в Java, но хочется хотя бы понять, как в принципе реализовать алгоритм

Comments

[Василий Банников]

Советую сразу пропустить идею с регулярками.

Парсишь исходное выражение, получаешь из последовательности отдельных токенов - синтаксическое дерево.

Остаётся это дерево покрутить и собрать в новую строку.

Answer 1

[Wataru]

Решение попроще, за квадрат:
Пропустили ведущие и trailing пробелы, проверили, что строка начианется с "min" (иначе ничего делать не надо, возвращаем все).
Потом заведите счетчик открытых скобок, пройдитесь до первой запятой внутри одной пары скобок. Рекурсивно преобразуйте левую часть, добавьте к этому min и результат рекурсивного преобразования правой части (от зяпятой до закрывающей скобки в конце).

Решение поумнее, за линию:

Рекурсивная функция будет принимать строку и индекс того места, с которого надо обработать выражение. Возвращать будет результат преобразования и индекс конца обработанного выражения. Важно, обработаться может только часть строки.

Итак, функция, опять же, проверяет, что есть min. Если нет - возвращает всю строку до первой "," или непарной ")" - нужен счетчик открытых скобок.
В противном случае, пропускает "min", "(". Рекурсивно преобразовывает от этой позиции. Потом смотрит, что после позиции, которую вернула рекурсивная функция, лежит ",". Иначе - ошибка. Добавляет min к ответу, Рекурсивно преобразовывает оставшееся и добавляет к ответу. Проверяет, что дальше после позиции где закончила обработку рекурсивная функция лежит ")". Возвращает следующую за этим позицию.

Можно не возвращать преобразованную строку, а сразу все функции могут просто дописывать свой ответ в какое-то одно место. А возвращать int - индекс конца. Ну, или длину обработанной части строки - так даже понятнее.

Comments

[Alexandroppolus]

просто дописывать свой ответ в какое-то одно место.

смутно припоминаю, что это место называется StringBuffer

автор ещё не указал, надо ли добавлять скобки для подвыражений.
Например, было min(a, b + c), надо a min b + c или a min (b + c), второе выглядит как-то более явно

Answer 2

[mayton2019]

Поскольку случай - очень простой, то он решается шаблоном. Но если вместо а или б может быть
тоже выражение - тогда нужно определять свою грамматику. Например:
min ( min(a,b) , min (c,d) )
Тогда умные дядьки-теоретики берут язык описания грамматик. EBNF типа. И пытаются
свой новояз описать в терминах например EBNF https://en.wikipedia.org/wiki/Extended_Backus%E2%8...
Описывают что такое число. Какое оно. Отрицательное? Вещественное? Экспоентциальное?
Короче надо описать вообще все что может быть. Описывают функцию минимума.
Потом по этой грамматике создают парсер. Программно. И парсер на выходе выдает
дерево. Где корень - это вся грамматика а на листиках будут висеть числа. Или терминалки не помню
как они это называют. И вот когда ты уже получил это чортово дерево - можно ПРИСТУПАТЬ ко второй
части задачи - а именно к транформации в инфиксную форму. Но ты сначала реализуй хотя-бы первую
часть.

Это все теория и она требует погружения. Я думаю что эта задача и ей подобные в частных случаях
решаются проще. Если например твой язык поддерживает регулярки - то перечисли макс. число
вариантов что будут на входе и выбери через матчинг подходящий. Это - быстрее.