PICSim.js - калькулятор и обратная польская запись

Обратная Польская Запись англ. (Reverse Polish Notation, RPN) позволяет избавиться от скобок в арифметических выражениях. Сначала следуют два операнда арифметической операции, а затем знак операции. Например 4 2 + = 4 + 2 = 6 или 4 2 * 3 5 / - = (4 * 2) - (3 / 5) = 7.4. Программа-транслятор RPN-выражений основывается на стеке - каждый операнд посылается в стек, а если встречается оператор, то из стека извлекаются два последних операнда и выполняется операция, после чего результат посылается обратно в стек. Классическая реализация калькулятора на базе обратной польской записи подробно расписана в книге «Язык программирования Си» Брайана Кернигана и Денниса Ритчи (последний один из непосредственных авторов и разработчиков языка Си). В общем случае алгоритм решения подобных задач сводится к двум этапам:

лексической анализ - распознавание и выделение лексем из входной последовательности символов. В случае RPN калькулятора на выходе получаем числа и арифметические операции

синтаксический анализ - последовательность лексем преобразуется в структуру данных, которая хорошо подходит для дальнейшей обработки. В упрощённом случае для RPN калькулятора это стек

Ошибки при выполнении программы могут происходить на обоих этапах - за вводом недопустимых символов (например букв) должен следить лексической анализатор, а вот обработка деления на ноль или неправильное количество элементов в стеке это уже зона ответственности синтаксического анализа.

При выборе инструментария для генерации лексического / синтаксического анализатора стоит учитывать ограниченные возможности микроконтроллеров. Анализатор не должен зависеть от системы и сторонних библиотек, поэтому 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-калькулятора.

🏠 Интернет Всего 🚗

Other articles

PICSim.js - сопрограммы и простейшая многозадачность

PICSim.js - часы реального времени DS1307

PICSim.js - матричная клавиатура

PICSim.js - аналого-цифровой преобразователь

Other articles

links

social