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

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

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

Обратная польская нотация	Обычная нотация
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 2 3 * * * * = = = =. К чему это привело? Добавьте к приведенной программе «защиту от дурака».
Введите входные данные состоящие из 10000 единиц и 9999 знаков +. Сможет ли программа отработать на этих входных данных?

Замечания

У данной программы есть целый ряд недостатков:

Программа не будет работать, если количество элементов в стеке превысит 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;
        }
    }

Задания

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