Sonoma State University
Department of Computer Science
CS-460: Programming Languages
Exercise 5a: Converting numerical expressions from infix to postfix

Objective:

With your team, convert the numerical expressions (below) from infix notation into postfix notaton using the Shunting Yard Algorithm. Please show the step-by-step process of conversion like the following examples:

Example:

1 * ( 2 * ( 3 * ( 4 - 5 ) + 6 ) + 7 )

Step-by-step example processing an input numerical expression:

STEP	INPUT TOKEN	POSTFIX OUTPUT	STACK
1	1
2	*	1
3	(	1	*
4	2	1	* (
5	*	1 2	* (
6	(	1 2	* ( *
7	3	1 2	* ( * (
8	*	1 2 3	* ( * (
9	(	1 2 3	* ( * ( *
10	4	1 2 3	* ( * ( * (
11	-	1 2 3 4	* ( * ( * (
12	5	1 2 3 4	* ( * ( * ( -
13	)	1 2 3 4 5	* ( * ( * ( -
14	+	1 2 3 4 5 -	* ( * ( *
15	6	1 2 3 4 5 - *	* ( * ( +
16	)	1 2 3 4 5 - * 6	* ( * ( +
17	+	1 2 3 4 5 - * 6 +	* ( *
18	7	1 2 3 4 5 - * 6 + *	* ( +
19	)	1 2 3 4 5 - * 6 + * 7	* ( +
20		1 2 3 4 5 - * 6 + * 7 +	*
21		1 2 3 4 5 - * 6 + * 7 + *

How do I implement the Shunting Yard algorithm?

Please use the procedure I have posted for converting numerical expressions in to postfix notation. Since this is an in-class exercise, please ask me questions if you need any help.

Please convert the following numerical expressions from infix notation to postfix notation:

Note: The letters in the numerical expressions below denote integer variable types. Their token attributes are "IDENTIFIER". The percent sign is the token "MODULO".

• a - b * c + ( d - e * f )
• a * b - c * d / ( ( f + 1 ) * ( g + 2 ) )
• ( a + b + c + d ) / (2 + b * 4) - ( ( e * 3 ) % (2 + 2 ) )

Submission Instructions:

Please include the names of each member of your team along with "Exercise 5a: Converting numerical expressions from infix to postfix".

Exercise 5a Grading Rubric

CRITERIA	RATINGS				POINTS
Problem 1	Proficient 2 points Numerical expression is in postfix notation. Steps to convert from infix to postfix are present which includes STEP, INPUT TOKEN, POSTFIX OUTPUT, and STACK (state of the stack). There are no mistakes in the solution.	Satisfactory 1.4 points Steps to convert from infix to postfix are present which includes STEPS, INPUT TOKEN, POSTFIX OUTPUT, and STACK (state of the stack) but the numerical expression is incomplete; OR there are between one and three mistakes in the solution.	Needs Improvement 1.2 points Steps to convert from infix to postfix are present. The STEPS, INPUT TOKEN, POSTFIX OUTPUT, and STACK (state of the stack) may be present but the numerical expression is incomplete; OR there are four or more mistakes in the solution.	Below Expectation 0 points No solution submitted.	2 points
Problem 2	Proficient 3 points Numerical expression is in postfix notation. Steps to convert from infix to postfix are present which includes STEP, INPUT TOKEN, POSTFIX OUTPUT, and STACK (state of the stack). There are no mistakes in the solution.	Satisfactory 2.1 points Steps to convert from infix to postfix are present which includes STEPS, INPUT TOKEN, POSTFIX OUTPUT, and STACK (state of the stack) but the numerical expression is incomplete; OR there are between one and three mistakes in the solution.	Needs Improvement 1.8 points Steps to convert from infix to postfix are present. The STEPS, INPUT TOKEN, POSTFIX OUTPUT, and STACK (state of the stack) may be present but the numerical expression is incomplete; OR there are four or more mistakes in the solution.	Below Expectation 0 points No solution submitted.	3 points
Problem 3	Proficient 5 points Numerical expression is in postfix notation. Steps to convert from infix to postfix are present which includes STEP, INPUT TOKEN, POSTFIX OUTPUT, and STACK (state of the stack). There are no mistakes in the solution.	Satisfactory 3.5 points Steps to convert from infix to postfix are present which includes STEPS, INPUT TOKEN, POSTFIX OUTPUT, and STACK (state of the stack) but the numerical expression is incomplete; OR there are between one and three mistakes in the solution.	Needs Improvement 3 points Steps to convert from infix to postfix are present. The STEPS, INPUT TOKEN, POSTFIX OUTPUT, and STACK (state of the stack) may be present but the numerical expression is incomplete; OR there are four or more mistakes in the solution.	Below Expectation 0 points No solution submitted.	5 points
Total points: 10