Morse code

As a test, I was asked to write a morse code task where some of the signals weren’t able to be determined from the input. So in this case instead of having either the dot (.) or dash (-) we have a question mark (?) where it could be either a dot / dash.

Here is an image of the morse code alphabet of dots / dashes and here is a link to a view of the “tree” of the morse code of the dichotomic search, basically binary search of the morse code.

So, we are only going down 3 levels, below are some tests to confirm that the process is working fine.

  • .- = A
  • . = E
  • … = S
  • -.- = K
  • ? = ET
  • -? = NM

So, I approached this test by thinking that I need to have an “item” that stores the current value (e.g. character) and left / right item, and here is my item.h definition.

class item {
    private:
        char value;
        item *left;
        item *right;
    public:
        item(char value,item *left,item *right);
        item(char value);
        item(item *left,item *right);

        item();

        char getValue();

        item* leftItem();
        item* rightItem();
};

And then to build the 3 levels of the search tree

    item* head = new item(
        new item('e',
            new item('i', 
                new item('s'),
                new item('u')
            ),
            new item('a',
                new item('r'),
                new item('w')
            )
        ),
        new item('t',
            new item('n', 
                new item('d'),
                new item('k')
            ),
            new item('m',
                new item('g'),
                new item('o')
            )
        )
    );

and then the last part was literally reading in the signal to be processed and going down the tree either left / right or both for undermined signal.

string output(string signal, item* codes) {
    string ret="";
    if (signal.size() ==0 ) 
        return string(1,codes->getValue());
    for (string::size_type i=0; i < signal.size();i++) {
        if ('?' == signal[i]) {
            ret += output("."+signal.substr(i+1),codes);
            ret += output("-"+signal.substr(i+1),codes);
            return ret;
        } else if ('.' == signal[i]) {
            return output(signal.substr(i+1),codes->leftItem());
        } else if ('-' == signal[i]) {
            return output(signal.substr(i+1),codes->rightItem());
        } else {
            throw invalid_argument(string("Invalid character at this point of the string ").append(signal));
        }
    }
    return ret;
}

If you want to view the whole code, here is the link to the zip file of the morse code.