Ponder 02 : Infix to Postfix

Due Saturday at 5:00 PM MST

The second programming assignment will be to implement the stack data structure and use it to convert an infix mathematical expression (4 + 8 * 3) into a postfix one (4 8 3 * +). This, and all future assignments for CS 235, will consist of two parts: the first part is to implement the data structure of the week, the second is to use the data structure to solve a problem.

Pair Programming

Pair programming can be described as “two programmers, one keyboard.” Here, one programmer is the “driver” and operates the keyboard. The second (the “copilot”) follows along and offers feedback and ideas. This technique works best if the programmers periodically trade role of “driver.”

When both programmers are physically in the same room, they keep a running dialog going about the problem they are trying to solve and the quality of the solution they are exploring. When the copilot feels it is time to switch roles, he offers “Can I drive?”

When the programmers are not in the same room, the pair programming technique can still work through Skype or similar technology. Here, the driver simply shares his screen with the copilot. Switching roles is a little more of a hassle. It is not uncommon for both programmers to share their screens so they just have to switch windows when it comes time to switch drivers.

When to use pair programming

Pair programming should not be used all of the time. In fact, you should count on spending about a third of your time on the assignment doing pair programming. The best times are:

Beginning: Being by talking through the entire assignment together with your partner. Discuss what needs to be done, how it is to be done, and who is to do what. Each of you needs to understanding 100% of the program so it is important to know how your partner's code works.
Problems: As always happens when writing code, you occasionally get stumped. You don't know how to do something, you can't find the bug in the program, or you don't know how to fix the bug. At this point, call on your partner for help. This means, of course, that your partner has to know the problem you are working on as well as how your code works. It also means that you need to be completely familiar with your partner's code!
End: You should count on spending at least a half hour bringing the various parts of the program together at the end. Hopefully it will go smoothly, but it may not. Be prepared to make last-minute adjustments. Also, use this time to carefully review your partner's code so you get full credit for style and code quality. Be ready to offer suggestions and be ready to accept suggestions for your partner. Remember, you both share the same goal: to get 100% on the assignment!

It is important for both programmers to be respectful of the other. Both have something to learn, but could stand to improve their coding techniques.

Mechanics

In order to work together on a program, it is necessary for both programmers to use the same account. A collection of shared accounts have been created for CS 235 just as they were for CS 165. To work with these accounts, please see the following steps:

First, please make sure the files on your directory are locked down. This can be accomplished with "chmod 700 ~".
Next, we have a special account created for CS 235 collaborators. These accounts are called "cs235s3g1", "cs235s3g2", and so on. This corresponds to "CS 235 Section 3 Group 2," you will need to specify the correct section. The default password is "Temple4dpc".
When you are ready to collaborate with your partner, one of you should "claim" a group login. You do this by finding one of the "cs235*" accounts that still has the default password. If you are able to login, then it is yours. Immediately change the password with: yppasswd
Now, with a changed password, the account is yours for the remainder of the semester. Please e-mail both the account name and the new password to your partner.

Please submit often just in case one of you accidentally deletes a file. All of your submissions will be in the submittedHomework directory as usual. Finally, please make sure to put all the group members' name in the makefile. It is important to note that any time an API is changed (basically, a header file is changed), then all the people in the group should meet (either through e-mail or in person) to discuss the change and make sure everything will work after the change.

Stack

Create a class encapsulating the notion of a stack. This will work exactly like the std::stack class. Of course, any data-type will need to be supported, so your class will be a template class. It will need to be defined in its own header file (stack.h). The class name must be stack.

Your class will need to support the following operations:

Constructors: Default constructor (create a stack with zero elements in it), a non-default constructor (taking a capacity value as a parameter), and the copy constructor. If there is insufficient memory to allocate a new buffer, then the following exception is thrown:
ERROR: Unable to allocate a new buffer for Stack.
Destructor: When finished, the class should delete all the allocated memory.
operator=: Assignment operator. This method takes a stack as a parameter and copies all the elements to this. If the current buffer size is sufficient, not allocation is made. If the current buffer size is not sufficient, enough space is allocated to accomodate the new data. If there is insufficient memory to allocate a new buffer, then the following exception is thrown:
ERROR: Unable to allocate a new buffer for stack. It also returns *this by-reference as all assignment operators should.
empty(): Test whether the stack is empty. This method takes no parameters and returns a Boolean value.
size(): Return the stack size. This method takes no parameters and returns an integer value.
clear(): Clear the contents. This method takes no parameters and returns nothing. Note that you do not need to free the allocated memory; just set the size member variable to zero.
push(): Adds an element to the stack. This method takes a single parameter (the element to be added to the end of the stack) and has no return value. Note that if the stack is full, then the capacity will be doubled. In the case of an allocation error, the following c-string exception will be throw:
ERROR: Unable to allocate a new buffer for Stack
pop(): Removes an element from the end of the stack, serving to reduce the size by one. Note that if the stack is already empty, the stack remains unchanged.
top(): Returns the element currently at the end of the stack. There are two versions of this method: one that returns the element by-reference so the element can be changed through the top() method. The second version returns the element by-value or const by-reference so this is not changed. If the stack is currently empty, the following exception will be thrown:
ERROR: Unable to reference the element from an empty stack

Note that the only way to access elements in a stack is through the top() method. This means that there is no iterator for stack.

Driver Program

A driver program is provided. This file (/home/cs235/week02/assignment02.cpp) will pound-include your header file (stack.h) and expect a template class stack to be defined therein. This program will exercise your class, filling the container with user input and displaying the results. As with previous assignments, a makefile will be provided (/home/cs235/week02/makefile). A header file (infix.h) will be provided and an implementation file (infix.cpp) as well. You will need to create a stack header file (stack.h).

