Solved-HOMEWORK 8- Solution

Description

Be sure to include your name at the beginning of each le! Assignment 8 includes a programming portion and a written part. The programming portion must compile and consist of a single le (hw08.cpp). The typed portion should consist of a single le (hw08written.pdf). It must be in a .pdf format. Be sure to include your name at the beginning of each le! You must hand in the le via NYU Classes.

• Programming Part

• 1. Write the code to check for balanced parenthesis in a C++ program. If the C++ program has a mis-matched parenthesis¹, your code prints out the line number where the mismatched² occurred.

To do this you will nish writing the Balance class. The signature for the Balance class is in a le called Balance.cpp.

The Balance class has a single public method called checkBalance that:

takes no arguments and returns the number of mismatched parenthesis. The method checkBalance will print an error³ message and update the error count if the stack is empty and a closing parenthesis is found, or the end of the le is reached and the stack is not empty

uses the tokenizer class to pull out the parenthesis from the C++ program. The tokenizer class is in a le called tokenizer.cpp

calls a method called checkMatch that compares two parenthesis to see if they match. This method prints an error message if the parenthesis are mismatched, and updates the error count

Check that your algorithm works on your own C++ program.

2. In this part, you will store a list of correctly spelled words and a point value associated with each word into a variable of type map<string, int>. You will perform the following steps:

Enter the point value from a le called Letter point value.txt for each letter into a variable of type vector<int>. The point value associated with ‘A’ goes into position 0, and ’B’ goes into position 1, etc.

The point value of a word is determined by the point value of each letter. To compute the point value of a word, add up the point values of each letter in the word. For example, the point value of “cat” is 4 + 1 + 1 = 6, since ’C’ has a point value of 4, ’A’ has a point value of 1, and ’T’ has a point value of 1. Upper and lower case letters have the same point value. (e.g. So “CAT” also has a point value of 6.) Create a function to compute the point value of a word.

5% extra credit will be given if you turn this assignment in on Tues Nov 15 at 11:00 p.m.

• I encourage you to expand your code to nd mismatched brackets.

• For us, the mismatched occurred where you rst realized the parenthesis did not have a match. See the lecture slides for clari cation.

³The method checkBalance only checks some of the possible errors. The method checkMatch will check if the parenthesis do not match.

The words you will store are in a le called ENABLE.txt. You will read in each word and store it and its associated point value in a variable of type map<string,int>.

On your own⁴. You can write a program to help you play Words With Friends.

Remember the recursive function from the extra credit problem in a previous assignment, where the user enters a string and you nd all the combinations of the string.

For each string created from the recursive function, you can test to see if it is in the ENABLE word list. If so, you print out the word and the points associated with the word. Use the map<string,int> you created in programming part 2.

• Written Part

• 1. For each of the following in x expressions, illustrate the operation of the algorithm for converting in x to post x. Show the contents of the stack, and the output stream, after each token from the input is processed. If the in x expression is not syntactically valid, give an error message:

a.)	1	–		2		+	3	^		2
b.)	(2^3)					^ 2
c.)	2	^	3		^	2
d.)	(2		+			6)	/	3	–	(32 + 4 * 7)*2
e.)	3	+	2		–	4	+ 5
f.) (3 +			2)		^4^(3*					2+4)

2. For each of the following post x expressions, illustrate the operation of the stack-based evaluation algo-rithm. Show the contents of the stack after each operand or operator symbol from the input is processed. Additionally, indicate the value of the expression or give an error message if the expression is not syntac-tically valid.

EXAMPLE: input 1 2 3 * +

	3
2	2	6
1 1	1	1	7 stack (growing up)

If you prefer, you can write the input vertically and the stack growing from left to right, as follows (easier to type!):

input	stack
1	1
2	1	2
3	1	2	3

• 1 6

• 7

a.)	4	2	+ 3		3	^	–
b.)	3	2		^	3		2	* –
c.)	4	2	3	*	– 3		2	^-6+
d.)	4	3	+		2 *		1	–
e.)	3		5	*	1		+	4 / 6	+

3. Add % to the PREC_TABLE table⁵ and to the TokenType so that % precedence can now be determined using

PREC_TABLE.

enum TokenType { EOL, VALUE, OPAREN, CPAREN, EXP, MULT, DIV, PLUS, MINUS };

• PREC_TABLE matches order of Token enumeration struct Precedence

{

⁵% has the same precedence as * and /.

5