Question

In C++

Consider the language
L = { s$s' : s is a possibly empty string of characters other than $ , s' = reverse( s )}
as defi ned in Chapter 6 . Write a recognition algorithm for this language that uses both a queue and a stack. Thus,
as you traverse the input string, you insert each character of s into a queue and each character of s' into a stack.
Assume that each input string contains exactly one $ .

Answer 1

Summary :

Notes :
we implement the algorithm as following :
Iterate thru given string and perform following for each char

state = 0
length1 = 0
while input char is not 'S'
push the char to queue
   length1 += 1

if reached end of string :
return error

   length2 = 0 ;
while input char is not end of string
push the char to stack .
   length2 += 1

   if ( length1 != length2 )
       return error
  
   while ( !stack.empty() )
       if ( stack.top() != queue.front() )
           return error
       else
           stack.pop()
           queue.pop()
  

########################## Code #########################

#include <iostream>
#include <stdio.h>
#include <queue>
#include <stack>
#include <string>

using namespace std;

bool checkString( const string &str )
{
        stack<char> st ;
        queue<char> qu ;
        
        int len1 = 0 , len2 = 0 ;
        
        int state = 0 ;
        for( int i=0 ; i < str.size(); i++ )
        {
                if  ( str[i] == 'S' )
                {
                        if ( ( state == 0 )  )
                        state = 1 ;
                        else 
                        {
                                cout << "Multiple S found " << str[i] << " state " << state << " \n";
                                return false ;
                        }
                } else {
                        if ( state == 0 )
                        {
                                st.push(str[i]);
                                len1 += 1;
                        }
                        else 
                        {
                                qu.push(str[i]);
                                len2 +=1 ;
                        }
                }
        }
        if ( state == 0 )
        {
                cout << " No 'S' found \n";
                return false ;
        }
        
        if ( st.size() == qu.size() )
        {
                while ( !st.empty() )
                {
                        if ( st.top() != qu.front() )
                        {
                                cout << " s != s' ,  " << st.top() << " != " << qu.front() << "\n" ;
                                return false ;
                        } else 
                        {
                                st.pop();
                                qu.pop();
                        }
                }
                return true ;
        }
        else {
                cout << " --- length(s) != length(s') \n";
                return false ;
        }
        
}

int main()
{
        string s1 = "abcdefSdkjf";
        cout << " Checking for string - " << s1 << " ,  result - " << checkString(s1 ) << "\n";
        
        string s2 = "abcSdefSdkjf";
        cout << " Checking for string - " << s2 << " ,  result - " << checkString(s2 ) << "\n";
        
        string s3 = "abcdefSabcdef";    
        cout << " Checking for string - " << s3 << " ,  result - " << checkString(s3 ) << "\n";
        
        string s4 = "S";
        cout << " Checking for string - " << s4 << " ,  result - " << checkString(s4 ) << "\n";
        
        string s5 = "aS";
        cout << " Checking for string - " << s5 << " ,  result - " << checkString(s5 ) << "\n";
        
        string s6 = "Sn";
        cout << " Checking for string - " << s6 << " ,  result - " << checkString(s6 ) << "\n";
        
        string s7 = "abcdefSfedcba";
        cout << " Checking for string - " << s7 << " ,  result - " << checkString(s7 ) << "\n";
        
        string s8 = "abcdeffedcba";
        cout << " Checking for string - " << s8 << " ,  result - " << checkString(s8 ) << "\n";
        
}

#################### Output ###################