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

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

---

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
25. Другие примеры

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

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

Обратная польская нотация	Обычная нотация
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, то есть между операндами). Есть также префиксная нотация, активно используемая в языке Си (сначала имя функции, а затем её аргументы), а также в языке w: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-1] / stack[sp-2];   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 * * * * = = = =. К чему это привело? Добавьте к приведенной программе

"защиту от дурака".

1. Введите входные данные состоящие из 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", s.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 {
                    s.push(x);
                }
                break;
         }
   }
RESULT:
    i = 0;
    while(! empty() ){
        printf("Stack[%d] = %d\n", i,  s.pop());
        i++;
    }
    return 0;
}

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

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

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

TODO