Module 09: STL Practical Applications

Download Official Subject PDF

Prerequisites

Complete Modules 00-08 first. This module applies everything you’ve learned.

Key Concepts:

• Choosing the right container
• File parsing
• Algorithm implementation
• Performance considerations

---

Why This Matters

This module is about making the right choices. Different containers have different performance characteristics, and choosing wisely can make your program 10x faster—or 10x slower.

Container Selection Guide

• Need fast random access by index? → vector or deque
• Need fast insertion/deletion in the middle? → list
• Need key-value lookups? → map (sorted) or unordered_map (faster)
• Need LIFO (last-in, first-out)? → stack
• Need FIFO (first-in, first-out)? → queue

---

Understanding Advanced STL Syntax

This module uses advanced STL features. Here’s the syntax explained:

The lower_bound Algorithm

std::map<std::string, float>::iterator it = db.lower_bound(date);

• lower_bound finds the first element NOT LESS than the given key
• It returns an iterator to the first element >= the search value
• For maps, it uses the sorted order of keys
• If all elements are less, returns end()
• Used to find insertion points or lookup closest values

The insert Operation

v.insert(it, value);   // Insert value at position it

• insert adds elements at a specific iterator position
• For vectors, elements after the position are shifted (O(n))
• For lists, insertion is O(1) but you must find position first (O(n))
• Combined with lower_bound, inserts while maintaining sorted order

The static_cast<double> in Timing

double microseconds = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000000;

• static_cast<double> ensures floating-point division
• Without it, integer division would lose precision
• CLOCKS_PER_SEC is usually a large integer
• Cast before division to preserve decimal places

The std::atoi and std::atof Functions

int n = std::atoi(str.c_str());
float f = std::atof(str.c_str());

• atoi = ASCII to Integer
• atof = ASCII to Float
• .c_str() converts std::string to const char* (required by these C functions)
• These functions return 0 on error, which can be ambiguous

The operator[] with Maps

ages["Alice"] = 25;   // Insert or update

• [] on maps accesses or creates a key-value pair
• If key exists, returns reference to value
• If key doesn’t exist, inserts it with default value (0 for numbers)
• map[key] always succeeds (creates if needed)
• Use find() if you don’t want to create missing keys

---

1. Module Rules

Container Restrictions

• Must use at least one container per exercise
• Exercise 02 requires TWO different containers
• Once a container is used, it’s forbidden for remaining exercises

Suggested Container Allocation

Exercise	Suggested Container(s)	Why
ex00	map	Key-value pairs (date -> price)
ex01	stack	RPN naturally uses stack
ex02	vector + deque (or list)	Sorting comparison

---

2. Exercise 00: Bitcoin Exchange

Problem

Read a database of Bitcoin prices and calculate values for given amounts on specific dates.

Input Format

// Database (CSV): date,exchange_rate
2009-01-02,0
2011-01-03,0.3
2011-01-09,0.32

// Input file: date | value
date | value
2011-01-03 | 3
2011-01-03 | 2

Solution Approach

class BitcoinExchange {
private:
    std::map<std::string, float> _database;  // date -> price

