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

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
Нет описания правки
мНет описания правки
Строка 1: Строка 1:

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


Это нотация записи выражений называется [[w:Обратная польская нотация|обратной польской записью]] (Reverse Polish Notation, RPN).
Заметьте, что скобки в обратной польской нотации не нужны. В частности,
В теории языков программирования эта нотация называется ''постфиксной нотацией'. Обычная нотация называется алгебраической или ''инфиксной нотацией''.
если во втором примере мы опустим скобки,
Есть также префиксная нотация, активно используемая в языке Си (сначала имя функции, а затем её аргументы), а также в языке [[:w:LISP]]

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


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


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


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

Версия от 14:07, 29 марта 2006

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

Обратная польская нотация Обычная нотация
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). В теории языков программирования эта нотация называется постфиксной нотацией'. Обычная нотация называется алгебраической или инфиксной нотацией. Есть также префиксная нотация, активно используемая в языке Си (сначала имя функции, а затем её аргументы), а также в языке 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.

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