Polish Notation - Order of Operations

Order of Operations

Order of operations is defined within the structure of prefix notation and can be easily determined. One thing to keep in mind is that when executing an operation, the operation is applied to the first operand by the second operand. This is not an issue with operations that commute, but for non-commutative operations like division or subtraction, this fact is crucial to the analysis of a statement. For example, the following statement:

/ 10 5 = 2

is read as "divide 10 by 5". Thus the solution is 2, not 1/2 as would be the result of an incorrect analysis.

Prefix notation is especially popular with stack-based operations due to its innate ability to easily distinguish order of operations without the need for parentheses. To evaluate order of operations under prefix notation, one does not even need to memorize an operational hierarchy, as with infix notation. Instead, one looks directly to the notation to discover which operator to evaluate first. Reading an expression from left to right, one first looks for an operator and proceeds to look for two operands. If another operator is found before two operands are found, then the old operator is placed aside until this new operator is resolved. This process iterates until an operator is resolved, which must happen eventually, as there must be one more operand than there are operators in a complete statement. Once resolved, the operator and the two operands are replaced with a new operand. Because one operator and two operands are removed and one operand is added, there is a net loss of one operator and one operand, which still leaves an expression with N operators and N + 1 operands, thus allowing the iterative process to continue. This is the general theory behind using stacks in programming languages to evaluate a statement in prefix notation, although there are various algorithms that manipulate the process. Once analyzed, a statement in prefix notation becomes less intimidating to the human mind as it allows some separation from convention with added convenience. An example shows the ease with which a complex statement in prefix notation can be deciphered through order of operations:

− * / 15 − 7 + 1 1 3 + 2 + 1 1 = − * / 15 − 7 2 3 + 2 + 1 1 = − * / 15 5 3 + 2 + 1 1 = − * 3 3 + 2 + 1 1 = − 9 + 2 + 1 1 = − 9 + 2 2 = − 9 4 = 5

An equivalent in-fix is as follows: ((15 / (7 − (1 + 1))) * 3) − (2 + (1 + 1)) = 5

Here is an implementation (in pseudocode) of prefix evaluation using a stack. Note that under this implementation the input string is scanned from right to left. This differs from the algorithm described above in which the string is processed from left to right. Both algorithms compute the same value for all valid strings.

Scan the given prefix expression from right to left for each symbol { if operand then push onto stack if operator then { operand1=pop stack operand2=pop stack compute operand1 operator operand2 push result onto stack } } return top of stack as result