$3)$ This programming problem deals with the template$-$based stack StackType and queue QueType implementations, as well as C$++$ strings. $(40$ pts$)$

Note that you must use the provided StackType.h and QueType.h files found attached with the assignment. Also, be certain to adhere to the example below in using the standard library std::string as arguments and not a character array as input, since we will test it using strings.

You are to create a function decode in a file stringdecoding.cpp with the following signature:

std::string decode$($std::string exp, std::string code$)\{...\}$

The function body should satisfy the following characteristics:

The function must iterate through each character in exp $($recommended is to use the std::string at function$)$ and take one of two actions:

i$.$ Characters in the string exp that are not also in the string code should be present in output in normal, sequential order as they are encountered, without modification.

ii$.$ All characters in the string exp that are also present in the string code should be present in output after the characters printed in normal order from part i$.$ AND entirely in reverse order.

Sample input and output for reference is as follows:

decode$("$czitqommta$\_$ehmumt$\_$nio$\_$szozir$\_$eulopupoa$\_$yeht$\_","\_$acefhilnpst"$)$

must return the following string:

"zqommmumozozruouoy$\_$the$\_$apple$\_$is$\_$in$\_$the$\_$attic"

As alluded to above, the recommended approach is to:

$1.$ Create StackType$<>$ and QueType$<>$ instances of the appropriate types and add characters to them until the end of string exp is reached.

$2.$ Put together the output string using appropriate operations using to criteria i and ii above.