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

Калькулятор выражений в обратной польской нотации

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

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

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

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

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

#include <stdio.h>
int main()
{
    int stack[1000];  //
    int sp = 0;       // индекс ячейки, куда будет push-иться очередное число
                      // (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.

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