Язык Си в примерах/Калькулятор выражений в обратной польской нотации: различия между версиями
Greck (обсуждение | вклад) мНет описания правки |
Greck (обсуждение | вклад) Нет описания правки |
||
Строка 31: | Строка 31: | ||
int main() |
int main() |
||
{ |
{ |
||
int stack[1000]; |
int stack[1000]; |
||
// sp = индекс ячейки, куда будет push-иться очередное число |
|||
int sp =0; // (sp-1) = индекс ячейки, являющейся вершиной стека |
|||
while(!feof(stdin)) { |
while(!feof(stdin)) { |
||
int c = getchar(); |
int c = getchar(); |
||
Строка 90: | Строка 90: | ||
:* Программа не будет работать, если количество элементов в стеке превысит 1000 |
:* Программа не будет работать, если количество элементов в стеке превысит 1000 |
||
:* Программа не замечает некорректные входы и отрабатывает их с непредсказуемыми последстиями. |
:* Программа не замечает некорректные входы и отрабатывает их с непредсказуемыми последстиями. |
||
:* В программе явно не отображено, что присутствует структура данных "стек" |
:* В программе явно не отображено, что присутствует структура данных "стек". Это затрудняет понимание логики работы этой программы и усложняет сторонним разработчикам доработку данной программы. |
||
Версия от 13:57, 29 марта 2006
Рассмотрим запись арифметческих выражений, в которых сначала следуют два операнда арифметической операции, а затем знак операции. Например:
Обратная польская нотация | Обычная нотация |
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]; // 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.
В первую очередь, не рекомендуется объявлять глобальные переменные, которые не являются всеобщим достоянием, а относятся к вашим личным внутренним делам.