CS 2213/2211 -- Recitation 9

CS 2213/2211
Advanced Programming
Spring 2005
Recitation 9: Reverse Polish and
   translation using a struct
    Week 9: Mar 22-24
Due (on time): 2005-03-29  23:59:59
Due (late):        2005-04-03  23:59:59

Recitation 9 should be submitted following directions at: submissions with deadlines

2005-03-29 23:59:59 (that's Tuesday, 29 March 2005, 11:59:59 pm) for full credit.
2005-04-03 23:59:59 (that's Sunday, 3 April 2005, 11:59:59 pm) for 75% credit.

Introduction: This recitation works on areas:

Use of "bare" structs in C.
Reverse Polish Notation (RPN).
Translators.

Overview: For this assignment you will write a program translate that will translate an ordinary arithmetic expression into reverse Polish notation (RPN). This program should be used in conjunction with a program evaluate that will find the final value of an input RPN expression expression. (I am having you write the evaluate program first because it is easier.) Together the two programs will find the value of an input arithmetic expression. In fact, for the final runs after initial testing, you can pipe the output of translate in as input to evaluate, so that you use the command:

% translate  < sourcefile | evaluate

The input source will be made up of the following elements:

single-digit integer constants, 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9.
operators: +, -, *, /, or ^ (raise to a power).
parentheses: ( or ).
a special symbol: $ to terminate the whole input.

This assignment limits to single-digit integer constants in order to keep things simpler.

For example, here is sample input arithmetic expression, which calculates one root of the equation y = x² + 3x + 2:

((3^2 - 4*1*2)^(1/2) - 3)/(2*1)$

This will be translated into RPN::

32^41*2*-12/^3-21*/$

and then evaluated to produce the answer (the root) of -1.000000

Notice that all whitespace (= space, newline, tab, etc.) should be ignored on input.

Reverse Polish Notation (RPN): This is a simple parenthesis free and unambiguous notation in which operators follow their operands. Thus instead of 5+7, one writes 57+. In the simple examples in this recitation, each single digit is a separate operand, but that would not be the case in general. An RPN string is evaluated left to right. Each operator takes the two previous operands, and the result becomes a new operand. Thus the arithmetic expression 3+4*5 is translated to RPN as: 345*+. In evaluating this, the * applies to 4 and 5, giving 20, a new operand. Then the + applies to the 3 and the 20, to get 23. Similarly, the arithmetic expression 3*4+5 is translated to RPN as: 34*5+, and evaluated to get 17. Notice that in evaluating the arithmetic expressions, one needs to know that* has precedence over +, but the value of the RPN does not rely on this.

It is easy and natural to use a stack to evaluate RPN. The RPN string is processed item-by-item from left to right. An operand has its value pushed on a stack. An operator (all assumed to be infix with two operands here) causes its two operands to be popped off the stack, the operator is applied to these two operands, and the result is pushed onto the stack. If there are not two operands for an operator, that is an error, and at the end there should be a single operand on the stack.

A. Evaluate an RPN String: Here are the requirements for this part:

Requirements for Part A
Evaluate the string as a `double`. Use a stack of `double`s for the evaluation. The stack should be implements as a separate file, with a header file. You could partly mimic the stack of `char` that was presented earlier: Stack, but you should check that you don't pop an empty stack or push onto a full stack. Use `getchar()` to read the input as a sequence of `char`s. Ignore whitespace. Given a digit, you should read the digit as a `char`. Then you need to convert this, call it `ch`, to an `int` with the value of the digit. This can be done with `(ch - '0')`. Finally cast to a `double` and push onto the stack. The RPN string `85-$` should evaluate to `3`, so you must subtract the top element of the stack from the next-to-the-top element, and similar for division. Implement the `^` operator with the C function `pow`. You will need the header `<math.h>` and a `-lm` as part of the compile command. Print the final value of the RPN string as a `double`. Test your `evaluate` program with the data in the "Table of Test Runs" near the end of this recitation.

Requirements for Part A

Evaluate the string as a double.
Use a stack of doubles for the evaluation. The stack should be implements as a separate file, with a header file. You could partly mimic the stack of char that was presented earlier: Stack, but you should check that you don't pop an empty stack or push onto a full stack.
Use getchar() to read the input as a sequence of chars. Ignore whitespace.
Given a digit, you should read the digit as a char. Then you need to convert this, call it ch, to an int with the value of the digit. This can be done with (ch - '0'). Finally cast to a double and push onto the stack.
The RPN string 85-$ should evaluate to 3, so you must subtract the top element of the stack from the next-to-the-top element, and similar for division.
Implement the ^ operator with the C function pow. You will need the header <math.h> and a -lm as part of the compile command.
Print the final value of the RPN string as a double.
Test your evaluate program with the data in the "Table of Test Runs" near the end of this recitation.

B. Translate an Arithmetic Expression to RPN: This part is considerably more challenging than Part A. We will discuss this in class, so what follows in only an outline.

Requirements for Part B
Read a sequence of single-character items representing an input arithmetic expression, made up of just the characters mentioned above. Use a stack of `char`s to push operators during the translation. This stack must be completely separate from the stack of `double`s used for evaluation, with even the names of functions, such as `empty()` distinct. Use the information in the section below titled "Precedence of Operators and Translation Rules" to see how to handle this precedence and how to carry out the translation. Print the final RPN string with the `$` at the end. Test your `translate` program with the data in the "Table of Test Runs" near the end of this recitation.

Requirements for Part B

Read a sequence of single-character items representing an input arithmetic expression, made up of just the characters mentioned above.
Use a stack of chars to push operators during the translation. This stack must be completely separate from the stack of doubles used for evaluation, with even the names of functions, such as empty() distinct.
Use the information in the section below titled "Precedence of Operators and Translation Rules" to see how to handle this precedence and how to carry out the translation.
Print the final RPN string with the $ at the end.
Test your translate program with the data in the "Table of Test Runs" near the end of this recitation.

Precedence of Operators and Translation Rules: The following table gives the precedence of operators, with 4 the highest. Under "Associativity", an L means "left-to-right" associativity. The entries for ( and ) as if they were operators will be explained below.

Precedence and Associativity Table
Operator	Precedence	Associativity
`^`	`4`	`R`
`*`	`3`	`L`
`/`	`3`	`L`
`+`	`2`	`L`
`-`	`2`	`L`
`(`	`1`	`R`
`)`	`1`	`R`

In order to handle precedence and associativity in your program, you must use a C struct like the following. One such struct variable can hold the information for one operator.

struct prec {
   char op;
   int preced;
   char assoc;
};

You must write a function getprec with prototype: struct prec getprec(char );. Inside this function you must have a static array of structs declared and initialized using curley bracket notation so as to hold the information in the above table. (If you are having trouble with this initialization, here is some help: Struct initializtion.) Given an input character representing an operator, the function getprec should look the operator up in the array and return the struct entry with the given operator as its first field. Then this information must be used in the program that carries out the translation.

Here are rules for the translation process:

Rules for translation to RPN
Always output an operand (a single digit). Always push a left parenthesis. Always push an operator if the stack is empty, if an operator of lower precedence is on top, or if an operator of equal precedence is on top and right-to-left associativity applies. Otherwise pop and output the stacktop, and try rule 3 again. A left and a right parenthsis (right above left) on the stack are always simply deleted. Depending on how you handle the parentheses, when you get a right parenthesis, you may need to explicitly pop operators off the stack and send them to output until you get to a left parenthesis. (And both parentheses must be deleted.) A `$` character terminates the current input. Empty any remaining operators on the stack to output. Output a `$` and terminate the program.

Rules for translation to RPN

Always output an operand (a single digit).
Always push a left parenthesis.
Always push an operator if the stack is empty, if an operator of lower precedence is on top, or if an operator of equal precedence is on top and right-to-left associativity applies.
Otherwise pop and output the stacktop, and try rule 3 again.
A left and a right parenthsis (right above left) on the stack are always simply deleted.
Depending on how you handle the parentheses, when you get a right parenthesis, you may need to explicitly pop operators off the stack and send them to output until you get to a left parenthesis. (And both parentheses must be deleted.)
A $ character terminates the current input. Empty any remaining operators on the stack to output. Output a $ and terminate the program.

Test Runs Here are test runs for the two programs:

Table of Test Runs
Input arithmetic expression	Output reverse Polish	Final value
`2+3*4$`	`234*+$`	`14.000000000000`
`3*4+5$`	`34*5+$`	`17.000000000000`
`(2+3)*4$`	`23+4*$`	`20.000000000000`
`1+2+3+4$`	`12+3+4+$`	`10.000000`
`3^2^2^2$`	`3222^^^$`	`43046721.000000000000`
`((1)+(((2))))*((((3))))$`	`12+3*$`	`9.000000000000`
*(3(2+4)/(5+1))-2$**	`324+*51+/2-$`	`1.000000000000`
`(5+3)^(2+1)^2$`	`53+21+2^^$`	`134217728.000000000000`
`2+34^56+7$`	`2345^6+7+$`	`18441.000000000000`
`((3^2-412)^(1/2)-3)/(2*1)$`	`32^412-12/^3-21*/$`	`-1.000000000000`
`((2-3)^((4+1)5)/6-(2-4)7)-8$`	`23-41+5^6/24-7-8-$`	`5.833333333333`

Test runs for both programs piped together Here are test runs for the two programs: More test runs.

What you should submit: Refer to the submissions directions and to deadlines at the top of this page. The text file that you submit should first have Your Name, the Course Number, and the Recitation Number. The rest of the file should have the following in it, in the order below, and clearly labeled, including at the beginning the appropriate item letters: a, b, c, etc.

Contents of email submission for Recitation 9:
Last Name, First Name; Course Number; Recitation Number.
a. Program source code for Part A, including evaluate.c, source code for the stack, and the source for the header file that goes with the stack.
b. Results of runs of the input data from the second column of the table "Table of Test Runs" above. In each case the output should be the value given in the third column.
c. Program source code for Part B, including translate.c, source code for the stack, and the source for the header file that goes with the stack. (A separate stack from part A.)
d. Results of runs of the input data from the first column of the table "Table of Test Runs" above. In each case the output should be the value given in the second column.
e. Results of runs for the extra test data linked to above.
Beware: Since the stacks are array based, you may need to increase their size to handle the runs in part e above.

Revision date: 2005-03-20. (Please use ISO 8601, the International Standard.)