Обратная Польская Запись англ. (Reverse Polish Notation, RPN) позволяет избавиться от скобок в арифметических выражениях. Сначала следуют два операнда арифметической операции, а затем знак операции. Например 4 2 + = 4 + 2 = 6 или 4 2 * 3 5 / - = (4 * 2) - (3 / 5) = 7.4. Программа-транслятор RPN-выражений основывается на стеке - каждый операнд посылается в стек, а если встречается оператор, то из стека извлекаются два последних операнда и выполняется
операция, после чего результат посылается обратно в стек. Классическая реализация калькулятора на базе обратной польской записи подробно расписана в книге «Язык программирования Си» Брайана Кернигана и Денниса Ритчи (последний один из непосредственных авторов и разработчиков языка Си). В общем случае алгоритм решения подобных задач сводится к двум этапам:
-
лексической анализ - распознавание и выделение лексем из входной последовательности символов. В случае RPN калькулятора на выходе получаем числа и арифметические операции
-
синтаксический анализ - последовательность лексем преобразуется в структуру данных, которая хорошо подходит для дальнейшей обработки. В упрощённом случае для RPN калькулятора это стек
Ошибки при выполнении программы могут происходить на обоих этапах - за вводом недопустимых символов (например букв) должен следить лексической анализатор, а вот обработка деления на ноль или неправильное количество элементов в стеке это уже зона ответственности синтаксического анализа.
исходники | hex | picsim.js
При выборе инструментария для генерации лексического / синтаксического анализатора стоит учитывать ограниченные возможности микроконтроллеров. Анализатор не должен зависеть от системы и сторонних библиотек, поэтому Flex/Bison отпадают сразу т.к. завязаны на POSIX, а у нас тут голое железо. Также компиляторы для PIC18 и ниже официально не поддерживают рекурсивные функции (да да). Вобщем особо не развернуться. Но всё же нашелся один очень достойный кандидат - re2c. Генератор лексических анализаторов re2c очень похож на Flex - правила задаются в виде регулярных выражений слева, код соответствующих обработчиков справа. Сгенерированный код похож на человеческий и без проблем собирается даже под bare metal. Функция lex_flt это облегчённая версия atof/strtod, достаточная для RPN калькулятора.
stack.c
#include <stdint.h>
#include <stdbool.h>
static struct {
float data[RPN_MAX_CHARS / 2];
uint8_t sp;
} _stack;
// 0 == SUCCESS
static bool stack_push(const float f) {
if (_stack.sp < sizeof _stack.data / sizeof *_stack.data) {
_stack.data[_stack.sp++] = f;
return false;
}
return true;
}
// 0 == SUCCESS
static bool stack_pop(float * const f) {
if (_stack.sp > 0) {
*f = _stack.data[--_stack.sp];
return false;
}
return true;
}
static void stack_clr() {
_stack.sp = 0;
}
rpn.re.c
#include <stdbool.h>
#include "stack.c"
// 0 == SUCCESS
static bool lex_flt(const char *s, const char * const e, float * const f) {
float x = 1;
bool neg = false;
*f = 0;
/*!re2c
re2c:yyfill:enable = 0;
re2c:define:YYCTYPE = char;
re2c:define:YYCURSOR = s;
"-" { neg = true; goto mant_int; }
"" { goto mant_int; }
*/
mant_int:
/*!re2c
"." { goto mant_frac; }
"" { goto end; }
[0-9] { *f = (*f * 10) + (s[-1] - '0'); goto mant_int; }
*/
mant_frac:
/*!re2c
"" { goto end; }
[0-9] { *f += (x /= 10) * (s[-1] - '0'); goto mant_frac; }
*/
end:
if (neg) {
*f *= -1;
}
return e != s;
}
// 0 == SUCCESS
static bool cc(const char c) {
float o1, o2;
if (!stack_pop(&o2) && !stack_pop(&o1)) {
switch (c) {
case '+': return stack_push(o1 + o2);
case '-': return stack_push(o1 - o2);
case '/': return o2 == 0 || stack_push(o1 / o2);
case '*': return stack_push(o1 * o2);
}
}
return true;
}
// 0 == SUCCESS
static bool lex(const char * cur) {
// YYMARKER is needed because rules overlap:
// it backups input position of the longest successful match
const char *YYMARKER;
for(;;) {
const char *tok = cur;
float f;
/*!re2c
re2c:yyfill:enable = 0;
re2c:define:YYCTYPE = char;
re2c:define:YYCURSOR = cur;
flt = "-" ? ([0-9]+ | [0-9]* "." [0-9]+);
mop = [-+*\/];
* { return true; }
"\x00" { return false; }
flt { if (lex_flt(tok, cur, &f) || stack_push(f)) return true; continue; }
" " flt { if (lex_flt(tok + 1, cur, &f) || stack_push(f)) return true; continue; }
mop { if (cc(*tok)) return true; continue; }
" " mop { if (cc(*(tok + 1))) return true; continue; }
*/
}
}
// 0 == SUCCESS
bool rpn(const char * cur, float * const f) {
stack_clr();
return lex(cur) || stack_pop(f);
}
Работа с символьным дисплеем и матричной клавиатурой описывались в предыдущем материале.
Для преобразования выражений из обычной (например 3 + 4 * (2 - 1)) инфиксной нотации в постфиксную (RPN) существует алгоритм «сортировочная станция», который так же как и RPN основан на стеке и легко может быть адаптирован под микроконтроллеры. Таким образом несложно разработать калькулятор для обычный людей.
Ещё раз ссылка на исходники RPN-калькулятора.
There are comments.