Язык Си в примерах/Калькулятор выражений в обратной польской нотации: различия между версиями
Greck (обсуждение | вклад) Нет описания правки |
Greck (обсуждение | вклад) мНет описания правки |
||
Строка 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) ). |
|||
'''Задача:''' Напишите программу-калькулятор арифметических выражений записанных в обратной польской ноации. |
|||
Ниже приведена постая реализация такого калькулятора на Си. |
|||
Роль стэка играет обычный массив (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 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", 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.
В первую очередь, не рекомендуется объявлять глобальные переменные, которые не являются всеобщим достоянием, а относятся к вашим личным внутренним делам.