Infix to Postfix

In addition to passing the four test functions for the stack class, you will also need to use the stack class to implement a program to convert an infix expression (4 + 8 * 3) into a postfix expression (4 8 3 * +). There is a discussion on this in chapter 2 of the textbook. Note that you will need to handle the following operators:

() The parentheses are the highest level of the order of operations.
^ The exponent operator comes immediately after the parentheses. Note that the algorithm in the textbook cannot handle the exponent operator properly. You will need to handle this case.
* / % Multiplication, division, and modulus are after the exponent operator. They are at the same level of the order of operations.
+ - Addition and subtraction are after multiplication, division, and modulus.

Your convertInfixToPostfix() function will prompt the user for an infix equation and display the postfix version of the same. The following is an example of the output, with underline text as user input:

Enter an infix equation.  Type "quit" when done.
infix > 2 + 5
        postfix:  2 5 +

infix > (5.0 / 9.0) * (fahrenheit - 32)
        postfix:  5.0 9.0 / fahrenheit 32 - *

infix > 1 + 2 * 3 ^ 4
        postfix:  1 2 3 4 ^ * +

infix > quit

A few hints that may come in handy when implementing this part of the assignment:

There is a tab character immediately before postfix.
When displaying the postfix notation, there is a space before every operator, variable, and number.
Variable names with more than one letter must be supported. According the syntax for the C Programming Language, variable names are made up of letters and digits; the first character must be a letter. The underscore counts as a letter.
Numbers may include more than one digit. A number may start with a decimal and may not have more than one decimal.
You may wish to work through a few examples in the textbook.
You may wish to create a class to turn the input line into a collection of tokens in an effort to simplify this problem.

To get full credit for this program, you must use your own stack class. If your class does not work, use the standard template library std::stack from #include <stack>. If you do this, you will loose points for the first half of the assignment, but not the second.

Test Bed

The testBed for this assignment is:

testBed cs235/assign02 assignment02.tar

You can also run testBed on the executable:

testBed cs235/assign02 a.out

Of course, you will need to pass testBed to get full credit on the assignment.

Submitting

You will submit this assignment as a pair using the Linux submit command. Please:

Create a TAR file built from the makefile, which will contain five files:
- makefile: Directly from /home/cs235/week02/makefile except with your edits on the comment block.
- stack.h: Your class definition for stack.
- infix.h: Containing the prototype for convertInfixToPostfix() and any other function you may need.
- infix.cpp: Implementation for all the functions and classes necessary for the infix to postfix conversion.
- assignment02.cpp: Unmodified from /home/cs235/week02/assignment02.cpp.
Run the program by hand a few times through all four test cases as well as the infix-to-postfix converter.
Verify your solution with testBed.
Submit your file using the submit command. The submit command will prompt you for your instructor, the class (cs235), and the assignment (assign02). You submit your file with:

submit assignment02.tar

Your program will be graded according to the following rubric:

	Exceptional 100%	Good 90%	Acceptable 70%	Developing 50%	Missing 0%
Stack Interface 20%	The interfaces are perfectly specified with respect to const, pass-by-reference, etc.	assignment02.cpp compiles without modification	All of the methods in Stack match the problem definition	Stack has many of the same interfaces as the problem definition	The public methods in the Stack class do not resemble the problem definition
Stack Implementation 20%	Passes all four Stack testBed tests	Passes three testBed tests	Passes two testBed tests	Passes one testBed test	Program fails to compile or does not pass any testBed tests
Infix to Postfix 30%	The code is elegant and efficient	Passes the Infix to Postfix testBed test	The code essentially works but with minor defects	Elements of the solution are present	The Infix to Postfix code was not attempted
Code Quality 20%	There is no obvious room for improvement	All the principles of encapsulation and modularization are honored	One function is written in a "backwards" way or could be improved	Two or more functions appears "thrown together."	The code appears to be written without any obvious forethought
Style 10%	Great variable names, no errors, great comments	No obvious style errors	A few minor style errors: non-standard spacing, poor variable names, missing comments, etc.	Overly generic variable names, misleading comments, or other gross style errors	No knowledge of the BYU-I code style guidelines were demonstrated

Please make sure to fill out the program header in the makefile with the following information: the name of both programmers, the amount of coding time required by each to complete the assignment, the amount of discussion time (the Pair Programming part), and what was the most difficult part. Failure to do this will result in a loss of 10% on the assignment.

In addition to the above criteria, the following extra credit opportunities exist:

20%: Implement the assembly described in the textbook. The following instructions are to be supported:
- LOD : put the value from a variable in the register
- SET : put a number in the register
- SAV : copy the value in the register to a given variable
- EXP : modify the value in the register by raising it to a given power
- MUL : multiply the value in the register by a given value
- DIV : divide the number in the register by a given value
- MOD : find the remainder of the division of the number in the register with a given value
- ADD : add a given number to the value in the register
- SUB : subtract from the value in the register a given number
With every operator popped off of the stack when evaluating a post-fix expression, you need to add three assembly instructions: one to load the left-hand-side variable, the second to perform the arithmetic with the right-hand-side variable, the third to store the new value in memory (called A where the number will increment by one with each use). Note that there is a tab before each line of output. An example of this is the following:

Enter an infix equation.  Type "quit" when done.
infix > 1 + 2 * 3
        LOD 2
        MUL 3
        SAV A
        LOD 1
        ADD A
        SAV B