Question

Write a C++ program that will determine if one input string is a subsequence of a second input string. In a subsequence, all the characters in the first string will also be in the second string in the same order. For example: “abc” is a subsequence of “qzabc”. While the characters must be in the same order, they do not have to be consecutive. For example: “abc” is also a subsequence of “aaqbzcw”. We will use two stacks one and two. Two determine if the first string is a subsequence of the second string, push each of the charcters from the first input string onto stack one and then push the characters of the second input string onto stack two. Peek at the tops of the two stacks and if they match pop both. If they don’t match pop stack two. If stack one becomes empty, then we have found a subsequence. If stack two becomes

empty and there are still characters on stack one, it is not a subsequence.

Answer 1

PLEASE NOTE : FEEL FREE TO ASK ANY DOUBTS by COMMENTING

::::::::::::::::::::::::::::::::::::::::::::::::::: CODE :::::::::::::::::::::::::::::::::::::::::::::::::::

#include <iostream>
using namespace std;

// CLASS FOR STACK
class Stack{
   private:
       string str;   // to store characters
   public:
       // CONSTRUCTOR
       Stack(){
           this->str   = "";   // intialize empty string
       }

       // function to push character
       void push(char c){
           // add character to string
           this->str=this->str+c;
       }

       // function to pop character from stack
       char pop(){
           // if string is empty return zero character
           if(str.length()==0){
               return '\0';
           }

           // if string is not empty
           // store ending character in a variable
           char c=str[str.length()-1];

           // resize string by removing last character
           str.resize(str.size() - 1);

           // return character
           return c;
       }

       // function to return top character
       char peek(){
           // if string is empty return zero character
           if(str.length()==0){
               return '\0';
           }
           // else return last character
           return str[str.length()-1];
       }
};

// MAIN FUNCTION STARTS HERE
int main(){
   string s1,s2;
   // read string 1
   cout << "Enter String 1: ";   cin >> s1;
   // read string 2
   cout << "Enter String 2: ";   cin >> s2;

   // create stacks for string1 and string2
   Stack one;
   Stack two;

   // pushing all the characters of string1 to stack one
   for(int i=0;i<s1.length();i++){
       one.push(s1[i]);
   }
   // pushing all the characters of string1 to stack two
   for(int i=0;i<s2.length();i++){
       two.push(s2[i]);
   }

   // LOOP until either of above stack gets not empty
   while(true){
       // checking stack one is empty or not
       if(one.peek()=='\0'){
           // break if stack one is empty
           break;
       }
       // checking both stack top characters
       if(one.peek()==two.peek()){
           // if both topss are equal
           // pop both stacks character
           one.pop();
           two.pop();
       }
       // if top characters not equal
       else{
           // pop character from stack two
           two.pop();
           // checking stack two is empty or not
           if(two.peek()=='\0'){
               // break if stack two is empty
               break;
           }
       }
   }

   // CHECKING stack one is EMPTY or NOT
   if(one.peek()=='\0'){
       // PRINT message on console IF S1 is substring of S2
       cout << "String1 is Subsequence of String2\n";
   }
   else{
       // PRINT message on console
       // IF S1 is not substring of S2
       cout << "String1 is Not Subsequence of String2\n";
   }
   return 0;
}
// MAIN FUNCTION ENDS HERE

::::::::::::::::::::::::::::::::::::::::::::::::::: OUTPUT :::::::::::::::::::::::::::::::::::::::::::::::::::

- 0 x D : Stack_String.exe Enter String 1: abc Enter String 2: aaqbzcw Stringl is Subsequence of String2, Process exited after 7.741 seconds with return value o Press any key to continue...

- O X D : Stack_String.exe Enter String 1: aba Enter String 2: aaqbzcw Stringl is Not Subsequence of String2 Process exited after 11.48 seconds with return value o Press any key to continue...

::::::::::::::::::::::::::::::::::::::::::::::::::: CODE in EDITOR :::::::::::::::::::::::::::::::::::::::::::::::::::

Stack_String.cpp 1 #include <iostream> 2 using namespace std; // CLASS FOR STACK 59 class Stack{ private: string str; // to store characters public: // CONSTRUCTOR 10 Stack() { this->str = ""; // intialize empty string 11 14 15 // function to push character void push(char c){ // add character to string this->str=this->struc; // function to pop character from stack char pop() { // if string is empty return zero character if(str.length()==0){ return '\0'; // if string is not empty // store ending character in a variable char c=str[str.length()-1]; // resize string by removing Last character str.resize(str.size() - 1); // return character return c;

38 39 € 40 // function to return top character char peek() { // if string is empty return zero character if(str.length()==0){ return 'lo'; 41 42 // else return Last character return str(str.length()-1]; 47 L }; 49 // MAIN FUNCTION STARTS HERE 50 Ş int main() { string s1, s2; // read string 1 cout << "Enter String 1: "; cin >> s1; // read string 2 cout << "Enter String 2: "; cin >> s2; // create stacks for string1 and string 2 Stack one; Stack two; 62 63 // pushing all the characters of string1 to stack one for(int i=0;i<s1.length(); i++) { one.push(s1[i]); L 64 66 67 // pushing all the characters of stringi to stack two for(int i=0; i<s2.length(); i++) { two.push(s2[i]); 70 71 72 // LOOP until either of above stack gets not empty while(true) { // checking stack one is empty or not

if(one.peek()=='\0'){ // break if stack one is empty break; 0 // checking both stack top characters if(one. peek() ==two.peek()) { // if both topss are equal // pop both stacks character one.pop(); two.pop(); // if top characters not equal else{ // pop character from stack two two.pop(); // checking stack two is empty or not if(two.peek()=='\0'){ // break if stack two is empty break; 97 // CHECKING stack one is EMPTY or NOT if (one. peek()=='\0'){ // PRINT message on console IF Si is substring of 52 cout << "String1 is Subsequence of String2\n"; 99 103 else{ 102 // PRINT message on console // IF $1 is not substring of 52 104 cout << "String1 is Not Subsequence of String2\n"; 105 106 return 0; 107 L} 108 // MAIN FUNCTION ENDS HERE

Dear Friend, Feel Free to Ask Any Doubts by Commenting. ASAP i'll respond when i'm available.

Please Do Not Forget To Give A Thumbs UP +1. It will Helps me A Lot.

Thank YOU :-)