Язык Си в примерах/Калькулятор выражений в обратной польской нотации

Материал из Викиучебника — открытых книг для открытого мира
Перейти к навигации Перейти к поиску

Язык Си в примерах


  1. Компиляция программ
  2. Простейшая программа «Hello World»
  3. Учимся складывать
  4. Максимум
  5. Таблица умножения
  6. ASCII-коды символов
  7. Верхний регистр
  8. Скобочки
  9. Факториал
  10. Степень числа
  11. Треугольник Паскаля
  12. Корень уравнения
  13. Система счисления
  14. Сортировка
  15. Библиотека complex
  16. Сортировка на основе qsort
  17. RPN-калькулятор
  18. RPN-калькулятор на Bison
  19. Простая грамматика
  20. Задача «Расчёт сопротивления схемы»
  21. Простая реализация конечного автомата
  22. Использование аргументов командной строки
  23. Чтение и печать без использования stdio
  24. Декодирование звукозаписи в формате ADX

Что такое обратная польская нотация?[править]

Рассмотрим запись арифметических выражений, в которых сначала следуют два операнда арифметической операции, а затем знак операции. Например:

Обратная польская нотация Обычная нотация
2 3 + 2 + 3
2 3 * 4 5 * + (2 * 3) + (4 * 5)
2 3 4 5 6 * + - / 2 / (3 - (4 + (5 * 6)))

Это нотация записи выражений называется обратной польской нотацией (записью) (Reverse Polish Notation, RPN). В теории языков программирования эта нотация называется постфиксной нотацией. Обычная нотация называется алгебраической или инфиксной нотацией («ин» от англ. inside, то есть между операндами). Есть также префиксная нотация, активно используемая в языке Си (сначала имя функции, а затем её аргументы), а также в языке LISP.

Заметьте, что скобки в обратной польской нотации не нужны. В частности, если во втором примере мы опустим скобки, выражение по-прежнему будет интерпретироваться однозначно.

Транслятор RPN-выражений основан на стэке. Каждое следующее число помещается в стэк. Если встречается знак операции (обозначим его *), то два числа из стека извлекаются (a = pop(), b = pop()), для них вычисляется значение соответствующей бинарной арифметической операции, и результат помещается в стек (push(a * b)).


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

Ниже приведена простая реализация такого калькулятора на языке Си. Роль стека играет обычный массив (stack[1000]). Переменная sp (stack pointer) равна количеству элементов в стеке. Число (sp - 1) равно индексу ячейки, являющейся вершиной стека.

 #include <stdio.h>
 int main()
 {
     int stack[1000];  
     // sp = индекс ячейки, куда будет push-иться очередное число
     int sp =0;      // (sp-1) = индекс ячейки, являющейся вершиной стека
     while ( !feof(stdin) ) {
         int c = getchar();
         int x;
         switch (c) {
             case  ' ':
             case '\n':
                 break;
             case '=':
                 printf("Result = %d\n", stack[sp - 1]);  sp--;
                 break;
             case '+':
                stack[sp-2] = stack[sp-2] + stack[sp-1];  sp--;
                break;
             case '-':
                stack[sp-2] = stack[sp-2] - stack[sp-1];  sp--;
                break;
             case '*':
                stack[sp-2] = stack[sp-1] * stack[sp-2];  sp--;
                break;
             case '/':
               stack[sp-2] = stack[sp-2] / stack[sp-1];   sp--;
                break;
             default:
                 ungetc (c, stdin); // вернуть символ обратно в поток
                 if (scanf("%d", &x) != 1) {
                     fprintf(stderr, "Can't read integer\n");
                     return -1;
                 } else {
                     stack[sp] = x;                       sp++;
                 }
         }
     }
     printf("Result = %d\n",stack[sp-1]);
     return 0;
 }

Пример работы программы[править]

> ./stack
1 2 3 4 + * + =
Result = 15
1 2 + 3 4 + * =
Result = 21


Задания[править]

  1. Введите входные следующие входные данные 1 2 3 * * * * = = = =. К чему это привело? Добавьте к приведенной программе «защиту от дурака».
  2. Введите входные данные состоящие из 10000 единиц и 9999 знаков +. Сможет ли программа отработать на этих входных данных?


Замечания[править]

  1. У данной программы есть целый ряд недостатков:
  • Программа не будет работать, если количество элементов в стеке превысит 1000
  • Программа не замечает некорректные входы и отрабатывает их с непредсказуемыми последстиями.
  • В программе явно не отображено, что присутствует структура данных «стек». Это затрудняет понимание логики работы этой программы и усложняет сторонним разработчикам доработку данной программы.


