Поговорим об обратной польской записи математических выражений и напишем соответствующую программу-калькулятор с набором операций +, -, *, /. Для хранения данных будем использовать стек. Разработку будем вести на языке программирования C#.
Теоретические сведения
Обратная польская запись (еще ее называют бесскобочной) — это форма записи математических выражений, в которой знак операции стоит после своих операндов.
Приведем пример. Пусть имеется математическое выражение:
(3 — 6) * (2 + 1)
Тогда в обратной польской записи это выражение будет выглядеть следующим образом:
3 6 — 2 1 + *
Сначала нужно из 3 отнять 6, будет -3, затем к 2 прибавить 1, будет 3, и, наконец, -3 умножить на 3, будет -9. То есть:
3 6 — 2 1 + * = -9
Описание алгоритма
Каждый операнд (число) помещается в стек. Когда на вход поступает знак операции, из стека извлекается нужное количество операндов (для операций +, -, *, / требуется два операнда) и к ним применяется данная операция, затем результат заносится в стек. Конечный результат вычислений будет находиться в вершине стека.
Стек — это структура данных организованная по принципу LIFO (last in — first out, «последним пришел — первым вышел»). То есть данные, помещаемые в стек, оказываются в его вершине, таким образом стек как бы противоположен очереди.
Операция помещения данных в стек обозначается Push. Операция извлечения данных из стека — Pop.
Реализация алгоритма
Приведем реализацию описанного выше алгоритма на примере программы-калькулятора. Для разработки был использован язык программирования C#.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace RPN { class Program { static void Main(string[] args) { string arg; Stack<double> st = new Stack<double>(); while ((arg = Console.ReadLine()) != "exit") { double num; bool isNum = double.TryParse(arg, out num); if (isNum) st.Push(num); else { double op2; switch(arg) { case "+": st.Push(st.Pop() + st.Pop()); break; case "*": st.Push(st.Pop() * st.Pop()); break; case "-": op2 = st.Pop(); st.Push(st.Pop() - op2); break; case "/": op2 = st.Pop(); if (op2 != 0.0) st.Push(st.Pop() / op2); else Console.WriteLine("Ошибка. Деление на ноль"); break; case "calc": Console.WriteLine("Результат: " + st.Pop()); break; default: Console.WriteLine("Ошибка. Неизвестная команда"); break; } } } } } } |
Прокомментируем код программы.
arg — строка в которой будут хранится введенные данные, st — экземпляр класса Stack<double> (в стеке будут хранится вещественные числа типа double). Цикл while (строки 16-52) будет выполняться до тех пора, пока не будет введено слово exit, в его же условии производится считывание данных с консоли. Далее выполняется проверка введенных данных с помощью оператора double.TryParse(…): оператор вернет true, если было введено число и это число скопируется в переменную num (а затем число поместится в стек (строка 21)); если было введено не число, оператор вернет значение false, и затем введенные данные будут обработаны с помощью оператора switch. Вывод результата вычисления будет осуществлен при вводе команды calc.
Обратите внимание на порядок извлечения данных из стека при различный операциях: если при сложении и умножении порядок не важен, то при вычитании и делении он имеет значение.
Демонстрация работы программы приведена на скриншоте ниже.
Чтобы скачать исходник программы из этого урока, нажмите на кнопку:
Скачать исходник
Поделиться в соц. сетях:
Спасибо за статью. Понятное объяснение. Для полного понимания лучше сделать собственный класс Stack. Но это уже немного другая тема.
Спасибо. Получилось. Много где искал информации на эту тему, но у вас самое то.