NoDupes.cpp

#include "processInput.h$"$

#include

#include

#include

#include

#include

using namespace std;

void noDuplicates$($const string& input$)$

$\{$

bool isInStack$[10]$; $//$ inInStack$[$i$]==$ true iff digit is already on the stack

int remainingInInput$[10]$; $//$ how many occurrences of each digit remain unprocessed in the input?

fill$\_$n $($isInStack$,10,$ false$)$;

fill$\_$n $($remainingInInput$,10,0)$;

$//$ Count the number of times each digit occurs in the input

for $($char c: input$)\{$

int digit $=$ c $-\text{'}0\text{'}$;

$++$remainingInInput$[$digit$]$;

$\}$

stack digitStack;

$//$ Process each character of the input

for $($char c: input$)\{$

int digit $=$ c $-\text{'}0\text{'}$;

$--$remainingInInput$[$digit$]$;

processInputDigit $($digit$,$ digitStack, isInStack, remainingInInput$)$;

$\}$

$//$ Print the answer

print $($cout$,$ digitStack$)$;

cout $$ endl;

$\}$

int main $($int argc, char$**$ argv$)$

$\{$

if $($argc $<mtext\; id="EditorElement\_7948578"></mtext><mn\; id="EditorElement\_7948579">2</mn><mi\; id="EditorElement\_7948580">)</mi><mtext\; id="EditorElement\_7948581"></mtext><mi\; id="EditorElement\_7948582">\{</mi>$

cerr $$ "Usage: $"$ argv number

$"$

or $"$ argv filepath" $$ endl;

return $-1$;

$\}$

string input $($argv$[1])$;

if $($input$.$find$\_$first$\_$not$\_$of$("0123456789")!=$ string::npos$)$

$\{$

$//$ Input is not a number $-$ assume it is a file name and

$//$ read the number from there

ifstream in$($input$)$;

in $>>$ input;

in$.$close$()$;

$\}$

noDuplicates$($input$)$;

$\}$

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

$**$These are the two files that coincide with creating processInput.cpp$.$

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

$**$ability to function correctly within the noDupes application

$**$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]$;