C++ question NOTE!!!! THIS HAS TO BE CODED IN A GCC COMPILER AND NOT VISUAL STUD

Question

C++ question

NOTE!!!! THIS HAS TO BE CODED IN A GCC COMPILER AND NOT VISUAL STUDIO!!! A VISUAL STUDIO CPP FILE WILL NOT DO ME ANY GOOD!

COP 1335C Extra Credit Project 2 25 points Submission instructions: Save your program as message.cpp in your projects/extracredit folder. This project is an exercise in the use of stacks for encrypting messages. The goal of the program is to encode input messages using the following encryption strategy: The message sender inputs a four letter word, C C C C, and another four letter word, X X X X. The message sender then inputs the message to be sent. The program scans the message one character at a time and each character is pushed in the stack until either the scanned character is in the word C C C C or the end of message is encountered. When the scanned character is one of the characters in C C C C, print that character and continue to print and pop the characters at the top of the stack until either the stack is empty or the character at the top of the stack is one of the characters in X X X X. When the end of the message is encountered, print the character at the top of the stack and continue to pop and print the stack top until the stack is empty. Well, all I can say to you is "GOOD" "LUCK", it "SOUNDS SIMPLE TO ME", or as your program would say, "OSDNOT EEM LPMIS SU". Grading Rubric: Accuracy (15) Use of stacks Efficiency: (10) Use of functions Use of loops

AGAIN!!! PLEASE PLEASE PLEASE CODE THIS WITH A LINUX GCC COMPILER!!!!!

Explanation / Answer

How to efficiently implement stack:

Create a data structure kStacks that represents k stacks. Implementation of kStacks should use only one array, i.e., k stacks should use the same array for storing elements. Following functions must be supported by kStacks.

push(int x, int sn) –> pushes x to stack number ‘sn’ where sn is from 0 to k-1
pop(int sn) –> pops an element from stack number ‘sn’ where sn is from 0 to k-1

Method 1 (Divide the array in slots of size n/k)
A simple way to implement k stacks is to divide the array in k slots of size n/k each, and fix the slots for different stacks, i.e., use arr[0] to arr[n/k-1] for first stack, and arr[n/k] to arr[2n/k-1] for stack2 where arr[] is the array to be used to implement two stacks and size of array be n.

The problem with this method is inefficient use of array space. A stack push operation may result in stack overflow even if there is space available in arr[]. For example, say the k is 2 and array size (n) is 6 and we push 3 elements to first and do not push anything to second second stack. When we push 4th element to first, there will be overflow even if we have space for 3 more elements in array.

Method 2 (A space efficient implementation)
The idea is to use two extra arrays for efficient implementation of k stacks in an array. This may not make much sense for integer stacks, but stack items can be large for example stacks of employees, students, etc where every item is of hundreds of bytes. For such large stacks, the extra space used is comparatively very less as we use two integer arrays as extra space.

Following are the two extra arrays are used:
1) top[]: This is of size k and stores indexes of top elements in all stacks.
2) next[]: This is of size n and stores indexes of next item for the items in array arr[]. Here arr[] is actual array that stores k stacks.
Together with k stacks, a stack of free slots in arr[] is also maintained. The top of this stack is stored in a variable ‘free’.

All entries in top[] are initialized as -1 to indicate that all stacks are empty. All entries next[i] are initialized as i+1 because all slots are free initially and pointing to next slot. Top of free stack, ‘free’ is initialized as 0

#ifndef STACK_H
#define STACK_H
#include <iostream>
using namespace std;

class Stack
{
private:
   char *stackArray;
   int stackSize;
   int top;

public:
   int getTop();
   Stack( int );
   ~Stack()
   {
       delete[]stackArray;
   }

   void push( char );
   char pop();
   bool isFull();
   bool isEmpty();
}; // end of Stack class

// constructor
Stack::Stack( int size )
{
   stackArray = new char[size];
   stackSize = size;
   top = -1;
}

// function to push integer onto stack
void Stack::push( char letter )
{
   if ( !isFull() )
   {
       top++;
       stackArray[top] = letter;
   }
   else
   {
       cout << "The stack is full." << endl;
   }
}

// function to pop the top value off the stack and copies it into the variables pass as an argument
char Stack::pop()
{
   char letter;
   if ( !isEmpty() )
   {
       letter = stackArray[top];
       top--;
       cout << letter;
       return letter;
   }
   else
   {
       cout << "Stack is empty." << endl;
   }
   return letter;
}

// check to whether stack is full
bool Stack::isFull()
{
   if ( top == stackSize - 1 )
       return true;
   else
       return false;
}

// check to see if stack is empty
bool Stack::isEmpty()
{
   if ( top == -1 )
       return true;
   else
       return false;
}

#endif

#include <iostream>
#include <string>
using namespace std;

#include "stack.h"

int main()
{
   // local (automatic) variable declerations
   string word1;   // 4 letter word
   string word2;   // 4 letter word
   string message;   // message
   int i = -1;       // index counter
   int m = 1;
   bool word1MatchFound = false;
   bool word2MatchFound = false;
  
   do // prompt for user input for word1
   {
       cout << "Enter the first four letter word: ";
       getline( cin, word1 );

       if ( word1.length() < 4 || word1.length() > 4 )
       {
           cout << "The word must be exactly 4 characters in length. Please reenter." << endl;
       }
   } while ( word1.length() < 4 || word1.length() > 4 );
  
   do // prompt for user input for word2
   {
       cout << "Enter the second four letter word: ";
       getline( cin, word2 );

       if ( word2.length() < 4 || word2.length() > 4 )
       {
           cout << "The word must be exactly 4 characters in length. Please reenter." << endl;
       }
   } while ( word2.length() < 4 || word2.length() > 4 );

   // prompt for message entry
   cout << "Enter a message to encrypt: ";
   getline( cin, message );
  
   Stack myStack( message.length() );

   do // main program loop
   {
       i++; // increment i to advance forward and process new character
       word1MatchFound = false;
       word2MatchFound = false;

       for ( int j = 0; j < word1.length(); j++ )
       {
           // if the letter is found in word1, flag word1MatchFound = true and break out of for loop
           if ( message[i] == word1[j] )
           {
               word1MatchFound = true;
               break;
           }
       }
      
       // if the is not found in word1, push char to stack and increment i to process next letter
       if ( word1MatchFound == false )
       {
           myStack.push( message[i] );
       }
       else // if word1MatchFound == true
       {
           cout << message[i];
           m = i; // problem here if m = 0
           while( word2MatchFound == false && m > 0 )
           {
               // if letter is found in word2, set word2MatchFound = true and break out of loop
               m--;
               //word2MatchFound = false;
               for ( int k = 0; k < word2.length(); k++ )
               {
                   if ( message[m] == word2[k] )
                   {
                       word2MatchFound = true;
                       break;
                   }
               }

               if ( word2MatchFound == false )
               {
                   myStack.pop();
               }
           }
       }
   } while( i < message.length() );
  
   for ( int count = 0; count < message.length(); count++ )
   {
       myStack.pop();
   }

   system("pause");
   return 0;
}

I checked the code above there is no problem please try and read the above

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.