🔒 Locked

University Programming Projects

Started by Chad Smith Nov 29, 2012 at 7:47 AM 8 replies 1.8k views

Original Post

Nov 29, 2012 at 7:47 AM

Hey everyone, this fall semester I had a couple of University Programming Projects for the Computer Science class I was in. I was wonder if I could get some advice on the code I wrote for them. The projects are completely finished and have been completely graded. I will start with just the second project we had (The first one was pretty easy and I did post the code to it here a couple months ago).

The second project we had was to create our own bare bones basic stack class and use that to convert basic infix to postix
Example:
[source lang="cpp"]5+5 -> 55+

or

5+5-3 -> 55+3-[/source]
we did not have to have it be able to use parenthesis.

The requirements were to create our own stack class (bare bones basic) and we could not use the std::stack class in STL. The user would just have to type in convert, a basic infix expression and then convert. We had to do some basic error checking (like the user didn't just type in "5/" though we were allowed to assume some things (though I did try to check for only integer input)

I am wondering if some people could take a look at the code and see how it is. What are some things you would improve? Advice? Comments? Suggestions? I will take any input!
Also the grade I made on this was a 99, with one point being taken off because most of the code was in main.cpp and didn't split it into multiple functions. Though a 99 was the lowest grade I made out of all my other programming assignments with me making 100's on the rest (will post later on after input with this one, to get input on those). The Teacher Assistant seemed to like my solutions a little more than others though it seemed, so I was glad to hear that.

NOTE: I wrote the static CommandProcessor class to use on all my projects to try to help me with the command input

EDIT: I did have more of my functions in the Stack class returning NULL if they failed or something like that, though when I had to upload it the command line compiler that the servers used (a linux compiler) did not like me using NULL in those places, so I just replaced those with a return ' ' instead. I don't seem to be the biggest fan of the compiler used on the servers, but oh well. Visual Studio has zero problems with my code with me using NULL.

CommandProcessor.h
[source lang="cpp"]//CommandProcessor Header File
//Class for CommandProcessor
//Static Class to for processing commands and arguments

//only include once in the compiling/linking process
#ifndef COMMANDPROCESSOR_H
#define COMMANDPROCESSOR_H

//string for working with C++ strings
#include

class CommandProcessor
{
public:
//ExtractCommand will extract the command that was entered
static std::string ExtractCommand(std::string& line);
//ExtractArgument will extract the argument that was entered in the command
static std::string ExtractArgument(std::string& line);
//CheckArgument will make sure their is an argument in the command
static bool CheckArgument(std::string& line);
};

#endif[/source]
CommandProcessor.cpp
[source lang="cpp"]//CommandProcessor Class Definition Source File
//Definition for Static Class CommandProcessor

//include the header file for the class
#include "CommandProcessor.h"

//start the class definitions
std::string CommandProcessor::ExtractCommand(std::string& line)
{
//hold the index/location of the space in the command
int index=line.find(" ");

//if the string does not contain a space it will return string::npos
if(index==std::string::npos)
{
//return the entire line
//no arguments found
return line;
}
else
{
//return the command up until the arguments start
return line.substr(0, index);
}
}

std::string CommandProcessor::ExtractArgument(std::string& line)
{
//hold the index/location of the space in a line
int index=line.find(" ");

//if the string does not contain a space, return an empty string
if(index==std::string::npos)
{
return "";
}

else
{
//return a substring
//from one character after the space to the end of the line
//length-index-1 to take account for the characters we don't need and the one space we moved over
return line.substr(index+1, line.length()-index-1);
}
}

//CheckArgument will make sure that an argument is present in the command
//returns true if the argument was present
//returns falsee if the argument was not present
bool CommandProcessor::CheckArgument(std::string& line)
{
//if argument is not an empty string then we consider it a valid argument
//will keep program specific argument checking outside this class for code reusability
if(line=="")
{
return false;
}
//the argument was not a empty string, consder it valid right now and return true
return true;
}[/source]

Node.h
[source lang="cpp"]//Node.h
//Header file for the Node Struct
//Declares the Node Struct

#ifndef NODE_H
#define NODE_H

//Node Struct
//A node simply is a datatype, build as a struct
struct Node
{
//the data in the node will hold both operators and numbers.
int data;

//point to the next node in the stack
Node* nextNode;
};

#endif[/source]
Stack.h
[source lang="cpp"]//Stack.h
//Header file to declare the Stack Class

#ifndef STACK_H
#define STACK_H

//include iostream so we can compare things to NULL
#include
//Stack will use the Node datatype
#include "Node.h"

//start the clas declaration of the List based Stack
class Stack
{
private:
//hold a pointer to the first Node in the stack
Node* firstNode;
//hold the size of the current stack
int size;

public:
//Public methods for working generally with stacks
//Public default constructor
Stack();

//Push will put some data onto the Stack
void Push(char data);

//Pop will remove the first element or Node
char Pop();

//prints out the data of the first node
char Top();
};

#endif[/source]

Stack.cpp
[source lang="cpp"]//Stack class definition source file
//Define what the Stack class is

//include the Stack header file
#include "Stack.h"

Stack::Stack()
{
//the first pointer is null or empty at the start
firstNode=NULL;
size=0;
}

//Push Method
//Takes in a char datatype and pushes the data onto the top of the Stack
void Stack::Push(char data)
{
//create a temporary Node at first
Node* tempNode=new Node();
//store the data needed into the temporary node
tempNode->data=data;

//before we push make sure that the first node isn't null
if(firstNode!=NULL)
{
//the first node isn't null
//the next node in the list now holds the first node
tempNode->nextNode=firstNode;
//the first node in the list now holds the tempNode, or the newNode that needs to be entered
firstNode=tempNode;
}

//if anything else then we now know the firstNode is null
else
{
//since it was empty already we can simply add the new node the list
//be setting the firstNode equal to the new tempNode
firstNode=tempNode;
tempNode->nextNode=NULL;
}

//increase the size
size++;
}

char Stack::Pop()
{
char dataReturn=firstNode->data;
//check to make sure the size of the stack is not empty
//since we increased the size evertime we added a new node, we can just check the size
if(size<=0)
{
//we can't pop anything off the stack if it is empty
return ' ';
}

//create a temporary node to hold the first node
Node* tempNode=firstNode;
//the first node is now the node that was next
firstNode=firstNode->nextNode;
delete tempNode;
size--;
return dataReturn;
}

//returns the char data in the top node on the stack
//will return null if the stack is empty and the top of the stack is null
char Stack::Top()
{
if(firstNode==NULL)
{
return ' ';
}
return firstNode->data;
}[/source]
and finally Main.cpp
[source lang="cpp"]//Program2
//Infix to Postfix
//Main.cpp
//Main Source file for Program2

//iostream for console input and output
#include
//include the static class CommandProcessor
#include "CommandProcessor.h"
//Include Stack for a stack
#include "Stack.h"

//Function Prototypes
//Check to see if the string passed in is valid argument
bool ValidArgument(std::string& input);
//Do the conversion of infix to postfix in this function
void Convert(std::string& input);
//Checks to see if the characters in the arguments are numbers or operators
bool IsNumber(char input);
//Checks to see if the given operator is equal or lower to another operator
bool IsLowerOperator(char readingOperator, char stackOperator);

//main entry point
int main()
{
//the beginning text that gets added on to just about everything
const std::string BEGINNING_TEXT= "infix_to_postfix> ";
//hold the input
std::string input;
//hold the command input string
std::string commandInput="";
//hold the argument input string
std::string argumentInput="";
//boolean variable to know when the program should keep running or not
//running will be true when we need to keep running. false when we should quit
bool running=true;

while(running)
{
std::cout< std::getline(std::cin, input);
commandInput=CommandProcessor::ExtractCommand(input);
argumentInput=CommandProcessor::ExtractArgument(input);

//if we need to convert
if(commandInput=="convert")
{
if(ValidArgument(argumentInput))
{
Convert(argumentInput);
}
else
{
std::cout<<"Error! Not a valid argument!"< }
}

//command was to quit
else if(commandInput=="quit")
{
running=false;
}

//command was not reconized
else
{
std::cout<<"Error! Command not reconized!"< }
}

//return 0 for no error
return 0;
}

bool ValidArgument(std::string& input)
{
//boolean variable to keep track weather or not the input was valid
bool validInput=false;
if(CommandProcessor::CheckArgument(input))
{
//argument was not empty
//loop through the string to make sure it is a valid postfix
//only numbers and operators
for(unsigned int i=0; i {
//if the postfix argument was not a number or a operator set validInput to false;
if(!(input=='0'||input=='1'||input=='2'||input=='3'||input=='4'||input=='5'||input=='6'||input=='7'||input=='8'||input=='9' //check for numbers
||input=='+'||input=='-'||input=='*'||input=='/')) //check for all the operators
{
validInput=false;
//break out of the loop
break;
}
else
{
validInput=true;
}
}
}
//we now know that the argument was empty
else
{
validInput=false;
}
return validInput;
}

//Takes in a input string and converts it from Infix to Postfix
void Convert(std::string& input)
{
std::string output;
//a stack will hold the operators
Stack postFix;
//loop through the input string
for(unsigned int i=0; i {
//check to see if the character is a number or operator
if(IsNumber(input))
{
//it is a number, it goes straight to the output
output+=input;
}
else
{
//first check to see if there was anything on the stack
//if not then push the operator onto the stack
if(postFix.Top()==' ')
{
postFix.Push(input);
}

//if the operator is of lower or equal precedence then pop the operator on top and append it to the output until the top element is no longer higher precedence
else if(IsLowerOperator(input, postFix.Top()))
{
do
{
output+=postFix.Pop();
}
while(IsLowerOperator(input, postFix.Top()));
postFix.Push(input);
}
//the operator is of higher precendence, just push it onto the stack
else
{
postFix.Push(input);
}
}
}
//we are outside the for loop, all the elements are read, pop all the elements
//keep "popping" until the top element is NULL
while(postFix.Top()!=' ')
{
output+=postFix.Pop();
}
std::cout< }

//Returns true if the input character is a number
//returns false if it is a operator
bool IsNumber(char input)
{
//if the input is an operator return false
if(input=='*'||input=='/'||input=='-'||input=='+')
{
//number is an operator return false
return false;
}
//return true because we now know it has to be a number
//this function would not be called if an alpha character was in the string
return true;
}

//Returns true if the first operator is lower or equal precedence to the one on top of the stack
//returns false if it is not
bool IsLowerOperator(char readingOperator, char stackOperator)
{
//is the value of equal or lower precedence
if((readingOperator=='-'&&stackOperator=='+')||(readingOperator=='-'&&stackOperator=='-')||(readingOperator=='+'&&stackOperator=='-')||(readingOperator=='+'&&stackOperator=='+')
||(readingOperator=='-'&&stackOperator=='*')||(readingOperator=='-'&&stackOperator=='/')||(readingOperator=='+'&&stackOperator=='*')||(readingOperator=='+'&&stackOperator=='/')
||(readingOperator=='*'&&stackOperator=='*')||(readingOperator=='*'&&stackOperator=='/')||(readingOperator=='/'&&stackOperator=='/')||(readingOperator=='/'&&stackOperator=='*'))
{
//return true as the operator was of equal or lower precendence
return true;
}

//it is not lower or equal value, return false
else
{
return false;
}
}[/source]

PwFClockWise

Nov 30, 2012 at 11:56 AM

I'm also studying programming at the university and the way we learned is to never have too much in main. When I make my projects main will include an interface class that will have all the functions that your main class currently has. I don't know if this is better with aspect to efficiency, but it sure makes the code a bit nicer to look at in my opinion.

So It would be like main only created an instance of application and application has the loop.

Hope I was of any help ^^

Stroppy Katamari

Nov 30, 2012 at 2:37 PM

Was only std::stack banned, or were you banned from using all std containers? A stack implementation using std::vector would be about this big (not tested, might have typos...)

class myIntStack {
 std::vector<int> v;
 public:
 bool empty() { return v.empty(); }
 void push(int i) { v.push_back(i); }
 void pop() { v.pop_back(); }
 int top() { return v.back(); }
 }

If you were banned from using containers, did they specifically require a linked list to implement a stack of ints? It's a terrible choice for that purpose. A tiny vector implementation would make sense instead.

Too many comments make the code less readable. This code has maybe 20x more comments than is actually useful, but I recognize that is also possibly due to requirements, or anticipation of requirements.

There is one >10-line block in the push code where you test for a condition, then do an equivalent thing in either case, where all the lines except two should just be removed.

I wouldn't split tiny code like this into multiple files unless the exercise specifically asked for me to do that, because there's no actual point in doing so.

The code that checks operator precedence is a mess, very hard to see if it has bugs or not. Instead, you could use something like a map of operators to precedence values, and the comparison would just look like "precedenceMap['-'] < precedenceMap['*']".

Don't use "NULL" in C++. Long story short: it's not a language feature, it's old and bad C stuff that is only defined in some standard libraries, and may have different definitions in different places. Use the value 0 instead. If your compiler is new enough to support it, always use "nullptr" instead of 0 to indicate null pointers.

Don't return 0 from a function returning generic ints to indicate error. That would mean the function can't return actual 0-values, and therefore your int stack doesn't support containing 0's. The correct way is to offer an empty() function to the user of the stack which they can use to check for emptiness before they try reading or popping the stack. Additionally, you can use an assert() or throw an exception in the case the user of the stack tries to read/pop empty stack.

Chad Smith

Nov 30, 2012 at 3:44 PM

Was only std::stack banned, or were you banned from using all std containers? A stack implementation using std::vector would be about this big (not tested, might have typos...)
class myIntStack { std::vector<int> v; public: bool empty() { return v.empty(); } void push(int i) { v.push_back(i); } void pop() { v.pop_back(); } int top() { return v.back(); } }

If you were banned from using containers, did they specifically require a linked list to implement a stack of ints? It's a terrible choice for that purpose. A tiny vector implementation would make sense instead.

Yes we were banned from using any premade containers and the program requirements required us to create a linked list of int's. The point of the project was really too see if we understood the theory behind a linked list stack. Though we did study array based stacks (which I would had used a vector for that if that would had been allowed).

Too many comments make the code less readable. This code has maybe 20x more comments than is actually useful, but I recognize that is also possibly due to requirements, or anticipation of requirements.
[/quote]
Yes, the requirements were to use, lets say, a lot of comments. What was preached to us at all times was "make sure you comment your code! When in doubt comment it!" Sadly that it was the instructor believes so I didn't want points taken off for it. I felt since they preached commenting your code so much that it'd be better to over comment in this certain situation as it would be weird to take off points after they preached to us how much they like comments.

Pointers were new to a lot of people in the class (even though I understand the just of them and can use them them though still struggle every now and then) so a lot of people ran into pointer problems before so she wanted us to comment our code to make sure we always knew what our pointers were doing.

There is one >10-line block in the push code where you test for a condition, then do an equivalent thing in either case, where all the lines except two should just be removed.
[/quote]
Thanks , I'll take a look at that.

I wouldn't split tiny code like this into multiple files unless the exercise specifically asked for me to do that, because there's no actual point in doing so.
[/quote]

The code that checks operator precedence is a mess, very hard to see if it has bugs or not. Instead, you could use something like a map of operators to precedence values, and the comparison would just look like "precedenceMap['-'] < precedenceMap['*']".
[/quote]
! That was my original idea. I asked my professor if it would be ok to use a std::map just for this and she approved it but she said to make sure I made plenty of notes in my code for the TA to know that she did approve it, so points wasn't taken off. I didn't want to take the chance so I just programmed it like that really fast. Point taken though and I really hated that code I wrote there.

Don't use "NULL" in C++. Long story short: it's not a language feature, it's old and bad C stuff that is only defined in some standard libraries, and may have different definitions in different places. Use the value 0 instead. If your compiler is new enough to support it, always use "nullptr" instead of 0 to indicate null pointers.
[/quote]
I'll look into it. Could be why the linux compiler did not like my NULL that I would use in some places to return. Visual Studio 2012 didn't mind or spit out any warnings to me. I'm not sure if the linux compiler on the severs will support nullptr or not. They say it is 'updated" though after talking to some people in the Computer Science department I am not sure what all it does support or how up to date it really is.

Don't return 0 from a function returning generic ints to indicate error. That would mean the function can't return actual 0-values, and therefore your int stack doesn't support containing 0's. The correct way is to offer an empty() function to the user of the stack which they can use to check for emptiness before they try reading or popping the stack. Additionally, you can use an assert() or throw an exception in the case the user of the stack tries to read/pop empty stack.
[/quote]

Point taken! Will look into modifying my code for that.

Thanks for all the input! I'll look into making changes to clean the code up. I'll post program 3 up here later, though a lot of your comments to move onto to program also because of requirements. Just to give a heads up, Program 3 asked us to create a basic Binary Search Tree. Again no STL libraries or containers were allowed to be used.

Stroppy Katamari

Nov 30, 2012 at 5:10 PM

I'll look into it. Could be why the linux compiler did not like my NULL that I would use in some places to return. Visual Studio 2012 didn't mind or spit out any warnings to me. I'm not sure if the linux compiler on the severs will support nullptr or not. They say it is 'updated" though after talking to some people in the Computer Science department I am not sure what all it does support or how up to date it really is.

No matter what NULL happens to be defined as in a particular environment, it is intended to represent a null pointer. It's definitely a conceptual mistake on your part to assign NULL to an int, so a compiler which complains about it is doing you a favor. (But again, don't use NULL at all and you are in the clear...)

I took another look at the code and noticed that your stack implementation is completely broken. It always leaks all of its memory if not manually emptied by the user. It will also explode if copied by the user. Writing the stack properly would require writing a destructor, and then either writing a copy constructor and assignment operator, or deleting them to prevent the user from trying to copy or assign.

Frankly, I don't understand how they could fail to comment on the problems of the stack if that was the point of the exercise, and how they could award full points. I'm a teaching assistant for a C course. We demand all exercise answers to be free of compiler errors and warnings (straight fail if there's even a warning) and we massively deduct points for any memory leaks or illegal memory accesses which happen when our automated tester runs a number of test cases on the code. This is how it should be with C and C++. Absent that (bare minimum!) standard of safety and cleanliness with smaller artificial pieces of code, the students might get the illusion that they can write code, but would be completely useless in a real-world project because neither they themselves or anyone else could trust the code they have written.

Stroppy Katamari

Nov 30, 2012 at 6:17 PM

BTW, I don't want to discourage you. Some of this stuff is hard, you are doing a lot of things right, and you are active in finding out how to fix the rest. That's all anyone can ask for.

I'm more critical towards instructors. Most C and C++ instruction suuucks. You need to be aware of that.

Chad Smith

Nov 30, 2012 at 7:17 PM

I took another look at the code and noticed that your stack implementation is completely broken. It always leaks all of its memory if not manually emptied by the user. It will also explode if copied by the user. Writing the stack properly would require writing a destructor, and then either writing a copy constructor and assignment operator, or deleting them to prevent the user from trying to copy or assign.

Frankly, I don't understand how they could fail to comment on the problems of the stack if that was the point of the exercise, and how they could award full points. I'm a teaching assistant for a C course. We demand all exercise answers to be free of compiler errors and warnings (straight fail if there's even a warning) and we massively deduct points for any memory leaks or illegal memory accesses which happen when our automated tester runs a number of test cases on the code. This is how it should be with C and C++. Absent that (bare minimum!) standard of safety and cleanliness with smaller artificial pieces of code, the students might get the illusion that they can write code, but would be completely useless in a real-world project because neither they themselves or anyone else could trust the code they have written.

In reply to your last post: I am not at all discouraged by what you're saying. I asked for input. I can take any positive or negative input. Even if you would had said my code was the worst code in existence In my mind I can not be discouraged by that. I asked for opinions for anyone and welcome any input that anyone here can give me. Same reason why I don't believe developers or designers should get mad at reviewers if they didn't like their game. You put it out in the public it's going to be picked apart.

Now to comment on the quoted portion:
You're exactly right that my stack really is broken. No doubt that if I were to use this code in a more advanced project then that stack class would fail. If I were creating the stack class for a more professional use I would first start of by using templates to have the stack use more than just integers. Then I would overload the assignment operator, create a copy constructor, and create a destructor for it. No doubt it would leak memory if the user didn't use it properly.

Though while I did state the bug purpose was to know how to create a linked list stack, this is more like an introduction to data structures type of class. It's the class directly after well the first two programming courses a University would offer. Matter of fact most people in the class had zero ideas of pointers like this as most of them only had Java experience from other community colleges. So they also had almost zero idea of what a copy constructor or operator overloading actually is. Matter of fact they just introduced those concepts in the class a week ago. Though I myself had known of those concepts and know how to create and those things. Matter of fact templates were just discussed last lecture.

So I guess they only wanted to see if we understood the basic theory of a stack and could turn the theory of pushing and popping items on and off the stack into actual code. Though for practice I was going to work on making this project better and edit my code to take in any advice I have taken and also attempt to redo my stack class to make it less broken and to be able to get it where it was more user friendly as if some other programmer was going to be using it.

Stroppy Katamari

Nov 30, 2012 at 11:00 PM

Though while I did state the bug purpose was to know how to create a linked list stack, this is more like an introduction to data structures type of class. It's the class directly after well the first two programming courses a University would offer. Matter of fact most people in the class had zero ideas of pointers like this as most of them only had Java experience from other community colleges. So they also had almost zero idea of what a copy constructor or operator overloading actually is. Matter of fact they just introduced those concepts in the class a week ago. Though I myself had known of those concepts and know how to create and those things. Matter of fact templates were just discussed last lecture.

Any way I look at it, that assignment and its grading fails to make sense. If they expect you to allocate dynamic memory, they absolutely should expect you to release that memory as well; those go hand in hand. And if they want you to build a data structure, but they haven't covered stuff like constructors, destructors and assignment well enough to build an encapsulated type (class) then they could simply have you build that data structure without using a class.

It is not really a "data structures" course either if they teach stuff like templates; that's language specific stuff.

Chad Smith

Dec 1, 2012 at 2:48 AM

It is not really a "data structures" course either if they teach stuff like templates; that's language specific stuff.

It's really not a Data Structures class at all it just covers some very basics one. The course title is actually "Computing Foundations I." It's more theory than anything in the class. Language Specifics are taught mostly since most people are having to switch from Java or C to C++.

Though I feel I did release my memory? I will agree it is not professional nor would it work if you tried to use it some other way though if I pop something off the stack I do delete it, that would be me deleting my memory would it not? But again I know that this stack is not bullet proof nor even correct on the way stacks are used. Though for the way the stack is being used in the project I don't see what is bad. I pop when I need to which deletes and I push when I need to.

Chad Smith

Dec 1, 2012 at 3:00 AM

Also to note: I'm not trying to argue with you. Just want to make sure I do understand correctly.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.