Editing Polish notation (section)

==Evaluation algorithm==
Prefix/postfix notation is especially popular for its innate ability to express the intended order of operations without the need for parentheses and other precedence rules, as are usually employed with [[infix notation]]. Instead, the notation uniquely indicates which operator to evaluate first. The operators are assumed to have a fixed [[arity]] each, and all necessary operands are assumed to be explicitly given. A valid prefix expression always starts with an operator and ends with an operand. Evaluation can either proceed from left to right, or in the opposite direction. Starting at the left, the input string, consisting of tokens denoting operators or operands, is pushed token for token on a [[Stack (abstract data type)|stack]], until the top entries of the stack contain the number of operands that fits to the top most operator (immediately beneath). This group of tokens at the stacktop (the last stacked operator and the according number of operands) is replaced by the result of executing the operator on these/this operand(s). Then the processing of the input continues in this manner. The rightmost operand in a valid prefix expression thus empties the stack, except for the result of evaluating the whole expression. When starting at the right, the pushing of tokens is performed similarly, just the evaluation is triggered by an operator, finding the appropriate number of operands that fits its arity already at the stacktop. Now the leftmost token of a valid prefix expression must be an operator, fitting to the number of operands in the stack, which again yields the result. As can be seen from the description, a [[Deterministic pushdown automaton|push-down store]] with no capability of arbitrary stack inspection suffices to implement this [[parsing]].

The above sketched stack manipulation works—with mirrored input—also for expressions in [[reverse Polish notation]].