Hopefully I can do some good for your open-source project, and I need something to do for the summer semester till I can get into courses that can teach me about binary trees, and other goodies. So far the classes have had me creating algorithms that are just all text and manipulating simple data-structures.... invoice systems and compare-two-words to see if they're anagrams. I need some good old fashioned beefsteak, so send me your problems, help me along the path of learning, and I'll put my learned skills to good use.
No Spam Please
email: falchion-gpx@hotmail.com
-Charlie
Sample code from last problem assignment... prefix to postfix problem.
main
Code: Select all
// Charles Gene Allensworth.
// Date: 4-30-2013.
// For: Chapter 18, Program CPP18_1_10
// Saved as: CPP18_1_10.cpp
// Note: I performed research on wikipedia for help with the algorythm.
// while I did not copy anyone's code, I studied what currently exists.
#include <iostream>
#include <iomanip>
#include <fstream>
#include "mystack.h"
using namespace std;
int getOperandValue(char operand);// determines order of operation
void inFixToPostFix(string& postFixString, char& ch, int opVAL, int topVAL, stackType<char>& charStack, ifstream& inFILE );// processes and outputs infix equasions to postfix equasions.
int main()
{
char ch;// the charactor to analise
stackType<char> operandStack(100); // creates a stack for the character to be analized and compared.
ifstream infile;// infile stream
ofstream outfile;// outfile stream
string output;
int opVal = 0, topVal = 0;
infile.open("inFixData.txt");
if (!infile)
{
cout << "Cannot open the input file. "
<< "Program terminates!" << endl;
return 1;
}
outfile.open("postFixData.txt");
infile >> ch;// get the next character from file
while (infile)// end of file check for reading the file
{
opVal = getOperandValue(ch);// gets the operand presidence
if(!operandStack.isEmptyStack())// finds the presidence of the operator on top of the stack...
topVal = getOperandValue(operandStack.top());
inFixToPostFix(output, ch, opVal, topVal, operandStack, infile);// process data recursively
} //end while
infile.close();
outfile.close();
system("pause");
return 0;
} //end main
int getOperandValue(char operand)
{
int value;
switch (operand)
{
// case ')':
// value = 1;
case '+':
value = 2;
break;
case '-':
value = 2;
break;
case '*':
value = 3;
break;
case '/':
value = 3;
// case '(':
// value = 4;
break;
}
return value;
}
void inFixToPostFix(string& postFixString, char& ch, int opVAL, int topVAL, stackType<char>& charStack, ifstream& inFILE )
{
int subParenth = subParenth;
switch (ch) // checks for operands, and paranthasese, and acts accordingly.
{
case '(':
charStack.push(ch);
// cout << charStack.top() << "...( found...";
break;
case ')':
while(!charStack.isEmptyStack())
{
// cout << charStack.top() << endl;
if(charStack.top() == '(')
{
// cout << "...popping (...";
charStack.pop();// pop and discard from stack
}
else
{
postFixString = postFixString + charStack.top();//output the operand and pop
charStack.pop();//pop the stack
}
}// end while
break;
case '+':
if(opVAL >= topVAL)
charStack.push(ch);
else
{
if(!charStack.isEmptyStack())
{
while(!charStack.isEmptyStack())
{
postFixString = postFixString + charStack.top();
charStack.pop();
}// end while
charStack.push(ch);
}// end if
}// end else
break;
case '-':
if(opVAL >= topVAL)
charStack.push(ch);
else
{
if(!charStack.isEmptyStack())
{
while(!charStack.isEmptyStack())
{
postFixString = postFixString + charStack.top();
charStack.pop();
}// end while
charStack.push(ch);
}// end if
}// end else
break;
case '*': // no exponant symbol '^' so don't bother with more.
if(opVAL >= topVAL)
charStack.push(ch);
else
{
if(!charStack.isEmptyStack())
{
while(!charStack.isEmptyStack())
{
postFixString = postFixString + charStack.top();
charStack.pop();
}// end while
charStack.push(ch);
}// end if
}// end else
break;
case '/':
if(opVAL >= topVAL)
charStack.push(ch);
else
{
if(!charStack.isEmptyStack())
{
while(!charStack.isEmptyStack())
{
postFixString = postFixString + charStack.top();
charStack.pop();
}// end while
charStack.push(ch);
}// end if
}// end else
break;
case ';':// nothing to bother with
postFixString = postFixString;
break;
default:// add token to output... in this case, a string
postFixString = postFixString + ch;
}// end switch
if(ch == ';')
{
cout << postFixString;// outputs output
while(!charStack.isEmptyStack())// outputs stack
{
cout << charStack.top();
charStack.pop();
}
charStack.initializeStack();// resets stack (just in case)
postFixString = "";// resets output
topVAL = 0;// resets top val
cout << endl;// outputs endl for next equasion.
}// end ; check
inFILE >> ch;
}
Code: Select all
//Header file: myStack.h
#ifndef H_StackType
#define H_StackType
#include <iostream>
#include <cassert>
#include "stackADT.h"
using namespace std;
template <class Type>
class stackType: public stackADT<Type>
{
public:
const stackType<Type>& operator=(const stackType<Type>&);
//Overload the assignment operator.
void initializeStack();
//Function to initialize the stack to an empty state.
//Postcondition: stackTop = 0
bool isEmptyStack() const;
//Function to determine whether the stack is empty.
//Postcondition: Returns true if the stack is empty,
// otherwise returns false.
bool isFullStack() const;
//Function to determine whether the stack is full.
//Postcondition: Returns true if the stack is full,
// otherwise returns false.
void push(const Type& newItem);
//Function to add newItem to the stack.
//Precondition: The stack exists and is not full.
//Postcondition: The stack is changed and newItem
// is added to the top of the stack.
Type top() const;
//Function to return the top element of the stack.
//Precondition: The stack exists and is not empty.
//Postcondition: If the stack is empty, the program
// terminates; otherwise, the top element
// of the stack is returned.
void pop();
//Function to remove the top element of the stack.
//Precondition: The stack exists and is not empty.
//Postcondition: The stack is changed and the top
// element is removed from the stack.
stackType(int stackSize = 100);
//constructor
//Create an array of the size stackSize to hold
//the stack elements. The default stack size is 100.
//Postcondition: The variable list contains the base
// address of the array, stackTop = 0, and
// maxStackSize = stackSize.
stackType(const stackType<Type>& otherStack);
//copy constructor
~stackType();
//destructor
//Remove all the elements from the stack.
//Postcondition: The array (list) holding the stack
// elements is deleted.
private:
int maxStackSize; //variable to store the maximum stack size
int stackTop; //variable to point to the top of the stack
Type *list; //pointer to the array that holds the
//stack elements
void copyStack(const stackType<Type>& otherStack);
//Function to make a copy of otherStack.
//Postcondition: A copy of otherStack is created and
// assigned to this stack.
};
template <class Type>
void stackType<Type>::initializeStack()
{
stackTop = 0;
}//end initializeStack
template <class Type>
bool stackType<Type>::isEmptyStack() const
{
return(stackTop == 0);
}//end isEmptyStack
template <class Type>
bool stackType<Type>::isFullStack() const
{
return(stackTop == maxStackSize);
} //end isFullStack
template <class Type>
void stackType<Type>::push(const Type& newItem)
{
if (!isFullStack())
{
list[stackTop] = newItem; //add newItem to the
//top of the stack
stackTop++; //increment stackTop
}
else
cout << "Cannot add to a full stack." << endl;
}//end push
template <class Type>
Type stackType<Type>::top() const
{
assert(stackTop != 0); //if stack is empty,
//terminate the program
return list[stackTop - 1]; //return the element of the
//stack indicated by
//stackTop - 1
}//end top
template <class Type>
void stackType<Type>::pop()
{
if (!isEmptyStack())
stackTop--; //decrement stackTop
else
cout << "Cannot remove from an empty stack." << endl;
}//end pop
template <class Type>
stackType<Type>::stackType(int stackSize)
{
if (stackSize <= 0)
{
cout << "Size of the array to hold the stack must "
<< "be positive." << endl;
cout << "Creating an array of size 100." << endl;
maxStackSize = 100;
}
else
maxStackSize = stackSize; //set the stack size to
//the value specified by
//the parameter stackSize
stackTop = 0; //set stackTop to 0
list = new Type[maxStackSize]; //create the array to
//hold the stack elements
}//end constructor
template <class Type>
stackType<Type>::~stackType() //destructor
{
delete [] list; //deallocate the memory occupied
//by the array
}//end destructor
template <class Type>
void stackType<Type>::copyStack(const stackType<Type>& otherStack)
{
delete [] list;
maxStackSize = otherStack.maxStackSize;
stackTop = otherStack.stackTop;
list = new Type[maxStackSize];
//copy otherStack into this stack
for (int j = 0; j < stackTop; j++)
list[j] = otherStack.list[j];
} //end copyStack
template <class Type>
stackType<Type>::stackType(const stackType<Type>& otherStack)
{
list = NULL;
copyStack(otherStack);
}//end copy constructor
template <class Type>
const stackType<Type>& stackType<Type>::operator=
(const stackType<Type>& otherStack)
{
if (this != &otherStack) //avoid self-copy
copyStack(otherStack);
return *this;
} //end operator=
#endif
Code: Select all
//Header file: stackADT.h
#ifndef H_StackADT
#define H_StackADT
template <class Type>
class stackADT
{
public:
virtual void initializeStack() = 0;
//Method to initialize the stack to an empty state.
//Postcondition: Stack is empty
virtual bool isEmptyStack() const = 0;
//Function to determine whether the stack is empty.
//Postcondition: Returns true if the stack is empty,
// otherwise returns false.
virtual bool isFullStack() const = 0;
//Function to determine whether the stack is full.
//Postcondition: Returns true if the stack is full,
// otherwise returns false.
virtual void push(const Type& newItem) = 0;
//Function to add newItem to the stack.
//Precondition: The stack exists and is not full.
//Postcondition: The stack is changed and newItem
// is added to the top of the stack.
virtual Type top() const = 0;
//Function to return the top element of the stack.
//Precondition: The stack exists and is not empty.
//Postcondition: If the stack is empty, the program
// terminates; otherwise, the top element
// of the stack is returned.
virtual void pop() = 0;
//Function to remove the top element of the stack.
//Precondition: The stack exists and is not empty.
//Postcondition: The stack is changed and the top
// element is removed from the stack.
};
#endif
