Преобразование из префиксной записи в инфиксную

#c_sharp #алгоритм #pascal #преобразование #польская_запись

Как преобразовать префиксную запись (польскую нотацию) в инфиксную. Запись может
содержать: '(', ')', '+', '-', '*', '/', '0..9', 'a..z'. Подскажите алгоритм решения
данной задачи (описание, Pascal, C#), какие структуры данных нужно использовать?
    

Ответы

Ответ 1

Очевидный честный алгоритм — распарсить польскую запись в дерево. Имея дерево, можно
рекурсивно строить любые формы записи (а также оптимизировать, компилировать и выполнять,
что угодно).

Для записи

− 5 * 6 7


вы делаете следующие шаги:


Видите минус, аллоцируете узел бинарной операции с двумя операндами.
Читаете первый операнд.


видите 5, это и есть первый операнд, аллоцируете для него листовой узел с константой

Читаете второй операнд.


видите *, аллоцируете для него узел бинарной операции с двумя операндами
читаете первый операнд


видите 6, аллоцируете для него листовой узел с константой
видите 7, аллоцируете для него листовой узел с константой






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


Прочитать один токен
Если это константа, она и есть результат
Если это бинарная операция, запомнить её тип, рекурсивно получить значение операндов,
вывести выражение, заключив его в скобки, чтобы не думать о приоритете операторов.
дополните правилами для других типов узлов по вкусу


Ответ 2

Если лишние скобки в результате - не проблема, то можно сконвертировать обычной рекурсией:

class Program
{
    static void Main(string[] args)
    {
        string source = "- * / 15 - 7 + 1 1 3 + 2 + 1 1";

        var tokens = new Queue(source.Split());

        Console.WriteLine(DoConvert(tokens));
    }

    private static string[] operators = new string[] { "+", "-", "*", "/" };

    private static string DoConvert(Queue tokens)
    {
        var token = tokens.Dequeue();

        if (operators.Contains(token))
        {
            return String.Format("({0} {1} {2})", DoConvert(tokens), token, DoConvert(tokens));
        }
        else
        {
            return token;
        }
    }
}