Complete in C$++,$ practice working with stacks.

Your focus in this assignment will be implementing, the processInput.cpp$,$ the functions declared in processInput.h

Problem Description: This program takes as input an integer of up to $500,000$ digits. $($Obviously$,$ we can$$t store this in a C$++$ int or even a long long int. It will need to be stored in a string$).$ The challenge is to find the smallest integer that can be formed by removing duplicate digits from the input. The final input must contain every digit that can be found in the input $($including possibly a leading $0).$ Digits may not be swapped or otherwise rearranged. They may only be removed and may be removed only if the same digit occurs elsewhere in the number.

For example, given the input

$31231302$

the smallest input that can be formed be removing duplicates would be

$1230$

How did we get that? We use a stack:

The program must run in O$($n$)$ time where n is the length of the input string.

The program reads either a long integer from the command line or a path to a file containing a single line of text holding such a string.

In addition to the stack, you may need structures to keep track of how many occurrences of each digit remain in the part of the input to be processed and to keep track of which digits are already in the stack. You could determine this by repeatedly scanning the input and stack, but that won$$t achieve the desired O$($n$)$ complexity if you have to do an O$($n$)$ scan for each of the n digits. But since there are only $10$ possible digits, you can track these with simple arrays:

int unprocessedDigits$[10]$;

bool digitInStack$[10]$;

Attached is processInput.h

#ifndef PROCESSINPUT$\_$H

#define PROCESSINPUT$\_$H

#include

#include

$/**$

$*$ @brief Process a digit of input.

$*$

$*$ Process a single digit of input in the search for the smallest

$*$ number that can be formed by removing duplicates.

$*$

$*$ @param digit the input digit, a number in the range $0.\mathrm{.}9$

$*$ @param digitStack a stack of digits representign the best number found so far,

$*$ with the most significant digit of the number on the bottom

$*$ of the stack.

$*$ @param digitIsInStack an array indicating which digits are on the stack.

$*$ Will be updated by this function.

$*$ @param remainingDigitsInInput a count of the number of times each

$*$ digit occurs in the remaining output.

$*/$

void processInputDigit $($int digit, std::stack& digitStack,

bool$*$ digitIsInStack, const int$*$ remainingDigitsInInput$)$;

$/**$

$*$ @brief Print the number on the stack to out.

$*$

$*$ @param out the stream to which to print.

$*$ @param digitStack a stack of digits, most significant on the bottom.

$*/$

void print $($std::ostream& out, std::stack& digitStack$)$;

#endif