Викиучебник

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

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
мНет описания правки
мНет описания правки
Строка 3:
==Что такое обратная польская нотация?==
 
Рассмотрим запись арифметческих выражений, в которых сначала следуют два операнда арифметической операции,
операции, а затем знак операции. Например:
 
{| border=1
Строка 22:
Это нотация записи выражений называется [[w:Обратная польская нотация|обратной польской нотацией (записью)]] (Reverse Polish Notation, RPN).
В теории языков программирования эта нотация называется ''постфиксной нотацией''. Обычная нотация называется алгебраической или ''инфиксной нотацией''
(«ин» от англ. ''inside'', то есть между операндами). Есть также префиксная нотация, активно используемая в языке Си (сначала имя функции, а затем её аргументы), а также в языке [[:w:LISP|LISP]].
 
Заметьте, что скобки в обратной польской нотации не нужны. В частности, если во втором примере мы опустим скобки,
опустим скобки, выражение по прежнему будет интерпретироваться однозначно.
 
Транслятор RPN-выражений основан на [[w:Стек|стэке]]. Каждое следующее число
помещается в стэк. Если встречается знак операции (обозначим его <tt>*</tt>), то два числа из стэкастека извлекаются (<tt>a = pop()</tt>, <tt>b = pop()</tt>), для них вычисляется значение соответствующей бинарной арифметической операции, и результат помещается в стек (<tt>push(a * b)</tt>).
(<tt>a = pop(), b = pop()</tt>), для них вычисляется значение соответствующей бинарной арифметической операции и результат помещается в стек (<tt>push(a * b)</tt>).
 
 
'''Задача:''' Напишите программу-калькулятор арифметических выражений записанных в обратной польской ноации.
 
Ниже приведена постая реализация такого калькулятора на языке Си.
Роль стэкастека играет обычный массив (stack[1000]). Переменная <tt>sp</tt> (stack pointer) равна количеству элементов в стеке.
Число (<tt>sp - 1</tt>-1) равно индексу ячейки, являющейся вершиной стека.
 
#include <stdio.h>
Строка 67 ⟶ 66 :
break;
default:
ungetc(c, stdin); // вернуть символ обратно в поток
if(scanf("%d", &x) != 1) {
fprintf(stderr, "Can't read integer\n");
Строка 92 ⟶ 91 :
 
# Введите входные следующие входные данные <tt>1 2 3 * * * * = = = =</tt>. К чему это привело? Добавьте к приведенной программе
"«защиту от дурака"».
# Введите входные данные состоящие из 10000 единиц и 9999 знаков +. Сможет ли программа отработать на этих входных данных?
 
 
===Замечания===
# У данной программы есть целый ряд недостатков:
:* Программа не будет работать, если количество элементов в стеке превысит 1000
:* Программа не замечает некорректные входы и отрабатывает их с непредсказуемыми последстиями.
:* В программе явно не отображено, что присутствует структура данных "«стек"». Это затрудняет понимание логики работы этой программы и усложняет сторонним разработчикам доработку данной программы.
 
 
Строка 161 ⟶ 160 :
 
 
В данной программе в некоторой степени реализована "«защита от дурака"», а именно, если вводится выражение, в котором число операций превосходит число
помещенных в стек элементов (например <tt>1 2 + *</tt>), то программа не допустить уменьшиния переменной <tt>sp</tt> до отрицательных значений, а выдаст предупреждение <tt>"«Невозможно выполнить POP для пустого стека».</tt>.
 
Кроме защиты от дурака-пользователя необходима еще защита от дурака-программиста, который возьмет ваш код, решит его использовать и дорабатывать.
Строка 170 ⟶ 169 :
В первую очередь, в принципе не рекомендуется объявлять глобальные переменные, особенно такие, которые не являются всеобщим достоянием, а относятся к внутренним делам отдельного модуля (например, нашей программы, для работы со стеком).
 
Кроме того, рекомендуется имена функций присутствующие в билиотеке снабжать префиксом.
TODO
Например, имена функций, связанных со стеком, логично снабдить префиксом <tt>stack</tt>.
 
В итоге получаем следующующую, «более правильную» реализацию стека:
 
#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);
}
 
/* Деструктор стека.
* Принимает на вход указатель на стек и освобождает занятую им память.
*/
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);
}
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-калькулятор, используя эту реализацию стека.
# Постройте систему тестов и проверьте, что Ваш калькулятр успешно проходит все тесты и «защищён от дурака».
Источник — https://ru.wikibooks.org/wiki/Язык_Си_в_примерах/Калькулятор_выражений_в_обратной_польской_нотации