Конвертер польской записи

Польская запись — способ представления математических и логических выражений без привычного размещения операторов между значениями. В обычной инфиксной записи оператор стоит между операндами, например A + B. В префиксной он стоит перед ними: + A B, а в постфиксной — после: A B +. Префиксную форму часто называют польской записью, а постфиксную — обратной польской записью, или RPN. Поскольку порядок оператора и операндов однозначен, таким выражениям обычно не нужны скобки. Конвертер выполняет четыре распространённых преобразования: инфиксная в префиксную, инфиксная в постфиксную, префиксная в инфиксную и постфиксная в инфиксную. Для инфиксного ввода распознаются идентификаторы, десятичные числа, скобки и операторы сложения, вычитания, умножения, деления и возведения в степень. Применяется стандартный приоритет: сначала степень, затем умножение и деление, затем сложение и вычитание. Скобки явно меняют порядок. Степень считается правоассоциативной, поэтому a ^ b ^ c означает a ^ (b ^ c). Преобразования из инфиксной записи используют алгоритм сортировочной станции для упорядочивания токенов по приоритету. Стек временно хранит операторы, а значения сразу поступают в вывод. Затем из полученной постфиксной последовательности строится префиксный результат. Для перехода из префиксной и постфиксной записи в инфиксную используется стек частичных выражений. При встрече оператора из него извлекаются два соответствующих операнда, объединяются, заключаются в скобки и возвращаются в стек. Последний элемент — полное инфиксное выражение. В префиксном и постфиксном вводе важны пробелы: они отделяют каждый операнд и оператор. Пишите * + A B C, а не *+ABC. В инфиксных выражениях пробелы необязательны, поскольку скобки и символы операторов разделяют токены. Конвертер сохраняет имена переменных и числовые значения, добавляя пробелы и скобки для удобства проверки. Преобразование записи полезно при изучении деревьев выражений, синтаксического анализа компиляторов, стековых машин, калькуляторов и структур данных. Постфиксные выражения можно вычислять слева направо с помощью простого стека, а префиксные — аналогично справа налево. Перевод привычной инфиксной формулы делает приоритет операторов явным и помогает проверять упражнения по разбору выражений.