Викиучебник

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

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Нет описания правки
м Замена <tt /> на <code />; избыточные <big /> и <font /> вокруг <source />; {{SUBPAGENAME}}; пробелы.
Строка 3:
==Что такое обратная польская нотация?==
 
Рассмотрим запись арифметических выражений, в которых сначала следуют два операнда арифметической
операции, а затем знак операции. Например:
 
Строка 10:
|'''Обычная нотация'''
|-
|2 3 +
|2 + 3
|-
|2 3 * 4 5 * +
|(2 * 3) + (4 * 5)
|-
|2 3 4 5 6 * + - /
|2 / (3 - (4 + (5 * 6)))
|}
 
Это нотация записи выражений называется [[w:Обратная польская нотация|обратной польской нотацией (записью)]] (Reverse Polish Notation, RPN).
В теории языков программирования эта нотация называется ''постфиксной нотацией''. Обычная нотация называется алгебраической или ''инфиксной нотацией''
(«ин» от англ. ''inside'', то есть между операндами). Есть также префиксная нотация, активно используемая в языке Си (сначала имя функции, а затем её аргументы), а также в языке [[:w:LISP|LISP]].
 
Заметьте, что скобки в обратной польской нотации не нужны. В частности, если во втором примере мы
опустим скобки, выражение по прежнему будет интерпретироваться однозначно.
 
Транслятор RPN-выражений основан на [[w:Стек|стэке]]. Каждое следующее число
помещается в стэк. Если встречается знак операции (обозначим его <ttcode>*</ttcode>), то два числа из стека извлекаются (<ttcode>a = pop()</ttcode>, <ttcode>b = pop()</ttcode>), для них вычисляется значение соответствующей бинарной арифметической операции, и результат помещается в стек (<ttcode>push(a * b)</ttcode>).
 
 
'''Задача:''' Напишите программу-калькулятор арифметических выражений записанных в обратной польской нотации.
 
Ниже приведена простая реализация такого калькулятора на языке Си.
Роль стека играет обычный массив (stack[1000]). Переменная <ttcode>sp</ttcode> (stack pointer) равна количеству элементов в стеке.
Число (<ttcode>sp - 1</ttcode>) равно индексу ячейки, являющейся вершиной стека.
 
<big><source lang="c">
#include <stdio.h>
int main()
Строка 79:
return 0;
}
</source></big>
 
===Пример работы программы===
Строка 92:
===Задания===
 
# Введите входные следующие входные данные <ttcode>1 2 3 * * * * = = = =</ttcode>. К чему это привело? Добавьте к приведенной программе «защиту от дурака».
# Введите входные данные состоящие из 10000 единиц и 9999 знаков +. Сможет ли программа отработать на этих входных данных?
 
Строка 98:
===Замечания===
# У данной программы есть целый ряд недостатков:
:* Программа не будет работать, если количество элементов в стеке превысит 1000
:* Программа не замечает некорректные входы и отрабатывает их с непредсказуемыми последстиями.
:* В программе явно не отображено, что присутствует структура данных «стек». Это затрудняет понимание логики работы этой программы и усложняет сторонним разработчикам доработку данной программы.
Строка 107:
Введем операции работы со стеком в программу. Это повысит читаемость кода и облегчит понимание заложенной в программу логики.
 
<big><source lang="c">
#include <stdio.h>
#include <malloc.h>
Строка 160:
return 0;
}
</source></big>
 
В данной программе в некоторой степени реализована «защита от дурака», а именно, если вводится выражение, в котором число операций превосходит число
помещенных в стек элементов (например <ttcode>1 2 + *</ttcode>), то программа не допустит уменьшения переменной <ttcode>sp</ttcode> до отрицательных значений, а выдаст предупреждение «Невозможно выполнить POP для пустого стека».</tt>.
 
=== Выделение стека в отдельную структуру ===
 
Кроме защиты от дурака-пользователя необходима еще защита от дурака-программиста, который возьмет ваш код, решит его использовать и дорабатывать.
Точнее, нужно просто соблюдать некоторые правила, которые не позволили бы программисту, который включил ваш код в свой проект получить ошибки,
связанные с пересечением имён, испольуемых им в своих файлах и вами, в файле <ttcode>stack.c</ttcode>.
 
В первую очередь, в принципе не рекомендуется объявлять глобальные переменные, особенно такие, которые не являются всеобщим достоянием, а относятся к внутренним делам отдельного модуля (например, нашей программы, для работы со стеком).
 
Кроме того, рекомендуется имена функций присутствующие в билиотеке снабжать префиксом.
Например, имена функций, связанных со стеком, логично снабдить префиксом <ttcode>stack</ttcode>.
 
В итоге получаем следующую, «более правильную» реализацию стека:
 
<big><source lang="c">
#include <malloc.h>
/* Структура с указателем на массив int и служебной информацией
Строка 229:
}
}
</source></big>
 
===Задания===
Строка 235:
# Реализуйте RPN-калькулятор, используя эту реализацию стека. Выделите вычисление RPN-выражения в отдельную функцию.
# Постройте систему тестов и проверьте, что ваш калькулятор успешно проходит все тесты и «защищён от дурака» (как дурака-пользователя программы, так и дурака-программиста, использующего ваш стек и калькулятор).
[[Категория:Язык Си в примерах|Калькулятор выражений в обратной польской нотации{{SUBPAGENAME}}]]
Источник — https://ru.wikibooks.org/wiki/Язык_Си_в_примерах/Калькулятор_выражений_в_обратной_польской_нотации