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

From ACSL Category Descriptions
Jump to navigation Jump to search
 
(23 intermediate revisions by 5 users not shown)
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 is 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 <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.  
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 operands . 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.  
 
Problems in this category ask to convert between prefix, infix, and postfix, or to evaluate an expression in prefix or postfix.
 
== Converting Expressions ==


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 7: Line 11:
* Write down the operands in the same order that they appear in the infix expression.
* 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.
* 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.   
* For each term, write down the operator before (after) the operands.   
 
One way to convert from prefix (postfix) to infix is to make repeated scans through the expression.
Each scan, find an operator with two adjacent operands and replace it with a parenthesized infix expression.
This is not the most efficient algorithm, but works well for a human.
 
A quick check for determining whether a conversion is correct is to convert the result back into the original format.
 
== Context ==
 
''Prefix'' and ''postfix'' notation is also known as [https://en.wikipedia.org/wiki/Polish_notation ''Polish'' and ''Reverse Polish'' notation], respectively.
 
== Examples ==
 
=== Infix to Prefix ===
 
 
The following sequence of steps illustrates converting $X=\left(AB-{C\over{D}}\right)^E$ from infix to prefix:
::{| class="wikitable" style="text-align: center"
|-
!(X = (((A * B) - (C / D)) ↑ E))
|-
| style="background-color: #ffffff; text-align: left; padding-left: 2em"  |X A B C D E
|-
| style="background-color: #ffffff; text-align: left; padding-left: 2em" | X <syntaxhighlight lang="python" inline>* A B</syntaxhighlight> C D E
|-
| style="background-color: #ffffff; text-align: left; padding-left: 2em" | X <syntaxhighlight lang="python" inline>* A B</syntaxhighlight> <syntaxhighlight lang="python" inline>/ C D</syntaxhighlight> E
|-
| style="background-color: #ffffff; text-align: left; padding-left: 2em" | X <syntaxhighlight lang="python" inline>- * A B / C D</syntaxhighlight> E
|-
| style="background-color: #ffffff; text-align: left; padding-left: 2em" |  X <syntaxhighlight lang="python" inline>↑-  * A B / C D E</syntaxhighlight>
|-
| style="background-color: #ffffff; text-align: left; padding-left: 2em" | <syntaxhighlight lang="python" inline>= X ↑ - * A B / C D E</syntaxhighlight>
|}
 
=== Infix to Postfix ===


== Example ==


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 postfix:
::{| class="wikitable" style="text-align: center"
::{| class="wikitable" style="text-align: center"
|-
|-
!Infix to Prefix
!(X = (((A * B) - (C / D)) ↑ E))
!Infix to Postfix
|-
| style="background-color: #ffffff; text-align: left; padding-left: 2em"  |X A B C D E
|-
| style="background-color: #ffffff; text-align: left; padding-left: 2em" | X <syntaxhighlight lang="python" inline>A B *</syntaxhighlight> C D E
|-
| style="background-color: #ffffff; text-align: left; padding-left: 2em" | X <syntaxhighlight lang="python" inline>A B *</syntaxhighlight> <syntaxhighlight lang="python" inline>C D /</syntaxhighlight> E
|-
| style="background-color: #ffffff; text-align: left; padding-left: 2em" | X <syntaxhighlight lang="python" inline>A B * C D / -</syntaxhighlight> E
|-
| style="background-color: #ffffff; text-align: left; padding-left: 2em" |  X <syntaxhighlight lang="python" inline>A B * C D / - E ↑</syntaxhighlight>
|-
| style="background-color: #ffffff; text-align: left; padding-left: 2em" | <syntaxhighlight lang="python" inline> X A B * C D / - E ↑ =</syntaxhighlight>
|}


=== Prefix to Infix ===
The following sequence of steps illustrates converting  $(3*4+{8\over{2}})^{(7-5)}$  from its prefix representation to infix:
::{| class="wikitable" style="text-align: left"
|-
|-
|(X = (((A * B) - (C / D)) ↑ E)) || (X = (((A * B) - (C / D)) ↑ E))
! ↑ + * 3 4 / 8 2 – 7 5
|-
|-
| 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="background-color: #ffffff" | ↑ + <syntaxhighlight lang="python" inline>(3*4)</syntaxhighlight> / 8 2 – 7 5
|-
|-
| 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="background-color: #ffffff" |↑ + <syntaxhighlight lang="python" inline>(3*4)</syntaxhighlight> <syntaxhighlight lang="python" inline>(8/2)</syntaxhighlight> – 7 5
|-
|-
| 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="background-color: #ffffff" |↑ <syntaxhighlight lang="python" inline>(3*4)+(8/2)</syntaxhighlight> - 7 5
|-
|-
| 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="background-color: #ffffff" |↑ <syntaxhighlight lang="python" inline>((3*4)+(8/2))</syntaxhighlight> <syntaxhighlight lang="python" inline>(7-5)</syntaxhighlight>
|-
|-
| 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="background-color: #ffffff" |<syntaxhighlight lang="python" inline>(((3*4)+(8/2))↑(7-5))</syntaxhighlight>
|}
 
=== Postfix to Infix ===
 
The following sequence of steps illustrates converting  $(3*4+{8\over{2}})^{(7-5)}$  from its postfix representation to infix:
::{| class="wikitable" style="text-align: left"
|-
|-
| 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 ↑ =
!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> <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> <syntaxhighlight lang="python" inline>(7-5)</syntaxhighlight> ↑
|-
| style="background-color: #ffffff" |<syntaxhighlight lang="python" inline>(((3*4)+(8/2))↑(7-5))</syntaxhighlight>
|}
|}


A quick check for determining whether a conversion is correct is to convert the result back into the original format. THhat is, to convert from ''prefix'' notation to ''infox  This is best done by changing groups of 2 operands and an operator into a parenthesized infix expression. This needs to be done for us to evaluate the expression easily. Using different examples, here is the process of converting back to infix:
== Video Resources ==
Prefix to Infix: Postfix to Infix:
 
↑ + * 3 4 / 8 2 – 7 5 7 1 + 2 ↑ 7 3 - / 4 + 5 /
The following YouTube videos show ACSL students and advisors working out some previous problems.
↑ + (3 * 4) (8 / 2) (7 – 5) (7 + 1) 2 ↑ (7 – 3) / 4 + 5 /
 
↑ ((3 * 4) + (8 / 2)) (7 – 5) ((7 + 1) ↑ 2) (7 – 3) / 4 + 5 /
{|
(((3 * 4) + (8 / 2)) ↑ (7 – 5)) = 256 ((((7 + 1) ↑ 2) / (7 – 3)) + 4) / 5) = 4
 
|-
| <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 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.
 
|-
| <youtube width="300" height="180">https://youtu.be/4YZdsw2UOpo</youtube>
| [https://youtu.be/4YZdsw2UOpo ''Prefix Notation'' ('''Tangerine Code''')]
 
To quote the video description: ''A general tutorial on prefix notation that can be used for American Computer Science League.''
 
|-
| <youtube width="300" height="180">https://youtu.be/R-t9-rbJDw8</youtube>
| [https://youtu.be/R-t9-rbJDw8 ''Postfix Notation'' ('''Tangerine Code''')]
 
To quote the video description: ''A general tutorial on postfix notation that can be used for American Computer Science League.''
 
|-
| <youtube width="300" height="180">https://youtu.be/dcc-nXY2L6c</youtube>
| [https://youtu.be/dcc-nXY2L6c ''2015 16 Contest 2 Prefix Infix Postfix Problem#1'' ('''Ravi Yeluru''')]
 
Ravi Yeluru walks through the solution to an ACSL Prefix/Infix/Postfix program that appeared in the 2015-16 year, Contest #2.
 
|-
| <youtube width="300" height="180">https://youtu.be/lEIPvUqstEY</youtube>
| [https://youtu.be/lEIPvUqstEY ''2015 16 Contest 2 Prefix Infix Postfix Problem#2'' ('''Ravi Yeluru''')]
 
Ravi Yeluru walks through the solution to an ACSL Prefix/Infix/Postfix program that appeared in the 2015-16 year, Contest #2.
 
|}
 
=== Other Videos ===
 
The following YouTube videos cover various aspects of this topic; they were created by authors who are not involved (or aware) of ACSL, to the best of our knowledge. 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/t7YWDiz8LMY</youtube>
| [https://youtu.be/t7YWDiz8LMY ''Infix Postfix and Prefix Notation'' ('''Carleton Moore''')]
 
A very gentle overview of infix, prefix, and postfix.
|-
| <youtube width="300" height="180">https://youtu.be/z3VsmufB_QI</youtube>
| [https://youtu.be/z3VsmufB_Q I''Infix Prefix and Postfix'' ('''University Academy''')]
 
Another very gentle overview of infix, prefix, and postfix.
|-
| <youtube width="300" height="180">https://youtu.be/jos1Flt21is</youtube>
| [https://youtu.be/jos1Flt21is ''Infix Postfix and Prefix Notation'' ('''mycodeschool''')]
 
Another overview of infix, prefix, and postfix notations.
|-
| <youtube width="300" height="180">https://youtu.be/MeRb_1bddWg</youtube>
| [https://youtu.be/MeRb_1bddWg ''Evaluation of Prefix and Postfix expressions using stack'' ('''mycodeschool''')]
 
Describes the standard algorithm to evaluate prefix and postfix expressions.
 
|-
| <youtube width="300" height="180">https://youtu.be/vq-nUF0G4fI</youtube>
| [https://youtu.be/vq-nUF0G4fI ''Infix to Postfix using stack'' ('''mycodeschool''')]
 
Describes the standard algorithm to convert from infix to postfix.
|}
 
 
<!--
{|
|-
| <youtube width="300" height="180">URL</youtube>
| [URL ''TITLE'' ('''AUTHOR''')]
 
DESCRIPTION
|}
-->

Latest revision as of 11:04, 20 December 2021

The expression $5+\large{8\over{3-1}}$ clearly has a value of 9. It is 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 operands . 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.

Problems in this category ask to convert between prefix, infix, and postfix, or to evaluate an expression in prefix or postfix.

Converting Expressions

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 operator before (after) the operands.

One way to convert from prefix (postfix) to infix is to make repeated scans through the expression. Each scan, find an operator with two adjacent operands and replace it with a parenthesized infix expression. This is not the most efficient algorithm, but works well for a human.

A quick check for determining whether a conversion is correct is to convert the result back into the original format.

Context

Prefix and postfix notation is also known as Polish and Reverse Polish notation, respectively.

Examples

Infix to Prefix

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

(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

Infix to Postfix

The following sequence of steps illustrates converting $X=\left(AB-{C\over{D}}\right)^E$ from 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 ↑ =

Prefix to Infix

The following sequence of steps illustrates converting $(3*4+{8\over{2}})^{(7-5)}$ from its prefix representation 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))

Postfix to Infix

The following sequence of steps illustrates converting $(3*4+{8\over{2}})^{(7-5)}$ from its postfix representation 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))

Video Resources

The following YouTube videos show ACSL students and advisors working out some previous problems.

ACSL Prefix Postfix Infix Contest 2 Worksheet 1 (misterminich)

Mr. Minich is an ACSL advisor. This video was 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.

Prefix Notation (Tangerine Code)

To quote the video description: A general tutorial on prefix notation that can be used for American Computer Science League.

Postfix Notation (Tangerine Code)

To quote the video description: A general tutorial on postfix notation that can be used for American Computer Science League.

2015 16 Contest 2 Prefix Infix Postfix Problem#1 (Ravi Yeluru)

Ravi Yeluru walks through the solution to an ACSL Prefix/Infix/Postfix program that appeared in the 2015-16 year, Contest #2.

2015 16 Contest 2 Prefix Infix Postfix Problem#2 (Ravi Yeluru)

Ravi Yeluru walks through the solution to an ACSL Prefix/Infix/Postfix program that appeared in the 2015-16 year, Contest #2.

Other Videos

The following YouTube videos cover various aspects of this topic; they were created by authors who are not involved (or aware) of ACSL, to the best of our knowledge. Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.

Infix Postfix and Prefix Notation (Carleton Moore)

A very gentle overview of infix, prefix, and postfix.

IInfix Prefix and Postfix (University Academy)

Another very gentle overview of infix, prefix, and postfix.

Infix Postfix and Prefix Notation (mycodeschool)

Another overview of infix, prefix, and postfix notations.

Evaluation of Prefix and Postfix expressions using stack (mycodeschool)

Describes the standard algorithm to evaluate prefix and postfix expressions.

Infix to Postfix using stack (mycodeschool)

Describes the standard algorithm to convert from infix to postfix.


Retrieved from "http://www.categories.acsl.org/wiki/index.php?title=Prefix/Infix/Postfix_Notation&oldid=877"