Если бы меня спросили, какой мой любимый векторный редактор, я бы, не задумываясь, ответил: PowerPoint.

Это началось с желания делать презентации, которые приятно смотреть. Меня всегда огорчало, как часто даже в хороших докладах используются мыльные, шакальные картинки – особенно там, где вполне можно обойтись аккуратными векторными схемами. В какой-то момент я решил: буду рисовать всё сам – фигурами прямо в PowerPoint.

Так я и жил, пока однажды мне не понадобилось вставить тысячу точек scatter-графика и нарисовать пару нейросетей. PNG не хотелось, руками – слишком лениво. Тогда я создал pptx-shapes – библиотеку, которая позволяет добавлять фигуры на слайды презентации.

Алгоритм сортировочной станции (Shunting Yard) был предложен Дейкстрой ещё в 1961 году и служит для преобразования математических выражений из привычной всем инфиксной записи (где операторы стоят между операндами, как в 1 + 2 * 3) в постфиксную (обратную польскую нотацию, 1 2 3 * +), удобную для дальнейшего вычисления. Однако есть один важный момент, который почти всегда упускается или замалчивается: алгоритм предполагает, что входное выражение уже синтаксически корректно.

Ни в Википедии, ни в большинстве обучающих статей вы не встретите слов о том, что выражения вроде + (1 2, 3 * 4 + ) или sin(+) должны вызывать ошибку. В лучшем случае они просто не вычисляются (что будет понятно лишь на этапе обработки в обратной польской записи), в худшем – дают бессмысленный результат. Алгоритм продолжает работать, даже если выражение изначально некорректно – и мало кто задумывается, почему это плохо.

Эта статья – попытка исправить эту несправедливую ситуацию, в которой мы не только реализуем алгоритм сортировочной станции «на максималках» с поддержкой констант, переменных, функций, унарных операторов, приоритетов и ассоциативности, но и добавим полноценную проверку корректности выражения по ходу разбора.

Привет, Хабр! В свободное от работы время по вечерам мне нравится воплощать в жизнь свои сумасшедшие идеи. В один из таких вечеров родилась мысль реализовать компилятор кода в машину Тьюринга. Осознав всю тщетность бытия сложность реализации, было принято решение начать с чего-то более простого – симулятора простенького процессора со своим собственным ассемблером, в котором команды выполнялись бы с помощью различных состояний машины Тьюринга, а данные хранились бы на одной ленте. В конечном итоге удалось осуществить практически первоначальную задумку, а именно получить одну единственную машину Тьюринга, способную выполнять скомпилированную из NASM подобного ассемблера программу без какого-либо внешнего взаимодействия.