Язык Си в примерах/Калькулятор выражений в обратной польской нотации: различия между версиями
Greck (обсуждение | вклад) Нет описания правки |
Поставил теги <source> |
||
Строка 37: | Строка 37: | ||
Число (<tt>sp - 1</tt>) равно индексу ячейки, являющейся вершиной стека. |
Число (<tt>sp - 1</tt>) равно индексу ячейки, являющейся вершиной стека. |
||
<source lang="c"> |
|||
#include <stdio.h> |
#include <stdio.h> |
||
int main() |
int main() |
||
Строка 78: | Строка 79: | ||
return 0; |
return 0; |
||
} |
} |
||
</source> |
|||
===Пример работы программы=== |
===Пример работы программы=== |
||
Строка 105: | Строка 107: | ||
Введем операции работы со стеком в программу. Это повысит читаемость кода и облегчит понимание заложенной в программу логики. |
Введем операции работы со стеком в программу. Это повысит читаемость кода и облегчит понимание заложенной в программу логики. |
||
<source lang="c"> |
|||
#include <stdio.h> |
#include <stdio.h> |
||
#include <malloc.h> |
#include <malloc.h> |
||
Строка 157: | Строка 160: | ||
return 0; |
return 0; |
||
} |
} |
||
</source> |
|||
В данной программе в некоторой степени реализована «защита от дурака», а именно, если вводится выражение, в котором число операций превосходит число |
В данной программе в некоторой степени реализована «защита от дурака», а именно, если вводится выражение, в котором число операций превосходит число |
||
Строка 176: | Строка 179: | ||
В итоге получаем следующующую, «более правильную» реализацию стека: |
В итоге получаем следующующую, «более правильную» реализацию стека: |
||
<source lang="c"> |
|||
#include <malloc.h> |
#include <malloc.h> |
||
/* Структура с указателем на массив int и служебной ифнормацией |
/* Структура с указателем на массив int и служебной ифнормацией |
||
Строка 227: | Строка 230: | ||
} |
} |
||
} |
} |
||
</source> |
|||
===Задания=== |
===Задания=== |
Версия от 16:19, 5 июня 2007
- Компиляция программ
- Простейшая программа «Hello World»
- Учимся складывать
- Максимум
- Таблица умножения
- ASCII-коды символов
- Верхний регистр
- Скобочки
- Факториал
- Степень числа
- Треугольник Паскаля
- Корень уравнения
- Система счисления
- Сортировка
- Библиотека complex
- Сортировка на основе qsort
- RPN-калькулятор
- RPN-калькулятор на Bison
- Простая грамматика
- Задача «Расчёт сопротивления схемы»
- Простая реализация конечного автомата
- Использование аргументов командной строки
- Чтение и печать без использования stdio
- Декодирование звукозаписи в формате ADX
- Другие примеры
Что такое обратная польская нотация?
Рассмотрим запись арифметческих выражений, в которых сначала следуют два операнда арифметической операции, а затем знак операции. Например:
Обратная польская нотация | Обычная нотация |
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, то есть между операндами). Есть также префиксная нотация, активно используемая в языке Си (сначала имя функции, а затем её аргументы), а также в языке 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.
В первую очередь, в принципе не рекомендуется объявлять глобальные переменные, особенно такие, которые не являются всеобщим достоянием, а относятся к внутренним делам отдельного модуля (например, нашей программы, для работы со стеком).
Кроме того, рекомендуется имена функций присутствующие в билиотеке снабжать префиксом. Например, имена функций, связанных со стеком, логично снабдить префиксом stack.
В итоге получаем следующующую, «более правильную» реализацию стека:
#include <malloc.h>
/* Структура с указателем на массив int и служебной ифнормацией
*/
typedef struct stack {
int *data;
int last = 0;
int data_size;
} stack_t;
/* Конструктор стека.
* Принимает начальный размер стека и возвращает указатель на новый стек
*/
stack_t* stack_new(int initial_size) {
stack_t *stack = (stack_t*) malloc (sizeof(stack_t));
stack->data_size = initial_size;
if(stack->data_size <= 0) stack->data_size = 100;
stack->last = 0;
stack->data = (int*) malloc(sizeof(int)* stack->data_size);
return stack;
}
/* Деструктор стека.
* Принимает на вход указатель на стек и освобождает занятую им память.
*/
void stack_delete(stack_t *stack) {
free(stack->data)
free(stack);
}
/* Операция push
* Принимает указатель на стек и добавляемый элемент.
* При необходимости увеличивает количество памяти для массива элементов.
*/
void stack_push(stack_t *stack, int a) {
if(stack->last == stack->data_size) {
stack->data_size = (stack->data_size * 3 + 1) / 2;
stack->data = (int*)realloc(stack->data, stack->data_size * sizeof(int));
}
stack->data[stack->last++] = a;
}
/* Операция pop
* Принимает указатель на стек и адрес значения верхнего элемента.
* Возвращает 1 в случае, если стек был непуст, и 0 -- в противном случае.
*/
int stack_pop(stack_t *stack, int *a) {
if(stack->last > 0) {
*a = data[--stack->last];
return 1;
} else {
fprintf(stderr, "Попытка извлечь элемент из пустого стека!\n");
return 0;
}
}
Задания
- Реализуйте RPN-калькулятор, используя эту реализацию стека.
- Постройте систему тестов и проверьте, что Ваш калькулятр успешно проходит все тесты и «защищён от дурака».