← All posts tagged стек

fescoff
математика стек Все мы давно привыкли к инфиксной ("между") форме записи выражений, т.е. записываем два операнда и оператор между ними. Например a + b. При записи более сложных выражений приходится вводить скобки и приоритет операций. Существует еще постфиксная ("после") форма записи, называемая обратной польской записью. В ней нет скобок и приоритета операций, что снимает лишние сложности при вычислении выражения. В ней сперва записываются два операнда, а потом оператор. Например если в инфиксной форме записи выражение имеет вид (1+2)·3, то в постфиксной оно будет иметь вид 1 2 + 3 · . Для расшифровки постфиксной записи необходимо двигаться слева направо и последовательно брать по два операнда и выполнять тот оператор, который непосредственно правее последнего операнда. Еще в постфиксной записи есть одна тонкость, одно и тоже выражение можно записать по разному, т.е. 1 2 + 3 · = 3 1 2 + · . Т.е. выборка двух операндов ведется по последним двум. На первый взгляд такая форма записи кажется непривычной, то она очень удобна (нет скобок и приоритетов операций). Префиксные и постфиксные унарные операции в ней выполняются также, как и в инфиксной форме. Только для них есть "своеобразный" приоритет выполнения. Постфиксная форма записи выражений является линейной, в отличии от инфиксной.
Выражения в форме обратной польской записи на компьютере вычисляются по алгоритму стековой машины. Инфиксную форму записи можно перевести в постфиксную с помощи алгоритма "сортировочной станции".