Реализация калькулятора с явным определением операций со стеком[править]

Введем операции работы со стеком в программу. Это повысит читаемость кода и облегчит понимание заложенной в программу логики.

 #include <stdio.h>
 #include <malloc.h>
 
 int sp = 0;
 int stack[1000];
 int pop(void) {
     if (sp > 0) {
          return stack[--sp];
     } else { 
          fprintf(stderr, "Невозможно выполнить POP для пустого стека.\n");
          return 0;
     }
 };
 void push(int a) {
     stack[sp++] = a;
 };
 int empty() {
     return (sp == 0);
 }
 
 int main() {
     int i;
     while (!feof(stdin)) {
         int c = getchar();
         int x;
         switch (c) {
             case '\n':
             case ' ' : break;
             case '=' : printf("Result = %d\n", pop()); break;
             case 27  : goto RESULT;
             case '+' : push(pop() + pop()); break;
             case '-' : push(-pop() + pop()); break;
             case '*' : push(pop() * pop()); break;
             default:
                 ungetc(c, stdin);
                 if (scanf("%d", &x) != 1) {
                     fprintf(stderr, "Can't read integer\n");
                     return -1;
                 } else {
                     push(x);
                 }
                 break;
          }
    }
 RESULT:
     i = 0;
     while ( !empty() ){
         printf("Stack[%d] = %d\n", i,  pop());
         i++;
     }
     return 0;
 }

В данной программе в некоторой степени реализована «защита от дурака», а именно, если вводится выражение, в котором число операций превосходит число помещенных в стек элементов (например 1 2 + *), то программа не допустит уменьшения переменной sp до отрицательных значений, а выдаст предупреждение «Невозможно выполнить POP для пустого стека»..

Выделение стека в отдельную структуру[править]

Кроме защиты от дурака-пользователя, необходима еще защита от дурака-программиста, который возьмет ваш код, решит его использовать и дорабатывать. Точнее, нужно просто соблюдать некоторые правила, которые не позволили бы программисту, который включил ваш код в свой проект, получить ошибки, связанные с пересечением имён, испольуемых им в своих файлах и вами, в файле stack.c.

В первую очередь, в принципе не рекомендуется объявлять глобальные переменные, особенно такие, которые не являются всеобщим достоянием, а относятся к внутренним делам отдельного модуля (например, нашей программы, для работы со стеком).

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

В итоге получаем следующую, «более правильную» реализацию стека:

    #include <malloc.h>
    /* Структура с указателем на массив int и служебной информацией
     */
    typedef struct stack {
        int *data;
        int last;
        int data_size;
    } stack_t;
    /* Конструктор стека.
     * Принимает начальный размер стека и возвращает указатель на новый стек
     */
    stack_t* stack_new(int initial_size) {
        stack_t *stack = (stack_t*) malloc(sizeof(stack_t));
        stack->data_size = initial_size;
        if(stack->data_size <= 0) stack->data_size = 100;
        stack->last = 0;
        stack->data = (int*) malloc(sizeof(int)* stack->data_size);
        return stack;
    }
    /* Деструктор стека.
     * Принимает на вход указатель на стек и освобождает занятую им память.
     */
    void stack_delete(stack_t *stack) {
        free(stack->data);
        free(stack);
    }
    /* Операция push
     * Принимает указатель на стек и добавляемый элемент.
     * При необходимости увеличивает количество памяти для  массива элементов.
     */
    void stack_push(stack_t *stack, int a) {
        if (stack->last == stack->data_size) {
            stack->data_size = (stack->data_size * 3 + 1) / 2;
            stack->data = (int*)realloc(stack->data,  stack->data_size * sizeof(int));
        }
        stack->data[stack->last++] = a;
    }
    /* Операция pop
     * Принимает указатель на стек и адрес значения верхнего элемента.
     * Возвращает 1 в случае, если стек был непуст, и 0 -- в противном случае.
     */
    int stack_pop(stack_t *stack, int *a) {
        if (stack->last > 0) {
            *a = stack->data[--stack->last];
            return 1;
        } else {
            fprintf(stderr, "Попытка извлечь элемент из пустого стека!\n");
            return 0;
        }
    }

Задания[править]

  1. Реализуйте RPN-калькулятор, используя эту реализацию стека. Выделите вычисление RPN-выражения в отдельную функцию.
  2. Постройте систему тестов и проверьте, что ваш калькулятор успешно проходит все тесты и «защищён от дурака» (как дурака-пользователя программы, так и дурака-программиста, использующего ваш стек и калькулятор).