C++ help wanted
tuesdaywith
4CSC210_Lab4_Specs.docCSC210 (C++ OOP) Name #1: _______________________________ Name #2: _________________________________
Signature: ______________________________ Signature: _________________________________
Hours worked: __________________________ Hours worked: _____________________________
(signatures indicate that you have neither given nor received aid on this lab, hours indicate share of work)
Lab 4: In-Fix to Post-Fix Conversion using a Stack Class (done in pairs for a combined Lab Project)
Due Date: April 30, 2018 (afternoon class)
April 24, 2018 (evening class)
Purpose: To utilize a templated List class (the same one used in Lab 3) and to transform it into a stack class. Use your group’s new stack implementation to call class functions such as push and pop to help a client to write a conversion function from the infix notation (normally used in algebra) to a postfix expression (commonly referred to as Reverse Polish Notation (RPN). A good infix example is: (a + b) * c to a postfix expression a b + c * A secondary purpose for this lab is that it will become a capstone experience for many of the tasks done previously in this course. A student’s time and education are both valuable. Students interests are better served doing this lab project in pairs. Overall, the amount of work required in this lab, compared to other labs is quite excessive. I’ll give only minimum help. Therefore, given the huge preparation for this lab, the benefits of working in pairs outweigh any student’s solo efforts. The benefits of time management and workload are readily apparent when considering your preparation, documentation, formatting the report, as well as the time spent on two chapters of homework. This should be a win-win experience for both students, as each will learn valuable life-long lessons about programming in a team environment sharing this high workload situation.
Problem:
1. Programming exercise Chapter 18, exercise #10 on page 1292 of the Malik textbook (Seventh Edition) describes
only part of what this lab will demonstrate. Please ignore the directions that have you, “Design a class that stores the infix and postfix strings.” Also, ignore the next three bullets suggesting these should be class functions.
2. Instead your program will use similar client functions (these are suggestions) for the conversion such as:
string convertToPostFix(string &); and a bool precedence(char, char); function may also be useful in the client’s code to determine an operator’s higher precedence in this conversion. Of course, you’re not bound by these client functions. You may use these or not. The choice is up to you and your partner.
3. Your program will each entire line of data from a text file as one complete infix expression. You may use
the C++ built in getline(ifstream, string) technique. This could be within a function such as process(). Again, this is up to you.
4. The client code will create a linked list of characters using List<char> stack, call function(s) as necessary using client functions and List class functions to help convert this infix expression into a postfix expression. Your List class must implement all function in List.h (see the reverse side).
5. The internet is filled with a plethora of examples on how to do this. The challenge for you will be to implement any of these algorithms to handle processing single characters, whether these are letters, numbers, parenthesis symbols, or valid combinations. The book mentions this valuable suggestion, “You may assume that the expressions you will process are error-free”. I agree. Also, I will assist you in this project much less than in the previous labs. You must use my infix input data file on Y: drive or my website AND attempt to produce the exact output shown in my example with all fine details, including spaces between each operand and operator. The closer you get to the exact output shown, the higher your overall score will be. You can do this, especially in a group of two students, using four eyes ! (note: there are 63 hyphens in the first line of the report)
6. An algorithm will be discussed in class however, it may not be the exact algorithm that you wish to use.
7. Prepare a pseudocode to document the steps in the conversion process. Submit this as one documentation.
Input: Download the non-error infix input file from Y: or my website. This will be the only file used to grade your work.
Output: (see the next few pages) Echo print the output report to both the console and to the output file. Exact formatting
is very important, therefore, follow as closely to what I have shown in my example to minimize any deductions. Print hard copies listed below (one set per group) to turn in, and one student should email these same files to
with subject: CSC 210 Lab4
Checklist:
Source files with many copious comments: 1) Lab4Main.cpp, 2) List.cpp, 3) List.h, 4) inFixData.txt,
5) output.txt (report file), 6) pseudocode of your converter function (in Word), and 7) Chapter 18 Homework: pp.1282 - 1287: 1 through 20. (only one copy of each file is necessary for a group submission). Staple the hard copies of these in the order listed below this signed specification sheet. I will adjust grades based on hours.
// List.h (Header specifications for Lab 4's implementation of a stack class)
// This is a group project. You must implement all files in this specification
// for full credit. Do not create class functions not listed in this specification.
// For example, you should modify Lab 3 functions such as insertFirst to be used as
// push, used in a typical stack implementation. Others may be modified as necessary.
// Optionally, implementation files not mentioned in this header may be eliminated.
#ifndef H_List
#define H_List
#include <iostream>
#include <cassert>
// definition of the linked list node used
template <class Type>
struct nodeType
{
Type info;
nodeType<Type> *link;
};
// class definition starts here
template <class Type>
class List
{
public:
List(); // default constructor
List(const List<Type>& otherList); // copy constructor
~List(); // destructor
const List<Type>& operator= (const List<Type> &); // overload assignment operator.
void initializeList(); // list cleared to an empty state.
bool isEmptyList() const; // determines if list is empty.
int length() const; // returns number of records in list.
Type top() const; // returns first element in list.
void pop(); // deletes top element in the stack.
void push(const Type& ); // inserts newItem in list beginning.
private:
int count; // number of records in list
nodeType<Type> *first; // pointer to first node of list
nodeType<Type> *last; // pointer to last node of list
void copyList(const List<Type>& ); // makes a copy of the list.
void destroyList(); // deletes all the nodes from list.
};
#endif
(this is the Y: input file you must use in this lab)
a + b
a + b * c
a * b + c
a - b + (w * p)
(a - b) * (c + d)
a - b * c - d
(a + b) * c + d
(a + b + c) * d
(a + b) / (c * d)
(A + B) / (C * D)
(a + b) * (c - d / e) + f
(a + b + c) * d + e / (f - g)
A + B * (C + D) - E / F * G + H
(B + C) * (E - F) - G / (H - I)
(B + C) * (E - F) - (G / H - I)
x * (y + z) - (w + t)
(x + y) / (z - w) * t
((x - y) + (z - w) / t) * u
x - y / (z + w) * t / (v - s)
(a + (b * c - (d / e)))
(g * f / e) * (a - b) / (w * h)
(2 + 3 + 4) / (7 - 5 - 4)
2 + 3 + 4 + 5 + 6 + 7 + 8
(2 + 3 / 4) * (8 - b) + (8 * g)
2 + 3 / 4 * a - b + 8 * g
---------------------------------------------------------------
T H E I N F I X T O P O S T F I X C O N V E R T E R
---------------------------------------------------------------
Written by Jeff Goldstein
A L G E B R A I C I N F I X R P N P O S T F I X
------------------------------- -----------------------------
a + b a b +
a + b * c a b c * +
a * b + c a b * c +
a - b + (w * p) a b - w p * +
(a - b) * (c + d) a b - c d + *
a - b * c - d a b c * - d -
(a + b) * c + d a b + c * d +
(a + b + c) * d a b + c + d *
(a + b) / (c * d) a b + c d * /
(A + B) / (C * D) A B + C D * /
(a + b) * (c - d / e) + f a b + c d e / - * f +
(a + b + c) * d + e / (f - g) a b + c + d * e f g - / +
A + B * (C + D) - E / F * G + H A B C D + * + E F / G * - H +
(B + C) * (E - F) - G / (H - I) B C + E F - * G H I - / -
(B + C) * (E - F) - (G / H - I) B C + E F - * G H / I - -
x * (y + z) - (w + t) x y z + * w t + -
(x + y) / (z - w) * t x y + z w - / t *
((x - y) + (z - w) / t) * u x y - z w - t / + u *
x - y / (z + w) * t / (v - s) x y z w + / t * v s - / -
(a + (b * c - (d / e))) a b c * d e / - +
(g * f / e) * (a - b) / (w * h) g f * e / a b - * w h * /
(2 + 3 + 4) / (7 - 5 - 4) 2 3 + 4 + 7 5 - 4 - /
2 + 3 + 4 + 5 + 6 + 7 + 8 2 3 + 4 + 5 + 6 + 7 + 8 +
(2 + 3 / 4) * (8 - b) + (8 * g) 2 3 4 / + 8 b - * 8 g * +
2 + 3 / 4 * a - b + 8 * g 2 3 4 / a * + b - 8 g * +
