Здравствуйте друзья! Хочу вам рассказать об использовании алгоритма Обратной польской записи для создания калькулятора на языке C#. О самом алгоритме рассказывать не буду, так как такая тема уже поднималась. Заострю внимание на конкретной программе.
Наша программа будет состоять из двух частей: 1) Класс RPN (Reverse Polish Notation) — тут будет реализована работа алгоритма 2) Класс Program — тут, собственно, будет реализовано использование класса RPN — писать будем в консоли, что бы было понятнее.
Часть первая: класс RPN
Класс будет содержать ряд методов:
Это 3 основных метода класса, опишем их подробнее: Calculate — метод общедоступный, ему будет передаваться выражение в виде строки, и он будет возвращать результат вычисления. Результат он будет получать используя другие методы. GetExpression — метод, которому основной метод Calculate будет передавать выражение, и получать его уже в постфиксной записи. Counting — метод, который получая постфиксную запись выражения будет вычислять его результат.
Так же, помимо 3 основных методов, в классе будет еще 3 метода «обеспечения», это: IsDelimeter — возвращает true, если проверяемый символ — разделитель IsOperator — возвращает true, если проверяемый символ — оператор GetPriority — метод возвращает приоритет проверяемого оператора, нужно для сортировки операторов
Сначала рассмотрим неосновные методы, они простые, так что проблем с пониманием быть не должно:
А теперь основные методы: Calculate:
Часть 2: класс Program
Тут все просто, думаю объяснять большого смысла нет, просто прокомментирую:
Внимание! Ошибки! Хочу обратить ваше внимание на одну вещь! В нашем классе я не реализовывал проверку входных данных, поэтому при некорректном вводе будут вылетать исключения!
Что такое RPN или обратная польская запись? Преимущества. История.
Существуют три основных способа ввода данных на калькуляторе
Алгебраический (или инфиксная запись)
Это наиболее удобный способ для написания математических выражений. Вводятся числа, затем функция: 1 + 2 =
Польская запись (или префиксная запись)
Данный способ был изобретен польским логиком Яном Лукасевичем в 1920 годах. Смысл записи заключался в пропуске скобок в логических выражениях. Это наименее распространенный способ из трех перечисленных. Здесь сначала вводится функция, затем число: + 1 ввод 2 ввод
Обратная польская запись или (постфиксная запись)
Обратная польская запись (постфиксная) очень напоминает простую польскую запись, только здесь функция вводится в последнюю очередь. Первым предложил такой способ ввода данных австралийский философ Чарльз Л. Хамблин в 1950х годах. Запись представляет собой тот самый способ, которым люди чаще всего пользуются в вычислении выражений в уме или на бумаге: 1 ввод 2 ввод +
Разберем пример
Алгебраический метод
Сложить 3+5=8. Записать ответ или сохранить результат в памяти. Сложить 7+6=13. Теперь ввести 8 (из первого сложения) и поделить его на результат второго вычисления: x=0.62.
13 нажатий на кнопки, не говоря уже о том, что нужно где-то записать ответ первого вычисления или сохранить его в памяти, чтобы начать вычислять вторую сумму.
Нажать 3, затем кнопку ENTER. Нажать 5, затем кнопку +. Нажать 7, затем кнопку ENTER. Нажать 6, затем знак сложения +. Заметьте, что отображается ответ второго сложения. А теперь немного волшебства. Нажмите кнопку деления, и калькулятор выдает ответ 0.62.
9 нажатий, при этом не нужно ничего записывать и запоминать.
Компания HP и RPN
В 1968 компания HP представила первый настольный калькулятор модели HP 9100A, в котором использовалась RPN. Руководство Hewlett-Packard посчитало, что RPN является наиболее удобным способом введения данных как для пользователя, так и для процессора. С тех пор поклонников RPN стало намного больше.
Всего немного времени на привыкание, и RPN покажется вам самым логичным и простым способом вычисления, который позволяет вводить меньше символов и скобок, что очень важно, например, при работе со сложными выражениями. Между прочим, большинство победителей соревнований по вычислениям на калькуляторе используют именно модели HP, потому что RPN позволяет экономить время.
Reverse Polish Notation (RPN) of a given expression
A distinctive feature of the reverse Polish notation is that the arguments come first, and then the operation itself for these arguments.
Unlike direct Polish notation, where the operands go first and then the values / arguments.
for example in reverse Polish notation will look like
Why is this one called Polish? The fact is that the reverse Polish notation was invented on the basis of the usual Polish notation, which was proposed in 1920 by the Polish mathematician Jan Lukasevic.
This bot automatically converts an arbitrary expression into reverse Polish notation.
You can use this bot, both for studying or writing articles and essays, and using the ability to receive an answer in RPN format via JSON request to your services or sites.
What else to tell about him. Some readers questioned the correctness of the provision in the reverse Polish entry by providing an example.
I would like to object to this, since it is impossible to represent a negative number in reverse Polish notation in principle, therefore such a trick is used. The correctness of this method is confirmed by the correctness of the calculation of all other calculators on this site, including the Universal complex numbers calculator online
Syntax
infixa expression
An expression can be any (!!) mathematical expression. The language in which the expression is written is not important here. You can write an expression in Ruby, PHP or Pascal.
An expression can use an unlimited number of functions.
Examples
after the conversion becomes
An expression recorded in RPN format looks like this 1 2 + 4 sin * 3 +
Самое главная польза этой нотации это то, что полученное выражение не имеет ни одной скобки. Это очень(!!) упрощает расчет произвольных математических выражений и формул с множеством вложенных скобок.
А отличительная особенность обратной польской нотации состоит в том, что сначала идут аргументы, а потом уже сама операция для этих аргументов.
В отличии от прямой польской записи, где сначала идут операнды а потом значения/аргументы.
Например в обратной польской нотации будет иметь вид
Этот бот, автоматически конвертирует произвольное выражение в обратную польскую нотацию.
Вы можете использовать этот бот, как для изучения или написания статей и рефератов, так и используя возможность получать ответ в формате RPN через JSON запрос на свои сервисы или сайты.
Что еще рассказать о нём. Некоторые читатели подвергли сомнению правильность предоставления в обратной польской записи, представив пример
На это хотелось бы возразить, тем что отрицательное число представить в обратной польской нотации невозможно в принципе, поэтому в ход идет такая уловка. Правильность этого метода подтверждается правильностью вычисления всех остальных калькуляторов на этом сайте в том числе и Универсальный калькулятор комплексных чисел онлайн
Синтаксис
infixa выражение
Выражение может быть любое(!!) математическое выражение. Здесь не важен язык, на котором пишется выражение. Вы можете написать выражение на Ruby, PHP или Паскале.
В выражении может использоваться неограниченное количество функций.
Примеры
после преобразования становится
Выражение записанное в формате RPN выглядит так 1 2 + 4 sin * 3 +
Язык Си в примерах/Калькулятор выражений в обратной польской нотации
Содержание
Что такое обратная польская нотация? [ править ]
Рассмотрим запись арифметических выражений, в которых сначала следуют два операнда арифметической операции, а затем знак операции. Например:
Это нотация записи выражений называется обратной польской нотацией (записью) (Reverse Polish Notation, RPN). В теории языков программирования эта нотация называется постфиксной нотацией. Обычная нотация называется алгебраической или инфиксной нотацией («ин» от англ. inside, то есть между операндами). Есть также префиксная нотация, активно используемая в языке Си (сначала имя функции, а затем её аргументы), а также в языке LISP.
Заметьте, что скобки в обратной польской нотации не нужны. В частности, если во втором примере мы опустим скобки, выражение по-прежнему будет интерпретироваться однозначно.
Задача: Напишите программу-калькулятор арифметических выражений записанных в обратной польской нотации.
Пример работы программы [ править ]
Задания [ править ]
Замечания [ править ]
Реализация калькулятора с явным определением операций со стеком [ править ]
Введем операции работы со стеком в программу. Это повысит читаемость кода и облегчит понимание заложенной в программу логики.
В данной программе в некоторой степени реализована «защита от дурака», а именно, если вводится выражение, в котором число операций превосходит число помещенных в стек элементов (например 1 2 + * ), то программа не допустит уменьшения переменной sp до отрицательных значений, а выдаст предупреждение «Невозможно выполнить POP для пустого стека»..
Выделение стека в отдельную структуру [ править ]
В первую очередь, в принципе не рекомендуется объявлять глобальные переменные, особенно такие, которые не являются всеобщим достоянием, а относятся к внутренним делам отдельного модуля (например, нашей программы, для работы со стеком).
В итоге получаем следующую, «более правильную» реализацию стека:
