Due: Monday, April 20 at 2200 hours.
Hand out: Sample input (valid expressions, invalid expressions), my reference program
Hand in: Makefile and all the necessary program files. When I type "make" with no command line argument, your Makefile should create an executable named topostfix. Your program should compile on CSIF Linux machines and behave the same as my reference program.
Note: This is a group homework. You should work in groups of two. Only
one person from each group shall hand in all the files. At the beginning
of each file, write each team member's
name and email username at ucdavis.edu (one person per line) as comments.
For example:
Simpson, Bart; bsimpson
Burns, Montgomery; mburns
Implement a program that transforms infix expressions to postfix while detecting errors in the expressions.
An expression consists of numbers, operators, and left and right parentheses. A number consists of one or more digits. An operator consists of one or more characters that are not digits or left or right parentheses; however, only the operators defined in Table 1 are valid. A unary operator may be used as both prefix and postfix. For example, both !123 and 123! are valid. No space exists in any infix expression. Numbers are separated by operators or parentheses, and operators are separated by numbers or parentheses. Here are examples of valid infix expressions.
Detect all the errors, defined in Table 2, in the input infix expressions. Here are examples of invalid infix expressions. When encountering an error while transforming an infix expression, stop processing the expression, do NOT output any partial postfix expression that might have been built, print an appropriate error message to be specified below, and skip to the next infix expression in the input. If multiple errors occur in an infix expression, select any one of them to print.
Input: Read input from cin. The input consists of one or more infix expressions separated by '\n'. There is no space before, in, or after any expression. Your program should quit when encountering EOF.
Your program should NOT expect any input other than the above. E.g., your program should NOT ask the user to enter a string, such as "q" or "exit", to signal the end of the input.
Output:
cout. Separate neighboring numbers and operators by one space character, but do not print any space before or after the expression. Print a '\n' at the end of the expression.
cerr. The error message should start with "Error: " (without the quotations), followed by a string specified in Table 2.| Operator | Priority | Number of Operands |
|---|---|---|
| ! | 1 | unary |
| * | 2 | binary |
| / | 2 | binary |
| % | 2 | binary |
| + | 3 | binary |
| - | 3 | binary |
| < | 4 | binary |
| <= | 4 | binary |
| >= | 4 | binary |
| > | 4 | binary |
| == | 5 | binary |
| != | 5 | binary |
| && | 6 | binary |
| || | 7 | binary |
| Error message | Examples |
|---|---|
| Invalid token | 1%%2 1abc2 |
| Too many operands |
1!2 (1+2)!3 1!(2+3) (1+2)!(3+4) 0+(1+2)!(3+4)+5 0+((1+2)!(3+4))+5 |
| Too few operands |
-1 1- (-1) (1-) -(1-2) (1-2)- 1-(2-3)-4- -1-(2-3)-4 1-(2-(3-4)-5-)-6 |
| Too many left parentheses | (1+2 ((1+2)+3 |
| Too few left parentheses | 1+2) (1+2)+3) |