Польская запись

Польский математик Ян Лукашевич обнаружил, что при использовании функциональной записи выражения, в которой операция предшествует своим операндам (а не записывается между ними), скобки становятся излишними.

Пример. Инфиксной форме записи A+B соответствует префиксная форма записи (ПОЛИЗ) +AB.

Префиксная форма (или польская запись) формально может быть определена следующим образом:

1. Всякая переменная или константа есть выражение.

2. Если Q₁ – знак унарной (одноместной) операции, а a - выражение, то Q₁a является выражением

3. Если Q₂ – знак бинарной (двухместной) операции, а a₁ и a₂ - выражения, то Q₁a₁ a₂ является выражением

4. Если Q_n – знак n-местной операции, а a₁, a₂, …, a_n являются выражениями, то Q_na₁ a₂…a_n - выражение

5. Других выражений не существует

В отличие от обычной алгебраической записи выражений префиксная форма однозначно определяет порядок выполнения операций. Например, выражение A+B+C+D можно интерпретировать по-разному, а префиксная запись выражения всегда однозначно определяет порядок выполнения операций.

Полноскобочная форма выражения	Префиксная форма выражения
((((A+B)+C)+D) ((A+B)+(C+D)) ((A+(B+C))+D) (A+((B+C)+D)) (A+(B+(C+D)))	+++ABCD ++AB+CD ++A+BCD +A++BCD +A+B+CD

Постфиксная форма (польская инверсная запись - ПОЛИЗ) определяется следующими правилами:

1. Всякая переменная или константа есть выражение.

2. Если Q₁ – знак унарной (одноместной) операции, а a - выражение, то aQ₁ является выражением

6. Если Q₂ – знак бинарной (двухместной) операции, а a₁ и a₂ - выражения, то a₁ a₂ Q₁является выражением

7. Если Q_n – знак n-местной операции, а a₁, a₂, …, a_n являются выражениями, то a₁ a₂…a_n Q_n - выражение

8. Других выражений не существует

Поскольку изображение операции «унарный минус» совпадает с изображением операции «бинарный минус», то унарный минус можно представлять двумя способами: либо записывать его как бинарный оператор, т.е. –В представлять в виде 0-В, либо для унарного минуса ввести новый символ операции, например, символ «!».

Пример. Выражение (A+B)*C можно представить в польской инверсной записи как АВ+С*

Дата добавления: 2014-01-03