Difference between revisions of "Prefix/Infix/Postfix Notation"
Marc Brown (talk | contribs) |
Marc Brown (talk | contribs) |
||
| Line 11: | Line 11: | ||
A quick check for determining whether a conversion is correct is to convert the result back into the original format. | A quick check for determining whether a conversion is correct is to convert the result back into the original format. | ||
One way to convert from prefix (postfix) to infix is to make repeated scans through the expression. Each scan, replace an operand with two adjacent operators, and replace | One way to convert from prefix (postfix) to infix is to make repeated scans through the expression. Each scan, replace an operand with two adjacent operators, and replace with a parenthesized infix expression. This is not the most efficient algorithm, but works well for a human. | ||
== Context | Problems in this category ask to convert between prefix, infix, and postfix, or to evaluate an expression in prefix or postfix. | ||
== Context == | |||
''Prefix'' and ''postfix'' notation is also known as ''Polish'' and ''Reverse Polish'' notation, respectively, for the Polish logician Jan Lukasiewicz. | ''Prefix'' and ''postfix'' notation is also known as ''Polish'' and ''Reverse Polish'' notation, respectively, for the Polish logician Jan Lukasiewicz. | ||
== | == Examples == | ||
The following sequence of steps illustrates converting $X=\left(AB-{C\over{D}}\right)^E$ from infix to prefix and postfix: | |||
::{| class="wikitable" style="text-align: center" | |||
|- | |||
!Infix to Prefix | |||
!Infix to Postfix | |||
|- | |||
|(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 ↑ = | |||
|} | |||
=== Examples Converting to Infix === | |||
::{| class="wikitable" style="text-align: left" | |||
|- | |||
!Prefix to Infix || | |||
Postfix to Infix | |||
|- | |||
! ↑ + * 3 4 / 8 2 – 7 5 || 3 4 * 8 2 / + 7 5 -↑ | |||
|- | |||
| style="background-color: #ffffff" | ↑ + <syntaxhighlight lang="python" inline>(3*4)</syntaxhighlight> / 8 2 – 7 5 | |||
| style="background-color: #ffffff" | <syntaxhighlight lang="python" inline>(3*4)</syntaxhighlight> 8 2 / + 7 5 - ↑ | |||
|- | |||
| style="background-color: #ffffff" |↑ + <syntaxhighlight lang="python" inline>(3*4)</syntaxhighlight> <syntaxhighlight lang="python" inline>(8/2)</syntaxhighlight> – 7 5 | |||
| style="background-color: #ffffff" | <syntaxhighlight lang="python" inline>(3*4)</syntaxhighlight> <syntaxhighlight lang="python" inline>(8/2)</syntaxhighlight> + 7 5 - ↑ | |||
|- | |||
| style="background-color: #ffffff" |↑ <syntaxhighlight lang="python" inline>(3*4)+(8/2)</syntaxhighlight> - 7 5 | |||
| style="background-color: #ffffff" | <syntaxhighlight lang="python" inline>((3*4)+(8/2))</syntaxhighlight> 7 5 -↑ | |||
|- | |||
| style="background-color: #ffffff" |↑ <syntaxhighlight lang="python" inline>((3*4)+(8/2))</syntaxhighlight> <syntaxhighlight lang="python" inline>(7-5)</syntaxhighlight> | |||
| style="background-color: #ffffff" | <syntaxhighlight lang="python" inline>((3*4)+(8/2))</syntaxhighlight> <syntaxhighlight lang="python" inline>(7-5)</syntaxhighlight> ↑ | |||
|- | |||
| style="background-color: #ffffff" |<syntaxhighlight lang="python" inline>(((3*4)+(8/2))↑(7-5))</syntaxhighlight> | |||
| style="background-color: #ffffff" |<syntaxhighlight lang="python" inline>(((3*4)+(8/2))↑(7-5))</syntaxhighlight> | |||
|- | |||
!$(3*4+{8\over{2}})^{(7-5)}$ | |||
!$(3*4+{8\over{2}})^{(7-5)}$ | |||
|} | |||
== Examples == | |||
The following sequence of steps illustrates converting $X=\left(AB-{C\over{D}}\right)^E$ from infix to prefix and postfix: | The following sequence of steps illustrates converting $X=\left(AB-{C\over{D}}\right)^E$ from infix to prefix and postfix: | ||
| Line 40: | Line 96: | ||
| 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 ↑ = | ||
|} | |} | ||
=== Examples Converting to Infix === | |||
== | |||
::{| class="wikitable" style="text-align: left" | |||
|- | |||
!Prefix to Infix || | |||
Postfix to Infix | |||
|- | |||
! ↑ + * 3 4 / 8 2 – 7 5 || 3 4 * 8 2 / + 7 5 -↑ | |||
|- | |||
| style="background-color: #ffffff" | ↑ + <syntaxhighlight lang="python" inline>(3*4)</syntaxhighlight> / 8 2 – 7 5 | |||
| style="background-color: #ffffff" | <syntaxhighlight lang="python" inline>(3*4)</syntaxhighlight> 8 2 / + 7 5 - ↑ | |||
|- | |||
| style="background-color: #ffffff" |↑ + <syntaxhighlight lang="python" inline>(3*4)</syntaxhighlight> <syntaxhighlight lang="python" inline>(8/2)</syntaxhighlight> – 7 5 | |||
| style="background-color: #ffffff" | <syntaxhighlight lang="python" inline>(3*4)</syntaxhighlight> <syntaxhighlight lang="python" inline>(8/2)</syntaxhighlight> + 7 5 - ↑ | |||
|- | |||
| style="background-color: #ffffff" |↑ <syntaxhighlight lang="python" inline>(3*4)+(8/2)</syntaxhighlight> - 7 5 | |||
| style="background-color: #ffffff" | <syntaxhighlight lang="python" inline>((3*4)+(8/2))</syntaxhighlight> 7 5 -↑ | |||
|- | |||
| style="background-color: #ffffff" |↑ <syntaxhighlight lang="python" inline>((3*4)+(8/2))</syntaxhighlight> <syntaxhighlight lang="python" inline>(7-5)</syntaxhighlight> | |||
| style="background-color: #ffffff" | <syntaxhighlight lang="python" inline>((3*4)+(8/2))</syntaxhighlight> <syntaxhighlight lang="python" inline>(7-5)</syntaxhighlight> ↑ | |||
|- | |||
| style="background-color: #ffffff" |<syntaxhighlight lang="python" inline>(((3*4)+(8/2))↑(7-5))</syntaxhighlight> | |||
| style="background-color: #ffffff" |<syntaxhighlight lang="python" inline>(((3*4)+(8/2))↑(7-5))</syntaxhighlight> | |||
|- | |||
!$(3*4+{8\over{2}})^{(7-5)}$ | |||
!$(3*4+{8\over{2}})^{(7-5)}$ | |||
|} | |||
== Online Resources == | |||
===ACSL Videos=== | |||
The following YouTube videos show ACSL students and advisors working out some previous problems. To access the YouTube page with the video, click on the title of the video in the icon. (You can also play the video directly by clicking on the arrow in the center of the image; however, you'll | |||
probably want to have a larger viewing of the video since it contains writing on a whiteboard.) Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads. | |||
{| | |||
|- | |||
| <youtube width="300" height="180">https://youtu.be/Lj91oRv3EIY</youtube> | |||
| [https://youtu.be/Lj91oRv3EIY ''ACSL Prep - Mrs. Gupta - Prefix Infix Postfix'' ('''MegaChristian5555''')] | |||
This video starts with a nice introduction to the category, and then solves a handful of practice problems. | |||
|- | |||
| <youtube width="300" height="180">https://youtu.be/lDm08rP_lms</youtube> | |||
| [https://youtu.be/lDm08rP_lms ''ACSL Prefix Postfix Infix Contest 2 Worksheet 1'' ('''misterminich''')] | |||
Mr. Minich is an ACSL advisor. This video was one of two he created to help prepare his students for the ACSL Prefix/Infix/Postfix category. It shows solutions to 5 different problems that have | |||
appeared in recent years. | |||
|} | |||
=== Other Videos === | |||
{| | |||
|- | |||
| <youtube width="300" height="180">https://youtu.be/Lj91oRv3EIY</youtube> | |||
| [https://youtu.be/Lj91oRv3EIY ''ACSL Prep - Mrs. Gupta - Prefix Infix Postfix'' ('''MegaChristian5555''')] | |||
This video starts with a nice introduction to the category, and then solves a handful of practice problems. | |||
|- | |||
| <youtube width="300" height="180">https://youtu.be/lDm08rP_lms</youtube> | |||
| [https://youtu.be/lDm08rP_lms ''ACSL Prefix Postfix Infix Contest 2 Worksheet 1'' ('''misterminich''')] | |||
Mr. Minich is an ACSL advisor. This video was one of two he created to help prepare his students for the ACSL Prefix/Infix/Postfix category. It shows solutions to 5 different problems that have | |||
appeared in recent years. | |||
|} | |||
Revision as of 21:42, 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: parentheses, exponentiation, multiplication/division, and addition/'subtraction. 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.
A quick check for determining whether a conversion is correct is to convert the result back into the original format.
One way to convert from prefix (postfix) to infix is to make repeated scans through the expression. Each scan, replace an operand with two adjacent operators, and replace with a parenthesized infix expression. This is not the most efficient algorithm, but works well for a human.
Problems in this category ask to convert between prefix, infix, and postfix, or to evaluate an expression in prefix or postfix.
Context
Prefix and postfix notation is also known as Polish and Reverse Polish notation, respectively, for the Polish logician Jan Lukasiewicz.
Examples
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 ↑ =
Examples Converting to Infix
Prefix to Infix Postfix to Infix
↑ + * 3 4 / 8 2 – 7 5 3 4 * 8 2 / + 7 5 -↑ ↑ + (3*4)/ 8 2 – 7 5(3*4)8 2 / + 7 5 - ↑↑ + (3*4)(8/2)– 7 5(3*4)(8/2)+ 7 5 - ↑↑ (3*4)+(8/2)- 7 5((3*4)+(8/2))7 5 -↑↑ ((3*4)+(8/2))(7-5)((3*4)+(8/2))(7-5)↑(((3*4)+(8/2))↑(7-5))(((3*4)+(8/2))↑(7-5))$(3*4+{8\over{2}})^{(7-5)}$ $(3*4+{8\over{2}})^{(7-5)}$
Examples
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 ↑ =
Examples Converting to Infix
Prefix to Infix Postfix to Infix
↑ + * 3 4 / 8 2 – 7 5 3 4 * 8 2 / + 7 5 -↑ ↑ + (3*4)/ 8 2 – 7 5(3*4)8 2 / + 7 5 - ↑↑ + (3*4)(8/2)– 7 5(3*4)(8/2)+ 7 5 - ↑↑ (3*4)+(8/2)- 7 5((3*4)+(8/2))7 5 -↑↑ ((3*4)+(8/2))(7-5)((3*4)+(8/2))(7-5)↑(((3*4)+(8/2))↑(7-5))(((3*4)+(8/2))↑(7-5))$(3*4+{8\over{2}})^{(7-5)}$ $(3*4+{8\over{2}})^{(7-5)}$
Online Resources
ACSL Videos
The following YouTube videos show ACSL students and advisors working out some previous problems. To access the YouTube page with the video, click on the title of the video in the icon. (You can also play the video directly by clicking on the arrow in the center of the image; however, you'll probably want to have a larger viewing of the video since it contains writing on a whiteboard.) Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.
| ACSL Prep - Mrs. Gupta - Prefix Infix Postfix (MegaChristian5555)
This video starts with a nice introduction to the category, and then solves a handful of practice problems. | |
| ACSL Prefix Postfix Infix Contest 2 Worksheet 1 (misterminich)
Mr. Minich is an ACSL advisor. This video was one of two he created to help prepare his students for the ACSL Prefix/Infix/Postfix category. It shows solutions to 5 different problems that have appeared in recent years. |
Other Videos
| ACSL Prep - Mrs. Gupta - Prefix Infix Postfix (MegaChristian5555)
This video starts with a nice introduction to the category, and then solves a handful of practice problems. | |
| ACSL Prefix Postfix Infix Contest 2 Worksheet 1 (misterminich)
Mr. Minich is an ACSL advisor. This video was one of two he created to help prepare his students for the ACSL Prefix/Infix/Postfix category. It shows solutions to 5 different problems that have appeared in recent years. |