parsing: polish postfix

Goals, Skills & Concepts Introduction & Background Description Specifications Approach

Minimal Requirements ('C' version) ('B' version) ('A' Version) Testing and Marking Bonuses Challenge

Extra Lab Notes

Goals, Skills and Concepts:

• 1st OO program
• definition and use of classes
• composition
• intro to BNF
• intro to formal definition of languages
• intro to parsing
• encapsulation

Introduction and Background:
Write a program that will read in a 'standard' arithmetic expression, convert it to Polish Postfix notation, print out the postfix version and then finally evaluate the postfix version of the equation, printing out the answer.

Description:

All "terminal symbols" (i.e. numbers, operators, parentheses) are assumed to consist of a single character. Because of this, spaces are unnecessary and should be ignored. (Note: spaces can appear everywhere/ anywhere; we must ignore them. If you wish to allow more complex expressions, blanks should still be redundant).

Specifications:

All expressions are terminated with semi-colons. You may choose to force the user to enter only one expression per "physical line" or allow multiple, semi-colon separated expressions per line as well as expressions that span physical lines.

Empty expressions must be accepted.

Minimal requirements are to be able to read any and all legally formed expressions (not including parentheses). Your program is to read and parse them, convert them to Polish postfix and print out the Postfix form. This must be an object-oriented approach; each class must be contained in a separate source file. You must include a graphical (picture) representation of your classes and their relationships in your documentation. Your program must make use of 2 separate stacks: one for building the Postfix and the other as a place to hold "tokens" temporarily.

The B solution does all this plus it can recognize invalid expressions (recovery is best but recognition and "bailing" is sufficient). It will also be able to evaluate the Polish expression and print out the result (the answer) of the expression. The stack for building up the Postfix must be implemented as a deque. The Postfix form is not to be copied to another location before beginning the evaluation.

The A solution adds better error detection / recovery facilities as well as implementing the ability to parse and transform expressions containing parentheses.

Approach:

 See Lab Pages for way too much on this.

Requirements & Grading:

'C' Version:

1. Approach is OO
2. Documentation includes UML(ish) class diagrams
3. Handles a valid AE (without "( )" )
4. Uses 2 stacks.
5. Prints the Polish Postfix version of the expression.
   

'B' Version: All that the 'C' Version does, PLUS:

1. Handles (recognizes and doesn't blow up) invalid expressions
2. Evaluates the Postfix Expression
3. Uses 1 stack and 1 dequeue
4. Handles empty expressions
   

'A' Version: All that the 'B' Version does, PLUS:

1. Handles "( )" {recursively?}
2. Prints meaningful diagnostic messages
   
   

Testing:
Sample Executables: /home/233/Parser/AE

Test your program using at least the following expressions :

'C' Version	'B' Version ('C' plus:)	'A' Version ('B' plus:)
1 + 2 ; 1 + 2 + 3; 1 + 2 - 3; 1 + 2 * 3; 1 * 3 + 2; 1 + 2 * 3 + 4; 1 * 2 - 3 *4; 1 + 2 * 3 - 4; 8 / 4 / 2;	1 + ; + 2 + 3; 1 + 2 ^ 3; 1 ++ 2 * 3; 1 * 3 + 2 8 / 4 * 2;  ; 4 ++ 6; 2 7 3;	1 + (2) ; 1 + 2 + 3; 1 + 2 - 3; 1 + (2 * 3); 1 (* 3) + 2; (1 + 2) * (3 + 4); ((1 + 2) * 3 - 4; 8 / (4 / 2);  5 + (6 - 7); (3 (2 + 1)); ((7 + 6) * (4 + 2)); ((7 = 6) * (4 + 2); (3 * (2 + 1)); (2) + (2);

BONUSES:

1. [2 points] allow operands to be any natural number
2. [4 points] implement unary operators + -
3. [4 points] implement bit wise & | ^ ~ with proper precedence
4. [up to 6 points] allow operands to be any legal number (real or integer)
5. [up to 10 points] implement full functionality (as found in a typical mid-range calculator)

Challenges:

Not this time. On some assignments, the most involved and challenging bonuses (OK, sometimes just stupidly hard or ridiculous amounts of work) will be listed under this category.

Updated: October 19, 2005 11:29 AM