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

Второй момент уже более труден, нужно как-то ввести поддержку контроля передаваемых параметров в функции, иначе возможна ситуация, когда при неправильном количестве параметров возникнет ошибка. Но возникнет она уже после вызова функции и интерпретатор не сможет правильно идентифицировать причину ошибки. Понятно, что нужно как-то уметь отличать в стэке параметры функций от простых чисел и переменных.

Ну, и малость портит впечатление таблица приоритетов. Все-таки, можно эту проблему решить по другому. Как Вы правильно заметили, токен ’)’ выбивается из остальных своей спецификой. Учтем так же, что нам необходимо распознавать унарные операции. Их распознать легко, они могут следовать только за открывающей скобкой, либо сразу после другой операции, либо в самом начале строки. Таким образом при "расфасовке" необходимо распознавать следующие ситуации:

’(’ - выставляем флаг возможной унарной операции

’)’ - раскрутка стэка и сброс флага унарной операции

op - любая операция, выставляем флаг унарной возможной операции

symb - это все, что не относится к предыдущим категориям, сбрасываем флаг унарной операции.

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

PS: Еще раз спасибо за статью, хотя бы убедился, что не только я люблю оставлять задел "на будущее" :)

Уважаемый Андрей! Спасибо за Ваш отзыв!

Про возведение в степень. Эта операция делегируется функции pow(x, y), которая вычисляет x в степени y. Таким образом, получается просто обращение к функции.

Про параметры. Отличать в стеке параметры для функций от парамеров для других операций не нужно - в этом и заключается особенность ПОЛИЗ. Если в стеке не хватает операндов, необходимых для выполнения функции, то возникает ошибка "stack underflow", которая успешно обрабатывается.

Про унарные операции. Да, эта задача стоит того, чтобы ее порешать. Можно попробовать :-)

В целом же, вот эта фраза является особенно ценной: хотя бы убедился, что не только я люблю оставлять задел "на будущее" :) . Т.к., благодаря Вашему отзыву, мы убедились в том же.

Спасибо,

Уважаемый Андрей!

Здравствуйте,

Я не программист, но думаю, что без флагов (для унарного минуса) можно обойтись, используя мнимую единицу i.

В самом деле, -1 = i² , соответственно и унарный минус можно понимать, как i², а любое отрицательное число (-n) выразить как n * i² 

Раз i - операнд, тогда вот такой полиз: n i i ** . Или, допустим, зарегистрируем пользовательскую функцию my_^ (тем более, что её всё равно зарегистрируют, т.к., возводят в квадрат часто).

C пожеланиями,

Здравствуйте, Павел!

А зачем вообще избавляться от унарного минуса? Такой задачи нет. Наоборот, профессиональный калькулятор предполагает появление большого количества вспомогательных функций, которые упрощают расчёты хотя бы тем, что их не надо писать самому. Среди таких функций могут присутствовать:

• синус;
• косинус;
• квадратный корень;
• кубический корень;
• возведение в квадрат;
• возведение в куб;
• возведение x в степень y;
• и т.д.

Унарный минус - тут просто одна из функций.

К тому же, он существует в любой нотации (не только в ПОЛИЗ). Просто в инфиксной нотации он обозначается одним и тем же знаком "-", а распознаётся - по расположению в выражении.

С уважением,

Здравствуйте,

я написал не как избавиться, а как его реализовать без костылей. Как полизом, так и пользовательской функцией. Причём не отдельной, а ресурсной.

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

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

С пожеланиями,

 

P.S. Кстати, строго говоря, число i правильно переводить не как "мнимая единица", а как "воображаемая единица" (imaginary unit или imaginäre einheit по-немецки), как назвал Эйлер, который её и ввёл  в обиход. Откуда, собственно, и буква i. Почему-то русские перевели как "мнимая" и это слово закрепилось.

Между тем, конечно, понятие "воображаемая единица", которую мы должны сочинить, чтобы снять противоречие (например, как это было, когда потребовалось решить уравнение x²+1=0 ) несёт в себе эвристический метод, в то время, как фраза "мнимая единица" эту эвристику "замыливает".

Здравствуйте!

Огромное Вам Спасибо за интересную и важную для меня статью! У меня буквально на днях возникла потребность в простейшем интерпретаторе INI-файлов. Вроде такого:

[Fn keys layout]

Fn_x_step = 32
F1_pos_x = 8
F2_pos_x = F1_pos_x + Fn_x_step
F3_pos_x = F2_pos_x + Fn_x_step
... и так далее

Конечно, книги "Теоретические основы проектирования компиляторов" (Ф.Льюис, Д.Розенкранц, Р.Стирнс) или "Генератор компиляторов" (У.Маккиман, Д.Хорнинг, Д.Уортман) дают достаточно исчерпывающие основы. Однако, моя задача настолько проста и прозаична, что городить что-то серьезное просто не хочется :-) А Ваша прекрасная статья позволяет решить мою задачу легко и непринужденно (именно это я в своей многолетней программистской практике ценю больше всего).

Спасибр Вам!

P.S. Добавить в Ваш пример работу с переменными - простая и интересная задача.

Уважаемый Юргис!

P.S. Добавить в Ваш пример работу с переменными - простая и интересная задача. 

Конечно, присылайте пример. Или напишите здесь, или пришлите на мой e-mail (выше).

Скоро появится ещё 1 развёрнутый материал, посвящённый свёртыванию (идеализации) программного кода и структур данных.

Следите за обновлениями.

Большое Спасибо за Ваше мнение!
 

Спасибо за ответ!

Я сейчас как раз обдумываю, как расширить Ваш алгоритм для полного решения моей задачи. К сожалению, я узнал про ТРИЗ только что, из этой Вашей замечательной статьи :-)

Честно говоря, пока мысли немножко "разбегаются". Как я писал, мне нужно решить задачу выполнения кучи присваиваний переменным значений, формируемых (пока) арифметическими выражениями. Конечно, какие-нибудь Lua или Lex/Yacc позволяют решить мою задачу, но мне интересно самому разобраться.

Моя задача, по-сравнению с простым калькулятором, расширяется так:

1. Добавление в калькулятор операции присваивания
2. Добавление возможности работы с переменными
3. Добавление унарного знака операнда (как было предложено, две операции "nochange" и "neg")

После некоторых размышлений мне представляется, что часть действий логичнее было бы возложить на лексический блок, который предварительно просматривал бы исходный файл и генерировал поток лексем для описанного калькулятора. Он мог бы выполнять следующие задачи:

1. Убирать из входного потока все лишнее (коментарии, пустые строки, унарный "+", т.е. "nochange" и т.п.)
2. Создавать таблицу идентификаторов переменных
3. Распознавать числовые значения (возможно выполнять простейшие присваивания, типа WindowSize = 512)

Кроме того, хотелось бы включить возможность использования переменной до присваивания ей числового значения. Это вызывает потребность в многопроходной трансляции. (Что для меня совсем не страшно, т.к. исходные файлы в принципе небольшие.)

Думаю, что для улучшения понимания процесса полезно было бы написать формальную грамматику такого "языка". В общем, есть над чем подумать :-)

Большое спасибо за помощь!

С уважением, Юргис.

Уважаемые Коллеги!

Ранее обещанный материал о приложении ТРИЗ к программированию:

"Идеализация структуры данных" доступен по ссылке.

Обсуждение - здесь.

Спасибо,