Module 09 Solutions

Download Module 09 Solutions

Exercise 00: Bitcoin Exchange

Parse CSV and calculate exchange values.

BitcoinExchange.hpp

class BitcoinExchange {
private:
    std::map<std::string, float> _database;

public:
    void loadDatabase(const std::string& filename);
    void processInput(const std::string& filename);
};

BitcoinExchange.cpp

std::string findClosestDate(const std::string& date) {
    std::map<std::string, float>::iterator it = _database.lower_bound(date);

    if (it == _database.end() || it->first != date) {
        if (it == _database.begin())
            return "";  // No earlier date
        --it;  // Go to previous date
    }
    return it->first;
}

Key Points:

• Use std::map for sorted key-value storage
• lower_bound() finds closest date efficiently
• Validate: date format, value 0-1000, leap years

---

Exercise 01: RPN Calculator

Evaluate Reverse Polish Notation.

RPN.cpp

int RPN::evaluate(const std::string& expression) {
    std::stack<int> stack;

    for (size_t i = 0; i < expression.length(); i++) {
        char c = expression[i];

        if (c == ' ')
            continue;

        if (isdigit(c)) {
            stack.push(c - '0');
        }
        else if (isOperator(c)) {
            if (stack.size() < 2)
                throw std::runtime_error("Error");

            int b = stack.top(); stack.pop();
            int a = stack.top(); stack.pop();

            switch (c) {
                case '+': stack.push(a + b); break;
                case '-': stack.push(a - b); break;
                case '*': stack.push(a * b); break;
                case '/':
                    if (b == 0)
                        throw std::runtime_error("Error");
                    stack.push(a / b);
                    break;
            }
        }
        else {
            throw std::runtime_error("Error");
        }
    }

    if (stack.size() != 1)
        throw std::runtime_error("Error");

    return stack.top();
}

Key Points:

• Stack is perfect for RPN
• Order matters: a - b not b - a
• Input numbers < 10 (single digit)

---

Exercise 02: PmergeMe

Ford-Johnson sort with two containers.

PmergeMe.cpp

void PmergeMe::sortVector() {
    if (_vec.size() <= 1)
        return;

    std::vector<int> larger, smaller;

    // Pair and separate
    for (size_t i = 0; i + 1 < _vec.size(); i += 2) {
        if (_vec[i] > _vec[i + 1]) {
            larger.push_back(_vec[i]);
            smaller.push_back(_vec[i + 1]);
        } else {
            larger.push_back(_vec[i + 1]);
            smaller.push_back(_vec[i]);
        }
    }

    // Handle odd element
    bool hasOdd = (_vec.size() % 2 != 0);
    int oddElement = hasOdd ? _vec.back() : 0;

    // Recursively sort larger
    _vec = larger;
    sortVector();
    larger = _vec;

    // Insert smaller using binary search
    for (size_t i = 0; i < smaller.size(); i++) {
        std::vector<int>::iterator pos =
            std::lower_bound(larger.begin(), larger.end(), smaller[i]);
        larger.insert(pos, smaller[i]);
    }

    // Insert odd element
    if (hasOdd) {
        std::vector<int>::iterator pos =
            std::lower_bound(larger.begin(), larger.end(), oddElement);
        larger.insert(pos, oddElement);
    }

    _vec = larger;
}

Timing:

clock_t start = clock();
sortVector();
clock_t end = clock();
double us = (double)(end - start) / CLOCKS_PER_SEC * 1000000;
std::cout << "Time: " << us << " us" << std::endl;