# Difference between revisions of "Prefix/Infix/Postfix Notation"

Marc Brown (talk | contribs) (Created page with "The expression $5+\large{8\over{3-1}}$ clearly has a value of 9. It written in ''infix'' notation as $5+8/(3-1)$. The value of an ''infix'' version is well-defined because the...") |
Marc Brown (talk | contribs) |
||

Line 1: | Line 1: | ||

The expression $5+\large{8\over{3-1}}$ clearly has a value of 9. It written in ''infix'' notation as $5+8/(3-1)$. The value of an ''infix'' version is well-defined because there is a well-established order of precedence in mathematics: We first evaluate the parentheses (3-1=2); then, because division has higher precedence that subtraction, we next do 8/2=4. And finally, 5+4=9. The order of precedence is often given the mnemonic of '''Please excuse my dear Aunt Sue''', or '''PEMDAS''': '''p'''arentheses, '''e'''xponentiation, '''m'''ultiplication/'''d'''ivision, and '''a'''ddition/''''s'''ubtraction. Multiplication and division have the same level of precedence; addition and subtraction also have the same level of precedence. Terms with equals precedence are evaluated from left-to-right [https://en.wikipedia.org/wiki/Order_of_operations wikipedia]. | The expression $5+\large{8\over{3-1}}$ clearly has a value of 9. It written in ''infix'' notation as $5+8/(3-1)$. The value of an ''infix'' version is well-defined because there is a well-established order of precedence in mathematics: We first evaluate the parentheses (3-1=2); then, because division has higher precedence that subtraction, we next do 8/2=4. And finally, 5+4=9. The order of precedence is often given the mnemonic of '''Please excuse my dear Aunt Sue''', or '''PEMDAS''': '''p'''arentheses, '''e'''xponentiation, '''m'''ultiplication/'''d'''ivision, and '''a'''ddition/''''s'''ubtraction. Multiplication and division have the same level of precedence; addition and subtraction also have the same level of precedence. Terms with equals precedence are evaluated from left-to-right [https://en.wikipedia.org/wiki/Order_of_operations wikipedia]. | ||

The algorithm to evaluate an ''infix'' expression is complex, as it must address the order of precedence. Two alternative notations have been developed which lend themselves to simple computer algorithms for evaluating expressions. In ''prefix'' notation, each operator is placed before its operands5 . The expression above would be | The algorithm to evaluate an ''infix'' expression is complex, as it must address the order of precedence. Two alternative notations have been developed which lend themselves to simple computer algorithms for evaluating expressions. In ''prefix'' notation, each operator is placed before its operands5 . The expression above would be <syntaxhighlight lang="python" inline>5 8 3 1 - / +</syntaxhighlight>. In ''postfix'' notation, each operator is placed after its operand. The expression above is <syntaxhighlight lang="python" inline>+ 5 / 8 - 3 1</syntaxhighlight>. In ''prefix'' and ''postfix'' notations, there is no notion of order of precedence, nor are there any parentheses. The evaluation is the same regardless of the operators. | ||

An algorithm for converting from infix to prefix (postfix) is as follows: | An algorithm for converting from infix to prefix (postfix) is as follows: | ||

Line 9: | Line 9: | ||

* For each term, write down the operand before (after) the operators. | * For each term, write down the operand before (after) the operators. | ||

== Example == | |||

Infix to Prefix | The following sequence of steps illustrates converting $X=\left(AB-{C\over{D}}\right)^E$ from infix to prefix and postfix: | ||

(X = (((A * B) - (C / D)) ↑ E)) | ::{| class="wikitable" style="text-align: center" | ||

X A B C D E | |- | ||

X * A B C D E | !Infix to Prefix | ||

X * A B / C D E | !Infix to Postfix | ||

X - * A B / C D E | |||

X ↑ - *A B / C D E | |- | ||

= X ↑ - * A B / C D E | |(X = (((A * B) - (C / D)) ↑ E)) || (X = (((A * B) - (C / D)) ↑ E)) | ||

|- | |||

| style="text-align: left; padding-left: 2em" |X A B C D E || style="text-align: left; padding-left: 2em" | X A B C D E | |||

|- | |||

| style="text-align: left; padding-left: 2em" | X * A B C D E || style="text-align: left; padding-left: 2em" | X A B * C D E | |||

|- | |||

| style="text-align: left; padding-left: 2em" | X * A B / C D E || style="text-align: left; padding-left: 2em" | X A B * C D / E | |||

|- | |||

| style="text-align: left; padding-left: 2em" | X - * A B / C D E || style="text-align: left; padding-left: 2em" | X A B * C D / - E | |||

|- | |||

| style="text-align: left; padding-left: 2em" | X ↑ - *A B / C D E || style="text-align: left; padding-left: 2em" | X A B * C D / - E ↑ | |||

|- | |||

| style="text-align: left; padding-left: 2em" | = X ↑ - * A B / C D E || style="text-align: left; padding-left: 2em" | X A B * C D / - E ↑ = | |||

|} |

## Revision as of 20:07, 27 July 2018

The expression $5+\large{8\over{3-1}}$ clearly has a value of 9. It written in *infix* notation as $5+8/(3-1)$. The value of an *infix* version is well-defined because there is a well-established order of precedence in mathematics: We first evaluate the parentheses (3-1=2); then, because division has higher precedence that subtraction, we next do 8/2=4. And finally, 5+4=9. The order of precedence is often given the mnemonic of **Please excuse my dear Aunt Sue**, or **PEMDAS**: **p**arentheses, **e**xponentiation, **m**ultiplication/**d**ivision, and **a**ddition/'**s**ubtraction. Multiplication and division have the same level of precedence; addition and subtraction also have the same level of precedence. Terms with equals precedence are evaluated from left-to-right wikipedia.

The algorithm to evaluate an *infix* expression is complex, as it must address the order of precedence. Two alternative notations have been developed which lend themselves to simple computer algorithms for evaluating expressions. In *prefix* notation, each operator is placed before its operands5 . The expression above would be `5 8 3 1 - / +`

. In *postfix* notation, each operator is placed after its operand. The expression above is `+ 5 / 8 - 3 1`

. In *prefix* and *postfix* notations, there is no notion of order of precedence, nor are there any parentheses. The evaluation is the same regardless of the operators.

An algorithm for converting from infix to prefix (postfix) is as follows:

- Fully parenthesize the infix expression. It should now consist solely of “terms”: a binary operator sandwiched between two operands.
- Write down the operands in the same order that they appear in the infix expression.
- Look at each term in the infix expression in the order that one would evaluate them, i.e., inner-most parenthesis to outer-most and left to right among terms of the same depth.
- For each term, write down the operand before (after) the operators.

## Example

The following sequence of steps illustrates converting $X=\left(AB-{C\over{D}}\right)^E$ from infix to prefix and postfix:

Infix to Prefix Infix to Postfix (X = (((A * B) - (C / D)) ↑ E)) (X = (((A * B) - (C / D)) ↑ E)) X A B C D E X A B C D E X * A B C D E X A B * C D E X * A B / C D E X A B * C D / E X - * A B / C D E X A B * C D / - E X ↑ - *A B / C D E X A B * C D / - E ↑ = X ↑ - * A B / C D E X A B * C D / - E ↑ =