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

Objective:

With your team, convert the Boolean 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 example:

Example:

( i > 1 ) && ! ( j > 6 )

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

STEP	INPUT TOKEN	POSTFIX	STACK
1	(
2	i		(
3	>	i	(
4	1	i	( >
5	)	i 1	( >
6	&&	i 1 >
7	!	i 1 >	&&
8	(	i 1 >	&& !
9	j	i 1 >	&& ! (
10	>	i 1 > j	&& ! (
11	6	i 1 > j	&& ! ( >
12	)	i 1 > j 6	&& ! ( >
13		i 1 > j 6 >	&& !
14		i 1 > j 6 > ! &&

How do I implement the Shunting Yard algorithm?

Please use the procedure I have posted for Boolean expressions. 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: You may safely presume the variables below are appropriate types (integer or Boolean) and can properly evaluate to a Boolean expression. The token attributes for all variables is "IDENTIFIER".

• a || b && ((c > 0) && (c < 5))
• (aa || bb && cc) || (cc && dd || ee && ff) && (gg != 0)
• (aaa != 0) || (bbb > (ccc + ddd * eee)) && (fff > 6)

Submission Instructions:

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

Exercise 5b Grading Rubric

CRITERIA	RATINGS				POINTS
Problem 1	Proficient 2 points Boolean 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 Boolean 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 Boolean 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 4 points Boolean 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.8 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 Boolean expression is incomplete; OR there are between one and three mistakes in the solution.	Needs Improvement 2.4 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 Boolean expression is incomplete; OR there are four or more mistakes in the solution.	Below Expectation 0 points No solution submitted.	4 points
Problem 3	Proficient 4 points Boolean 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.8 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 Boolean expression is incomplete; OR there are between one and three mistakes in the solution.	Needs Improvement 2.4 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 Boolean expression is incomplete; OR there are four or more mistakes in the solution.	Below Expectation 0 points No solution submitted.	4 points
Total points: 10