Обратна полска нотация

Една от основните причини за появата на езици за програмиране на високо ниво бяха изчислителните проблеми, които изискват големи количества рутинни изчисления. Следователно, изискванията за максимално сближаване на формата на записване на изчисления с естествения език на математиката бяха направени на езиците за програмиране. В тази връзка, една от първите области на системното програмиране се формира изучаването на методи на изрази. Тук са получени множество резултати, но най-широко разпространен е методът на превод, използващ обратната полска нотация, предложен от полския математик Й. Лукашевич.

Нека бъде даден прост аритметичен израз на формата:

Нека представим този израз под формата на дърво, в което възлите съответстват на операции, а на клонове - на операции. Ще започнем изграждането от корена, което е операцията, която се извършва последна. Лявият клон отговаря на левия операнд на операцията, а десният клон отговаря на десния. Дървото на израза (1) е показано на фиг. един.

Нека завършим обхода на дървото, под което имаме предвид образуването на низ от символи от символите на възли и клони на дървото. Ще преминем от най-левия клон надясно и ще пренапишем възела в изходния ред само след като разгледаме всички негови клонове. Резултатът от обхождането на дървото е:

---