    bool isValidDate(const std::string& date);
    bool isValidValue(const std::string& value, float& result);
    std::string findClosestDate(const std::string& date);

public:
    BitcoinExchange();
    BitcoinExchange(const BitcoinExchange& other);
    BitcoinExchange& operator=(const BitcoinExchange& other);
    ~BitcoinExchange();

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

### File I/O with ifstream
```cpp
#include <fstream>
#include <string>

void BitcoinExchange::loadDatabase(const std::string& filename) {
    // Open file (.c_str() needed for C++98 compatibility)
    std::ifstream file(filename.c_str());

    // Check if file opened successfully
    if (!file.is_open())
        throw std::runtime_error("Cannot open database file");

    std::string line;
    std::getline(file, line);  // Skip header line

    // Read line by line
    while (std::getline(file, line)) {
        size_t pos = line.find(',');
        if (pos != std::string::npos) {
            std::string date = line.substr(0, pos);
            float price = std::atof(line.substr(pos + 1).c_str());
            _database[date] = price;
        }
    }

    file.close();  // Optional - closes automatically on destruction
}

std::getline for Line-by-Line Reading

std::ifstream file("input.txt");
std::string line;

// Read until EOF
while (std::getline(file, line)) {
    // Process line
    std::cout << line << std::endl;
}

// Check why loop ended
if (file.eof()) {
    // Normal end of file
}
else if (file.fail()) {
    // Read error occurred
}

map::lower_bound for Efficient Lookup

std::string BitcoinExchange::findClosestDate(const std::string& date) {
    // lower_bound returns iterator to first element >= date
    std::map<std::string, float>::iterator it = _database.lower_bound(date);

    // Case 1: Exact match found
    if (it != _database.end() && it->first == date) {
        return it->first;
    }

    // Case 2: date is smaller than all keys
    if (it == _database.begin()) {
        return "";  // No earlier date exists
    }

    // Case 3: Go to previous (earlier) date
    --it;
    return it->first;
}

Date Validation with Leap Year Logic

bool BitcoinExchange::isValidDate(const std::string& date) {
    // Format: YYYY-MM-DD (exactly 10 characters)
    if (date.length() != 10)
        return false;
    if (date[4] != '-' || date[7] != '-')
        return false;

    // Check that year, month, day are digits
    for (int i = 0; i < 10; i++) {
        if (i == 4 || i == 7) continue;  // Skip dashes
        if (!std::isdigit(date[i]))
            return false;
    }

    int year = std::atoi(date.substr(0, 4).c_str());
    int month = std::atoi(date.substr(5, 2).c_str());
    int day = std::atoi(date.substr(8, 2).c_str());

    // Basic range checks
    if (year < 1)
        return false;
    if (month < 1 || month > 12)
        return false;
    if (day < 1 || day > 31)
        return false;

    // Days per month (index 0 unused)
    int daysInMonth[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    // Leap year calculation
    // A year is a leap year if:
    // - Divisible by 4 AND not divisible by 100
    // - OR divisible by 400
    bool isLeapYear = (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
    if (isLeapYear && month == 2)
        daysInMonth[2] = 29;

    return day <= daysInMonth[month];
}

Leap Year Examples

// 2000: divisible by 400 -> LEAP YEAR
// 1900: divisible by 100 but not 400 -> NOT leap year
// 2024: divisible by 4, not by 100 -> LEAP YEAR
// 2023: not divisible by 4 -> NOT leap year

bool isLeap(int year) {
    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}

---

3. Exercise 01: Reverse Polish Notation (RPN)

Problem

Evaluate mathematical expressions in postfix notation.

How RPN Works

Infix:   (3 + 4) * 2
Postfix: 3 4 + 2 *

Evaluation:
- Read 3, push: [3]
- Read 4, push: [3, 4]
- Read +, pop 4,3, push 7: [7]
- Read 2, push: [7, 2]
- Read *, pop 2,7, push 14: [14]
- Result: 14

Solution

class RPN {
private:
    std::stack<int> _stack;

    bool isOperator(char c);
    int applyOperator(int a, int b, char op);

public:
    RPN();
    RPN(const RPN& other);
    RPN& operator=(const RPN& other);
    ~RPN();

    int evaluate(const std::string& expression);
};

int RPN::evaluate(const std::string& expression) {
    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();

            _stack.push(applyOperator(a, b, c));
        }
        else {
            throw std::runtime_error("Error");
        }
    }

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

    return _stack.top();
}

bool RPN::isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int RPN::applyOperator(int a, int b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/':
            if (b == 0)
                throw std::runtime_error("Error");
            return a / b;
    }
    throw std::runtime_error("Error");
}

---

4. vector::insert Operation

Insert at Position

std::vector<int> v;
v.push_back(10);
v.push_back(30);
v.push_back(40);
// v = {10, 30, 40}

// Insert 20 at position 1 (before 30)
std::vector<int>::iterator it = v.begin() + 1;
v.insert(it, 20);
// v = {10, 20, 30, 40}

Insert with lower_bound (Sorted Insert)

std::vector<int> sorted = {10, 20, 40, 50};

// Insert 30 in sorted position
std::vector<int>::iterator pos = std::lower_bound(sorted.begin(), sorted.end(), 30);
sorted.insert(pos, 30);
// sorted = {10, 20, 30, 40, 50}

Insert Performance

Container	Insert at front	Insert at back	Insert in middle
vector	O(n)	O(1) amortized	O(n)
deque	O(1)	O(1)	O(n)
list	O(1)	O(1)	O(1)*

*After finding position

---

5. deque Operations

deque - Double-Ended Queue

#include <deque>

std::deque<int> dq;

// Add elements (efficient at BOTH ends)
dq.push_back(30);   // {30}
dq.push_front(10);  // {10, 30}
dq.push_back(40);   // {10, 30, 40}
dq.push_front(5);   // {5, 10, 30, 40}

// Random access (like vector)
dq[0];              // 5
dq.at(1);           // 10

// Remove from both ends
dq.pop_front();     // {10, 30, 40}
dq.pop_back();      // {10, 30}

// Insert in middle
std::deque<int>::iterator it = dq.begin() + 1;
dq.insert(it, 20);  // {10, 20, 30}

deque vs vector

Feature	vector	deque
push_front	O(n) slow	O(1) fast
push_back	O(1)	O(1)
Random access	O(1)	O(1)
Memory	Contiguous	Chunked
Cache locality	Better	Worse

---

6. Exercise 02: PmergeMe (Ford-Johnson Algorithm)

Problem

Implement merge-insert sort using two different containers and compare performance.

Ford-Johnson Algorithm Overview

1. Pair elements: Group input into pairs
2. Sort each pair: Within each pair, identify larger and smaller element
3. Recursively sort: Sort the sequence of larger elements
4. Binary insert: Insert smaller elements using binary search (lower_bound)

Why Ford-Johnson?

• Minimizes the number of comparisons
• Uses Jacobsthal sequence for optimal insertion order
• Theoretical improvement over simple merge sort in comparison count

Jacobsthal Sequence (Optional Optimization)

The Jacobsthal sequence determines optimal insertion order: 1, 3, 5, 11, 21, 43, …

// J(n) = J(n-1) + 2*J(n-2), J(0)=0, J(1)=1
int jacobsthal(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return jacobsthal(n - 1) + 2 * jacobsthal(n - 2);
}

Simplified Implementation

class PmergeMe {
private:
    std::vector<int> _vec;
    std::deque<int> _deq;

    void sortVector();
    void sortDeque();

public:
    PmergeMe();
    PmergeMe(const PmergeMe& other);
    PmergeMe& operator=(const PmergeMe& other);
    ~PmergeMe();

    void parseInput(int argc, char** argv);
    void sort();
    void display() const;
};

// Ford-Johnson for vector
void PmergeMe::sortVector() {
    if (_vec.size() <= 1)
        return;

    std::vector<int> larger, smaller;

    // Step 1: Create pairs
    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;

    // Step 2: Recursively sort larger elements
    _vec = larger;
    sortVector();
    larger = _vec;

    // Step 3: Insert smaller elements
    // First element of smaller goes first (paired with first of larger)
    if (!smaller.empty()) {
        std::vector<int>::iterator pos = std::lower_bound(
            larger.begin(), larger.end(), smaller[0]);
        larger.insert(pos, smaller[0]);
    }

    // Insert remaining using Jacobsthal sequence for optimal insertions
    for (size_t i = 1; 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;
}

Step-by-Step Example

Input: [3, 1, 4, 1, 5, 9, 2, 6]

1. PAIR AND SORT PAIRS:
   (3,1) -> larger=3, smaller=1
   (4,1) -> larger=4, smaller=1
   (5,9) -> larger=9, smaller=5
   (2,6) -> larger=6, smaller=2

   Larger:  [3, 4, 9, 6]
   Smaller: [1, 1, 5, 2]

2. RECURSIVELY SORT LARGER:
   [3, 4, 9, 6] -> [3, 4, 6, 9]

3. BINARY INSERT SMALLER:
   Start: [3, 4, 6, 9]
   Insert 1 (paired with 3): lower_bound finds 3, insert before -> [1, 3, 4, 6, 9]
   Insert 1 (paired with 4): lower_bound finds 3, insert before -> [1, 1, 3, 4, 6, 9]
   Insert 5 (paired with 9): lower_bound finds 6, insert before -> [1, 1, 3, 4, 5, 6, 9]
   Insert 2 (paired with 6): lower_bound finds 3, insert before -> [1, 1, 2, 3, 4, 5, 6, 9]

Result: [1, 1, 2, 3, 4, 5, 6, 9]

Using Two Different Containers

class PmergeMe {
private:
    std::vector<int> _vec;  // First container
    std::deque<int> _deq;   // Second container (must be different!)

    void sortVector();
    void sortDeque();       // Same algorithm, different container
};

// Parse input into both containers
void PmergeMe::parseInput(int argc, char** argv) {
    for (int i = 1; i < argc; i++) {
        int num = std::atoi(argv[i]);
        if (num < 0)
            throw std::runtime_error("Error: negative number");
        _vec.push_back(num);
        _deq.push_back(num);  // Same data in both
    }
}

Timing

#include <ctime>

void PmergeMe::sort() {
    // Vector
    clock_t start = clock();
    sortVector();
    clock_t end = clock();
    double vecTime = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000000;

    // Deque
    start = clock();
    sortDeque();
    end = clock();
    double deqTime = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000000;

    std::cout << "Time to process " << _vec.size()
              << " elements with std::vector: " << vecTime << " us" << std::endl;
    std::cout << "Time to process " << _deq.size()
              << " elements with std::deque: " << deqTime << " us" << std::endl;
}

---

7. Common Pitfalls

Exercise 00

• Not handling missing dates (use closest earlier date)
• Not validating date format
• Value must be positive and <= 1000

Exercise 01

• Forgetting division by zero check
• Numbers must be < 10 (single digit in input)
• Result can be any size

Exercise 02

• Using same container for both implementations
• Not measuring time correctly
• Not implementing actual Ford-Johnson (simplified sorts may not pass)

---

8. Container Properties Summary

Container	Random Access	Insert Front	Insert Back	Insert Middle	Sorted
vector	O(1)	O(n)	O(1)*	O(n)	No
deque	O(1)	O(1)	O(1)	O(n)	No
list	O(n)	O(1)	O(1)	O(1)	No
map	O(log n)	-	-	O(log n)	Yes
set	O(log n)	-	-	O(log n)	Yes
stack	-	-	O(1)	-	No

*amortized

---

Exercise 00: Bitcoin Exchange

Subject Analysis

Create a program that:

• Reads a database file (CSV: date,exchange_rate)
• Reads an input file (CSV: date | value)
• For each input line, calculates value * exchange_rate
• Uses the closest earlier date if exact match not found

Key constraints:

• Date format: YYYY-MM-DD
• Input value: positive number between 0 and 1000
• Must handle invalid input gracefully
• Database file provided: data.csv

Approach Strategy

Think before coding:

1. Which container for the database?

   • std::map<std::string, float> - perfect for key-value with sorted keys
   • String dates sort correctly lexicographically (“2020-01-15” < “2020-02-01”)

2. How to find closest earlier date?

   • map::lower_bound(key) returns iterator to first element >= key
   • If no exact match, go back one position

3. What validations are needed?

   • Date format and validity (leap years!)
   • Value is positive and <= 1000
   • Line format (contains |)

Progressive Code Building

Stage 1: Class structure

BitcoinExchange.hpp

#ifndef BITCOINEXCHANGE_HPP
#define BITCOINEXCHANGE_HPP

#include <map>
#include <string>

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

    bool isValidDate(const std::string& date) const;
    bool isValidValue(const std::string& value, float& result) const;
    std::string trim(const std::string& str) const;

public:
    BitcoinExchange();
    BitcoinExchange(const BitcoinExchange& other);
    BitcoinExchange& operator=(const BitcoinExchange& other);
    ~BitcoinExchange();

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

#endif

Stage 2: Load database

BitcoinExchange.cpp - loadDatabase

#include "BitcoinExchange.hpp"
#include <fstream>
#include <sstream>
#include <iostream>

void BitcoinExchange::loadDatabase(const std::string& filename) {
    std::ifstream file(filename.c_str());
    if (!file.is_open()) {
        throw std::runtime_error("Error: could not open database file.");
    }

    std::string line;
    std::getline(file, line);  // Skip header

    while (std::getline(file, line)) {
        size_t comma = line.find(',');
        if (comma == std::string::npos) continue;

        std::string date = line.substr(0, comma);
        std::string rateStr = line.substr(comma + 1);

        float rate;
        std::istringstream iss(rateStr);
        if (iss >> rate) {
            _database[date] = rate;
        }
    }
}

Stage 3: Date validation

BitcoinExchange.cpp - validation

bool BitcoinExchange::isValidDate(const std::string& date) const {
    // Check format: YYYY-MM-DD (10 chars)
    if (date.length() != 10) return false;
    if (date[4] != '-' || date[7] != '-') return false;

    // Extract parts
    int year, month, day;
    if (sscanf(date.c_str(), "%d-%d-%d", &year, &month, &day) != 3) {
        return false;
    }

    // Validate ranges
    if (year < 1 || month < 1 || month > 12 || day < 1) return false;

    // Days per month
    int daysInMonth[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    // Leap year check
    bool isLeap = (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
    if (isLeap) daysInMonth[2] = 29;

    return day <= daysInMonth[month];
}

bool BitcoinExchange::isValidValue(const std::string& value, float& result) const {
    std::istringstream iss(value);
    if (!(iss >> result)) return false;
    if (result < 0) return false;
    return true;
}

Stage 4: Find closest date and process

BitcoinExchange.cpp - processing

void BitcoinExchange::processInput(const std::string& filename) {
    std::ifstream file(filename.c_str());
    if (!file.is_open()) {
        std::cerr << "Error: could not open file." << std::endl;
        return;
    }

    std::string line;
    std::getline(file, line);  // Skip header

    while (std::getline(file, line)) {
        size_t pipe = line.find(" | ");
        if (pipe == std::string::npos) {
            std::cerr << "Error: bad input => " << line << std::endl;
            continue;
        }

        std::string date = trim(line.substr(0, pipe));
        std::string valueStr = trim(line.substr(pipe + 3));

        // Validate date
        if (!isValidDate(date)) {
            std::cerr << "Error: bad input => " << date << std::endl;
            continue;
        }

        // Validate value
        float value;
        if (!isValidValue(valueStr, value)) {
            std::cerr << "Error: bad input => " << valueStr << std::endl;
            continue;
        }
        if (value < 0) {
            std::cerr << "Error: not a positive number." << std::endl;
            continue;
        }
        if (value > 1000) {
            std::cerr << "Error: too large a number." << std::endl;
            continue;
        }

        // Find closest date
        std::map<std::string, float>::iterator it = _database.lower_bound(date);
        if (it == _database.end() || it->first != date) {
            if (it == _database.begin()) {
                std::cerr << "Error: date too early => " << date << std::endl;
                continue;
            }
            --it;  // Go to previous (closest earlier) date
        }

        float rate = it->second;
        std::cout << date << " => " << value << " = " << (value * rate) << std::endl;
    }
}

Line-by-Line Explanation

Understanding lower_bound:

Scenario	lower_bound returns
Exact match exists	Iterator to that element
No exact match	Iterator to first element > key
All elements < key	end() iterator

std::map<std::string, float> db;
db["2020-01-01"] = 100;
db["2020-02-01"] = 200;
db["2020-03-01"] = 300;

// Case 1: Exact match
db.lower_bound("2020-02-01");  // Points to 2020-02-01

// Case 2: Between two dates
db.lower_bound("2020-02-15");  // Points to 2020-03-01
// We want 2020-02-01, so --it

// Case 3: Before all dates
db.lower_bound("2019-01-01");  // Points to 2020-01-01
// No earlier date exists - error!

Leap year calculation:

bool isLeap = (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
// 2000: leap (divisible by 400)
// 1900: not leap (divisible by 100 but not 400)
// 2020: leap (divisible by 4, not by 100)
// 2021: not leap

Common Pitfalls

1. Not handling “earlier than database” case:

// WRONG: Assumes there's always an earlier date
std::map<std::string, float>::iterator it = _database.lower_bound(date);
--it;  // Undefined behavior if it == begin()!

// RIGHT: Check for begin()
if (it == _database.begin()) {
    std::cerr << "Error: date too early" << std::endl;
    continue;
}
--it;

2. Forgetting leap years:

// WRONG: February always 28 days
int daysInMonth[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

// RIGHT: Check leap year
if (isLeap) daysInMonth[2] = 29;

3. Wrong pipe format:

// WRONG: Subject uses " | " (with spaces)
size_t pipe = line.find("|");

// RIGHT: Look for " | "
size_t pipe = line.find(" | ");

Testing Tips

Create test input file:

input.txt

date | value
2011-01-03 | 3
2011-01-03 | 2
2011-01-03 | 1
2011-01-03 | 1.2
2011-01-09 | 1
2012-01-11 | -1
2001-42-42
2012-01-11 | 1
2012-01-11 | 2147483648

Test script:

./btc input.txt

# Expected output:
# 2011-01-03 => 3 = 0.9
# 2011-01-03 => 2 = 0.6
# 2011-01-03 => 1 = 0.3
# 2011-01-03 => 1.2 = 0.36
# 2011-01-09 => 1 = 0.32
# Error: not a positive number.
# Error: bad input => 2001-42-42
# 2012-01-11 => 1 = 7.1
# Error: too large a number.

Final Code

BitcoinExchange.hpp

#ifndef BITCOINEXCHANGE_HPP
#define BITCOINEXCHANGE_HPP

#include <map>
#include <string>

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

    bool isValidDate(const std::string& date) const;
    std::string trim(const std::string& str) const;

public:
    BitcoinExchange();
    BitcoinExchange(const BitcoinExchange& other);
    BitcoinExchange& operator=(const BitcoinExchange& other);
    ~BitcoinExchange();

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

#endif

---

Exercise 01: RPN (Reverse Polish Notation)

Subject Analysis

Create a program that:

• Takes an RPN expression as argument
• Evaluates it and prints the result
• Numbers are always single digits (< 10)
• Operators: +, -, *, /

RPN explained:

• Normal: (3 + 4) * 2
• RPN: 3 4 + 2 *
• Read left to right, no parentheses needed

Approach Strategy

Think before coding:

1. Why use a stack?

   • RPN naturally uses LIFO order
   • Push numbers, pop for operations, push result

2. Algorithm:

   For each token:
     If number: push to stack
     If operator: pop two, calculate, push result
   Final answer: only item on stack

3. Order matters for subtraction/division:

   • 5 3 - means 5 - 3 = 2, not 3 - 5
   • Pop b first, then a: result = a OP b

Progressive Code Building

Stage 1: Class structure

RPN.hpp

#ifndef RPN_HPP
#define RPN_HPP

#include <stack>
#include <string>

class RPN {
private:
    std::stack<int> _stack;

    bool isOperator(char c) const;

public:
    RPN();
    RPN(const RPN& other);
    RPN& operator=(const RPN& other);
    ~RPN();

    int evaluate(const std::string& expression);
};

#endif

Stage 2: Core evaluation

RPN.cpp

#include "RPN.hpp"
#include <cctype>
#include <stdexcept>

bool RPN::isOperator(char c) const {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int RPN::evaluate(const std::string& expression) {
    // Clear stack from any previous run
    while (!_stack.empty()) {
        _stack.pop();
    }

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

        // Skip spaces
        if (c == ' ') {
            continue;
        }

        // Number: push to stack
        if (std::isdigit(c)) {
            _stack.push(c - '0');
        }
        // Operator: pop two, calculate, push result
        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();

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

    // Must have exactly one result
    if (_stack.size() != 1) {
        throw std::runtime_error("Error");
    }

    return _stack.top();
}

Line-by-Line Explanation

RPN evaluation trace:

Expression: "8 9 * 9 - 9 - 9 - 4 - 1 +"

Step | Token | Stack (bottom->top) | Action
-----|-------|---------------------|--------
1    | 8     | [8]                 | Push 8
2    | 9     | [8, 9]              | Push 9
3    | *     | [72]                | Pop 9,8; push 8*9=72
4    | 9     | [72, 9]             | Push 9
5    | -     | [63]                | Pop 9,72; push 72-9=63
6    | 9     | [63, 9]             | Push 9
7    | -     | [54]                | Pop 9,63; push 63-9=54
8    | 9     | [54, 9]             | Push 9
9    | -     | [45]                | Pop 9,54; push 54-9=45
10   | 4     | [45, 4]             | Push 4
11   | -     | [41]                | Pop 4,45; push 45-4=41
12   | 1     | [41, 1]             | Push 1
13   | +     | [42]                | Pop 1,41; push 41+1=42

Result: 42

Why pop b before a?

// For "5 3 -":
// Stack after pushes: [5, 3]  (3 on top)
int b = _stack.top(); _stack.pop();  // b = 3
int a = _stack.top(); _stack.pop();  // a = 5
result = a - b;  // 5 - 3 = 2 (correct!)

// If we did a - b wrong:
// result = b - a;  // 3 - 5 = -2 (wrong!)

Common Pitfalls

1. Wrong operand order:

// WRONG: Reversed operands
int a = _stack.top(); _stack.pop();
int b = _stack.top(); _stack.pop();
result = a - b;  // Wrong order!

// RIGHT: b is popped first (was on top)
int b = _stack.top(); _stack.pop();
int a = _stack.top(); _stack.pop();
result = a - b;  // Correct!

2. Not handling division by zero:

// WRONG: Crash on divide by zero
case '/': result = a / b; break;

// RIGHT: Check first
case '/':
    if (b == 0) throw std::runtime_error("Error");
    result = a / b;
    break;

3. Accepting multi-digit numbers:

// WRONG: Subject says single digits only
if (std::isdigit(c)) {
    // Parse full number...
}

// RIGHT: Single digit only
if (std::isdigit(c)) {
    _stack.push(c - '0');  // Only 0-9
}

4. Not validating final stack:

// WRONG: Accept any stack state
return _stack.top();

// RIGHT: Must have exactly one result
if (_stack.size() != 1) {
    throw std::runtime_error("Error");
}
return _stack.top();

Testing Tips

main.cpp

#include <iostream>
#include "RPN.hpp"

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "Usage: " << argv[0] << " <expression>" << std::endl;
        return 1;
    }

    RPN calculator;
    try {
        int result = calculator.evaluate(argv[1]);
        std::cout << result << std::endl;
    } catch (std::exception& e) {
        std::cerr << e.what() << std::endl;
        return 1;
    }

    return 0;
}

Test cases:

./RPN "8 9 * 9 - 9 - 9 - 4 - 1 +"  # 42
./RPN "7 7 * 7 -"                   # 42
./RPN "1 2 * 2 / 2 * 2 4 - +"      # 0
./RPN "(1 + 1)"                     # Error (parentheses not allowed)
./RPN "1 2 + +"                     # Error (not enough operands)
./RPN "1 2"                         # Error (no operator)
./RPN "5 0 /"                       # Error (division by zero)

Final Code

RPN.hpp

#ifndef RPN_HPP
#define RPN_HPP

#include <stack>
#include <string>

class RPN {
private:
    std::stack<int> _stack;
    bool isOperator(char c) const;

public:
    RPN();
    RPN(const RPN& other);
    RPN& operator=(const RPN& other);
    ~RPN();

    int evaluate(const std::string& expression);
};

#endif

RPN.cpp

#include "RPN.hpp"
#include <cctype>
#include <stdexcept>

RPN::RPN() {}
RPN::RPN(const RPN& other) : _stack(other._stack) {}
RPN& RPN::operator=(const RPN& other) {
    if (this != &other) _stack = other._stack;
    return *this;
}
RPN::~RPN() {}

bool RPN::isOperator(char c) const {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int RPN::evaluate(const std::string& expression) {
    while (!_stack.empty()) _stack.pop();

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

        if (c == ' ') continue;

        if (std::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();
}

---

Exercise 02: PmergeMe

Subject Analysis

Implement the Ford-Johnson merge-insertion sort algorithm:

• Take positive integers as arguments
• Sort using two different containers
• Display: before, after, time for each container
• Handle at least 3000 numbers

Output format:

Before: 3 5 9 7 4
After:  3 4 5 7 9
Time to process a range of 5 elements with std::vector : 0.00031 us
Time to process a range of 5 elements with std::deque  : 0.00014 us

Approach Strategy

Think before coding:

1. What is Ford-Johnson?

   • Also called “merge-insertion sort”
   • Minimizes comparisons through clever pairing
   • Uses binary insertion with Jacobsthal sequence

2. Simplified algorithm:

   1. Pair adjacent elements
   2. Put larger in "main chain", smaller in "pend"
   3. Recursively sort main chain
   4. Insert pend elements using binary search

3. Why two containers?

   • Subject requires performance comparison
   • vector: contiguous memory, cache-friendly
   • deque: fast insertion at both ends

Progressive Code Building

Stage 1: Class structure

PmergeMe.hpp

#ifndef PMERGEME_HPP
#define PMERGEME_HPP

#include <vector>
#include <deque>
#include <string>

class PmergeMe {
private:
    std::vector<int> _vec;
    std::deque<int>  _deq;

    void sortVector();
    void sortDeque();

public:
    PmergeMe();
    PmergeMe(const PmergeMe& other);
    PmergeMe& operator=(const PmergeMe& other);
    ~PmergeMe();

    void parseInput(int argc, char** argv);
    void sort();
    void displayBefore() const;
    void displayAfter() const;
};

#endif

Stage 2: Parse and validate input

PmergeMe.cpp - parsing

#include "PmergeMe.hpp"
#include <cstdlib>
#include <stdexcept>
#include <iostream>

void PmergeMe::parseInput(int argc, char** argv) {
    for (int i = 1; i < argc; i++) {
        char* endptr;
        long num = std::strtol(argv[i], &endptr, 10);

        if (*endptr != '\0') {
            throw std::runtime_error("Error: invalid input.");
        }
        if (num <= 0) {
            throw std::runtime_error("Error: only positive integers.");
        }
        if (num > 2147483647) {
            throw std::runtime_error("Error: integer overflow.");
        }

        _vec.push_back(static_cast<int>(num));
        _deq.push_back(static_cast<int>(num));
    }
}

Stage 3: Ford-Johnson for vector

PmergeMe.cpp - sortVector

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

    std::vector<int> larger, smaller;
    bool hasOdd = (_vec.size() % 2 != 0);
    int oddElement = hasOdd ? _vec.back() : 0;

    // Step 1: Pair elements
    size_t limit = hasOdd ? _vec.size() - 1 : _vec.size();
    for (size_t i = 0; i < limit; 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]);
        }
    }

    // Step 2: Recursively sort larger elements
    _vec = larger;
    sortVector();
    larger = _vec;

    // Step 3: Insert smaller elements 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]);
    }

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

    _vec = larger;
}

Stage 4: Timing

PmergeMe.cpp - sort with timing

#include <ctime>

void PmergeMe::sort() {
    // Time vector sort
    clock_t startVec = clock();
    sortVector();
    clock_t endVec = clock();
    double timeVec = (double)(endVec - startVec) / CLOCKS_PER_SEC * 1000000;

    // Time deque sort
    clock_t startDeq = clock();
    sortDeque();
    clock_t endDeq = clock();
    double timeDeq = (double)(endDeq - startDeq) / CLOCKS_PER_SEC * 1000000;

    std::cout << "Time to process a range of " << _vec.size()
              << " elements with std::vector : " << timeVec << " us" << std::endl;
    std::cout << "Time to process a range of " << _deq.size()
              << " elements with std::deque  : " << timeDeq << " us" << std::endl;
}

Line-by-Line Explanation

Ford-Johnson algorithm trace:

Input: [3, 5, 9, 7, 4, 1]

Step 1: Pair and separate
Pairs: (3,5) (9,7) (4,1)
Larger:  [5, 9, 4]
Smaller: [3, 7, 1]

Step 2: Recursively sort larger
[5, 9, 4] -> [4, 5, 9]  (after recursion)

Step 3: Insert smaller using binary search
Insert 3: [3, 4, 5, 9]
Insert 7: [3, 4, 5, 7, 9]
Insert 1: [1, 3, 4, 5, 7, 9]

Result: [1, 3, 4, 5, 7, 9]

Why lower_bound for insertion?

// lower_bound returns iterator to first element >= value
std::vector<int> v = {1, 3, 5, 7};

// Insert 4:
std::vector<int>::iterator pos = std::lower_bound(v.begin(), v.end(), 4);
// pos points to 5 (first element >= 4)
v.insert(pos, 4);
// v = {1, 3, 4, 5, 7}

Common Pitfalls

1. Not implementing actual Ford-Johnson:

// WRONG: Just using std::sort
void sortVector() {
    std::sort(_vec.begin(), _vec.end());
}

// RIGHT: Implement the pairing and recursive merge-insertion

2. Forgetting odd element:

// WRONG: Ignores odd element
for (size_t i = 0; i < _vec.size(); i += 2) {
    // Pairs only
}

// RIGHT: Handle odd element separately
bool hasOdd = (_vec.size() % 2 != 0);
int oddElement = hasOdd ? _vec.back() : 0;
size_t limit = hasOdd ? _vec.size() - 1 : _vec.size();

3. Timing the wrong thing:

// WRONG: Include parsing in timing
clock_t start = clock();
parseInput(argc, argv);  // Wrong!
sortVector();
clock_t end = clock();

// RIGHT: Only time the sort
parseInput(argc, argv);
clock_t start = clock();
sortVector();
clock_t end = clock();

4. Using same container:

// WRONG: Subject requires TWO different containers
std::vector<int> _data1;
std::vector<int> _data2;  // Both vectors!

// RIGHT: Different container types
std::vector<int> _vec;
std::deque<int>  _deq;

Testing Tips

# Generate test numbers
./PmergeMe 3 5 9 7 4

# Test with random numbers
./PmergeMe `shuf -i 1-100000 -n 3000 | tr "\n" " "`

# Verify sorting
./PmergeMe 5 4 3 2 1
# Should show: Before: 5 4 3 2 1
#              After:  1 2 3 4 5

Verification script:

#!/bin/bash
# Generate random numbers, sort, and verify
NUMS=$(shuf -i 1-10000 -n 100 | tr "\n" " ")
./PmergeMe $NUMS 2>&1 | head -2

# Compare with sort command
echo "Expected: $(echo $NUMS | tr " " "\n" | sort -n | tr "\n" " ")"

Final Code

PmergeMe.hpp

#ifndef PMERGEME_HPP
#define PMERGEME_HPP

#include <vector>
#include <deque>

class PmergeMe {
private:
    std::vector<int> _vec;
    std::deque<int>  _deq;

    void sortVector();
    void sortDeque();

public:
    PmergeMe();
    PmergeMe(const PmergeMe& other);
    PmergeMe& operator=(const PmergeMe& other);
    ~PmergeMe();

    void parseInput(int argc, char** argv);
    void sort();
    void displayBefore() const;
    void displayAfter() const;
};

#endif

main.cpp

#include <iostream>
#include "PmergeMe.hpp"

int main(int argc, char** argv) {
    if (argc < 2) {
        std::cerr << "Usage: " << argv[0] << " <numbers...>" << std::endl;
        return 1;
    }

    try {
        PmergeMe sorter;
        sorter.parseInput(argc, argv);
        sorter.displayBefore();
        sorter.sort();
        sorter.displayAfter();
    } catch (std::exception& e) {
        std::cerr << e.what() << std::endl;
        return 1;
    }

    return 0;
}

---

Module 09 Summary

Exercise	Container	Algorithm
ex00	std::map	lower_bound for date lookup
ex01	std::stack	RPN evaluation (LIFO)
ex02	vector + deque	Ford-Johnson merge-insertion

Key takeaways:

1. Choose containers wisely - each has strengths
2. STL algorithms - lower_bound, sort, find save time
3. Performance matters - measure with clock()
4. Validate input - robust error handling is essential

---

Quick Reference

Parsing Tips

// String to int
int n = std::atoi(str.c_str());

// String to float
float f = std::atof(str.c_str());

// Split string
size_t pos = str.find(delimiter);
std::string first = str.substr(0, pos);
std::string second = str.substr(pos + 1);

Timing

clock_t start = clock();
// ... code ...
clock_t end = clock();
double microseconds = (double)(end - start) / CLOCKS_PER_SEC * 1000000;

Binary Search (for insertion)

std::vector<int>::iterator pos = std::lower_bound(v.begin(), v.end(), value);
v.insert(pos, value);

---

Related Concepts

You’ve completed the C++ Piscine modules! Now prepare for the exam:

• Previous: Module 08: STL Containers - Review container fundamentals
• Next: Exam Rank 04 - Prepare for the practical exam