Sunday, February 21, 2016

Given a string with I and D output a sequence of numbers

Problem:
Given a string with "I" and "D" where "I" stands for Increment and "D" stands for Decrement, produce a sequence of numbers which follows the same pattern as the input string.

Sample Input:
ID
IID
IDDI

Sample Output:
2 3 1
2 3 4 1
3 4 2 1 5

C++ Program:
 
#include <iostream>
using namespace std;

void printNumbers(string input) {
    if (input.length() == 0) {
        return;
    }
    int dCount = 0;
    for (int i = 0; i < input.length(); i++) {
        if (input[i] == 'D') {
            dCount++;
        }
    }
    int numbers[100];
    for (int i = 0; i <= input.length(); i++) {
        numbers[i] = i+1;
    }
    // The starting number is at the index which equals the number of D's
    cout << endl << numbers[dCount] << " ";
    numbers[dCount] = -1;
    // Increment starts at the index next to index equal to number of D's.
    int iCount = dCount+1;
    // Next decrement starts at the index previous to index equal to number of D's.
    dCount--;
    for (int i = 0; i < input.length(); i++) {
        if (input[i] == 'I') {
            cout << numbers[iCount] << " ";
            numbers[iCount++] = -1;
        }
        else {
            cout << numbers[dCount] << " ";
            numbers[dCount--] = -1;
        }
    }
    cout << endl;
}

int main() {
 printNumbers("IDDI");
 return 0;
}