Prefix/Infix/Postfix Notation - Revision history

Marc: /* Converting Expressions */

2021-12-20T19:04:40Z

Converting Expressions

← Older revision		Revision as of 12:04, 20 December 2021
Line 11:		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.		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 ~~operators~~ and replace it with a parenthesized infix 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.		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.		A quick check for determining whether a conversion is correct is to convert the result back into the original format.

	== Context ==		== Context ==

Marc: /* Video Resources */

2021-12-08T04:17:24Z

Video Resources

← Older revision		Revision as of 21:17, 7 December 2021
Line 108:		Line 108:

	{\|		{\|
	\|-
	~~\| <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.~~

	\|-		\|-

Marc: Reverted edits by Raj Joshi (talk) to last revision by Marc Brown

2020-07-23T17:39:34Z

Reverted edits by Raj Joshi (talk) to last revision by Marc Brown

← Older revision		Revision as of 10:39, 23 July 2020
Line 108:		Line 108:

	{\|		{\|
	\|-
	~~\| <youtube width="300" height="180">https://youtu.be/9UO5aDyHZ84</youtube>~~
	~~\| [https://youtu.be/9UO5aDyHZ84 "ACSL Math: Prefix/Infix/Postfix Notation" (Quick Coding Bytes)]~~

	~~This video introduces the topic, then using an example problem, explains the methodology to solve problems that appear on ACSL contests.~~

	\|-		\|-
	\| <youtube width="300" height="180">https://youtu.be/Lj91oRv3EIY</youtube>		\| <youtube width="300" height="180">https://youtu.be/Lj91oRv3EIY</youtube>

Raj Joshi: /* Video Resources */

2020-07-21T11:10:14Z

Video Resources

← Older revision		Revision as of 04:10, 21 July 2020
Line 108:		Line 108:

	{\|		{\|
			\|-
			\| <youtube width="300" height="180">https://youtu.be/9UO5aDyHZ84</youtube>
			\| [https://youtu.be/9UO5aDyHZ84 "ACSL Math: Prefix/Infix/Postfix Notation" (Quick Coding Bytes)]

			This video introduces the topic, then using an example problem, explains the methodology to solve problems that appear on ACSL contests.

	\|-		\|-
	\| <youtube width="300" height="180">https://youtu.be/Lj91oRv3EIY</youtube>		\| <youtube width="300" height="180">https://youtu.be/Lj91oRv3EIY</youtube>

Marc Brown: /* Context */

2018-09-09T09:42:14Z

Context

← Older revision		Revision as of 02:42, 9 September 2018
Line 21:		Line 21:
	== Context ==		== 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 [https://en.wikipedia.org/wiki/Polish_notation ''Polish'' and ''Reverse Polish'' notation], respectively.

	== Examples ==		== Examples ==

Marc Brown at 09:39, 9 September 2018

2018-09-09T09:39:31Z

← Older revision		Revision as of 02:39, 9 September 2018
Line 1:		Line 1:
	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 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 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.		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.		Problems in this category ask to convert between prefix, infix, and postfix, or to evaluate an expression in prefix or postfix.

Carlen at 12:16, 19 August 2018

2018-08-19T12:16:16Z

← Older revision		Revision as of 05:16, 19 August 2018
Line 104:		Line 104:

	== Video Resources ==		== Video Resources ==



	The following YouTube videos show ACSL students and advisors working out some previous problems.		The following YouTube videos show ACSL students and advisors working out some previous problems.
Line 134:		Line 132:

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


	\|-		\|-
Line 147:		Line 144:

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





	\|}		\|}
Line 156:		Line 149:
	=== Other Videos ===		=== Other Videos ===

	The ~~follow~~ 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.		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>		\| <youtube width="300" height="180">https://youtu.be/t7YWDiz8LMY</youtube>
Line 187:		Line 180:
	\| [https://youtu.be/vq-nUF0G4fI ''Infix to Postfix using stack'' ('''mycodeschool''')]		\| [https://youtu.be/vq-nUF0G4fI ''Infix to Postfix using stack'' ('''mycodeschool''')]

	Describes the standard algorithm to convert from infix to postfix.		Describes the standard algorithm to convert from infix to postfix.
			\|}


			<!--
			{\|
			\|-
			\| <youtube width="300" height="180">URL</youtube>
			\| [URL ''TITLE'' ('''AUTHOR''')]

			DESCRIPTION
	\|}		\|}
			-->

Carlen: /* Online Resources */

2018-08-19T12:12:58Z

Online Resources

← Older revision		Revision as of 05:12, 19 August 2018
Line 103:		Line 103:
	\|}		\|}

	== ~~Online~~ Resources ==		== Video Resources ==



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

Marc Brown: /* ACSL Videos */

2018-08-15T18:26:40Z

ACSL Videos

← Older revision		Revision as of 11:26, 15 August 2018
Line 130:		Line 130:
	\|-		\|-
	\| <youtube width="300" height="180">https://youtu.be/R-t9-rbJDw8</youtube>		\| <youtube width="300" height="180">https://youtu.be/R-t9-rbJDw8</youtube>
	\| [https://youtu.be/R-t9-rbJDw8 ''~~Postive~~ Notation'' ('''Tangerine Code''')]		\| [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.''		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.

Marc Brown: /* ACSL Videos */

2018-07-31T16:27:29Z

ACSL Videos

← Older revision		Revision as of 09:27, 31 July 2018
Line 127:		Line 127:

	To quote the video description: ''A general tutorial on prefix notation that can be used for American Computer Science League.''		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 ''Postive Notation'' ('''Tangerine Code''')]

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




	\|}		\|}