Сегодня #zoda4a будет про обратную польскую запись, которая...

Сегодня #zoda4a будет про обратную польскую запись, которая всплыла у меня из подсознания в среду. Обратную польскую запись придумали, как явно следует из её названия, в Австралии, и она очень удобна для скармливания математических примеров компьютерам с малым объёмом памяти и медленно эту информацию читающим. Понятно, что сейчас она не очень актуальна, потому что даже телефоны на андроиде теперь в основном не тормозят, но, помимо прочего, данная система записи математических выражений позволяет избежать путаницы в их чтении и такой мерзости как скобки.

Вы вот никогда не думали, что знак математической операции, стоящий между двумя числами — это странно? ну то есть пока чисел всего два еще нормально. a + b: мы запоминаем а, потом читаем операцию, которую будем делать с а, потом читаем второго участника операции, выполняем операцию, стираем все из памяти и пишем туда результат операции, как-то так работает процесс, да? а если операций несколько? a+b+c читаем а, читаем, что следующий элемент надо прибавить, читаем элемент b, прибавляем, стираем все, пишем сумму а и b читаем следующий оператор, снова +, читаем c, складываем с с суммой а и b, забываем исходные числа, выдаем ответ. вроед тоже пока работает.

но стоит только добавить в выражение скобки или другие математические операции, которые обладают бОльшим, нежели сложение, приоритетом (а это, на минуточку, ВСЕ остальные операции, кроме вычитания) a+b*c то все, хрен, надо читать весь пример, весь хранить в памяти, расставлять приоритеты и согласно им выполнять действия. Понятно, что когда ввод одного символа в машину, что с клавиатуры, что с носителя занимал около секунды, а памяти зачастую хватало на тридцать два или чуть больше элемента, такой пример было совершенно не прочитать, не запомнить, а если бы и запомнить, анализ порядка действий занял бы у неё полдня или типа того. И вот тогда на помощь пришла обратная польская запись! не надо помнить больше трех элементов и одной операции, для выражений любой сложности! никаких скобок, никаких непонятных порядков действий! Знак операции в обратной польской нотации идет после тех элементов, с которыми эту операцию надо сделать.

a+b —--> ab+
a*b —--> ab*

после этого оба исходных элемента и операция забываются, а результат становится новым последним элементом и запись может быть продолжена:

a+b+c —--> ab+c+


если же выражение состоит из операций разного приоритета и (не дай бог) содержит скобки, то начинать скармливание выражение нужно непосредственно в том порядке, в котором действия должно быть выполняемы:

a+b*c —--> bc*a+ или abc*+
(a+b)*c —-> ab+c*
(a+b)/(c+d) —-> ab+cd+/
a+b/c+d —-> bc/a+d+ или abc/+d+ или abc/d++

то есть, операция выполняется между последним и предпоследним элементами в выражении, остальные лежат и ждут своего часа. Такая организация памяти — Last In First Out — называется стек, то есть стопка — то, что лежит сверху используется в первую очередь. если операция унарная (проводится только над одним элементом), то используется самый последний.

x^y — икс в степени y (^y - это одна операция, хоть для тех компьютеров это и не так)
sqrt(x) - корень квадратный (будем считать, это тоже одна операция, хотя и это неправда)

ещё пара примеров:

a*a-b*b=(a+b)(a-b) —--> aa*bb*-=ab+ab-*
(a+b)(a+b)=a*a+2*a*b+b*b----> ab+ab+*=aa*2a*b*+bb*+

всё просто, понятно, изящно.

можно и задание давать первые четыре переведите в польскую, пятую и шестую — обратно.

1) (a+b)*c+d
2) a/b+c/(a+b)
3) x+v*t+a*t*t/2
4) 1+1/(1+1/(1+1/(1+1/x)))
5) ab/ba/-
6) aaaaaaa1+/-/-/-

ответы мне в личку, доска почета в комментариях, гуд лак)

Ссылка по теме: ru.wikipedia.org/wiki/Обратная_польская_запись
Today # zoda4a will be about the reverse Polish entry, which came to me from the subconscious on Wednesday. The reverse Polish notation was invented, as is obvious from its name, in Australia, and it is very convenient for feeding mathematical examples to computers with a small memory size and slowly reading this information. It is clear that now it is not very relevant, because even the phones on the android now basically do not slow down, but, among other things, this system of writing mathematical expressions allows you to avoid confusion in their reading and such abominations as brackets.

You never thought that a sign of a mathematical operation between two numbers is strange? Well, that is, while the numbers just two are still normal. a + b: we memorize a, then we read the operation that we will do with a, then we read the second participant of the operation, perform the operation, erase everything from memory and write the result of the operation there, somehow the process works, right? and if there are several operations? a + b + c we read a, we read that the next element must be added, we read the element b, we add, we delete everything, we write the sum of a and b we read the next operator, again +, we read c, we add c to the sum of a and b, we forget the original numbers, give the answer. Vroed also works so far.

but one has only to add brackets or other mathematical operations that have more than addition, priority (and this, for a moment, ALL the other operations, except subtraction) a + b * c is all fucking, you need to read the whole example, all store, prioritize and execute actions according to them. It is clear that when inputting a single character into a car, that from the keyboard, that from the carrier took about a second, and the memory was often enough for thirty-two or a little more element, such an example was completely not read, did not remember, and if it were, remember, analysis the order of actions would take half a day or so. And then the reverse Polish post came to the rescue! there is no need to remember more than three elements and one operation, for expressions of any complexity! no brackets, no obscure steps! The sign of the operation in the reverse Polish notation comes after those elements with which this operation must be done.

a + b —--> ab +
a * b —--> ab *

after that, both the original elements and the operation are forgotten, and the result becomes the new last element and the recording can be continued:

a + b + c ——> ab + c +

 
if the expression consists of operations of different priority and (God forbid) contains brackets, then the expression should be fed directly in the order in which the actions should be performed:

a + b * c —--> bc * a + or abc * +
(a + b) * c —-> ab + c *
(a + b) / (c + d) —-> ab + cd + /
a + b / c + d —-> bc / a + d + or abc / + d + or abc / d ++

that is, the operation is performed between the last and last but one elements in the expression, the rest lie and wait in the wings. Such an organization of memory - Last In First Out - is called a stack, that is, a stack - what lies on top is used first. if the operation is unary (only one element is performed), then the last one is used.

x ^ y - x to the power of y (^ y is one operation, even though it is not so for those computers)
sqrt (x) - square root (we will assume that this is also a single operation, although this is not true)

a couple more examples:

a * a-b * b = (a + b) (a-b) ——> aa * bb * - = ab + ab- *
(a + b) (a + b) = a * a + 2 * a * b + b * b ----> ab + ab + * = aa * 2a * b * + bb * +

everything is simple, understandable, elegant.

it is possible and the task to give the first four translate into Polish, fifth and sixth - back.

1) (a + b) * c + d
2) a / b + c / (a ​​+ b)
3) x + v * t + a * t * t / 2
4) 1 + 1 / (1 + 1 / (1 + 1 / (1 + 1 / x)))
5) ab / ba / -
6) aaaaaaa1 + / - / - / -

my answers in lichku, honor roll in the comments, gud varnish)

Related link: ru.wikipedia.org/wiki/Reverse_pole_record
У записи 20 лайков,
4 репостов.
Эту запись оставил(а) на своей стене Андрей Городецкий

Понравилось следующим людям