Reputation: 93
c++ Converting roman numerals to decimals
This program is a part of an exam I just took, that I had to write. I only got this far and couldn't get anywhere. Here is the prompt:"Write a Test Function toDecimal() that converts a roman numeral such as MMLXVII to it's decimal number representation. Use Main() to test the function. The toDecimal() function should have 2 arguments, the string array of roman numerals and a helper function. This helper function will return the numeric value of each of the letters used in roman numbers. Then convert the string arguments as so: Look at the first two characters,if the first is larger, convert the first and add it to the summation, then call the conversion function again with the second value and add both. IF the first character is lesser than the second subtract the first from the second, and add the result to the conversion of the string. without validation it will also convert strings like "IC". VAlidate the string arguement, if there is an error, call the error processing function. Provide at least two error processing functions and test toDecimal() with each. One could be adking the user to correct, the other may correct it."
I,X,C,M cannot be repeated more than 3 times in succession, D,L,V, can never be repeated in succession.I can only be subtracted from V and X,X can only be subtracted from L and C, C can only be subtracted from D and M. V, L, and D can never be subtracted.
I've lost about 2 days worth of sleep on this, tried writing it hundreds of different ways using and breaking the rules. This is the closest I've got on it.
#include <iostream>
#include <string>
#include <map>
#include <algorithm>
#include <cstring>
using namespace std;
bool checker(string roman);
// Adds each value of the roman numeral together
int toDecimal(string, bool* (*function)(string));
int convert(string roman, int i);
int main(){
string roman;
cout << "This program takes a roman numeral the user enters then converts it to decimal notation." << endl;
cout << "Enter a roman numeral: ";
cin >> roman;
transform(roman.begin(), roman.end(), roman.begin(), toupper);
cout << roman << " is equal to " << toDecimal(roman, *checker(roman)) << endl;
}
bool checker(string roman){
int length = roman.length();
for (int count = 0; count < length; count++){
string sub = roman.substr(count, count);
if(sub != "I" || sub != "V" || sub != "X" || sub != "L" || sub != "C" || sub != "D" || sub != "M"){
cout << "Error. Try Again"<< endl;
return false;
}
else if(convert(roman, count) == convert(roman, count-1) && convert(roman, count) == convert(roman, count+1)){
if (convert(roman,count) == 1 || convert(roman,count) == 10 || convert(roman,count) == 100 || convert(roman,count) == 1000)
if(convert(roman, count-1) == convert(roman, count-2) || convert(roman, count+1) == convert(roman, count+2)){
cout << "Error Try again" << endl;
return false;
}
else if (convert(roman,count) == 5 || convert(roman,count) == 50 || convert(roman,count) == 500){
cout << "Error Try again" << endl;
return false;
}
else return true;
}
}
return true;
}
int toDecimal(string s, bool*(checker) (string roman)){
/**map<char, int> roman;
roman['M'] = 1000;
roman['D'] = 500;
roman['C'] = 100;
roman['L'] = 50;
roman['X'] = 10;
roman['V'] = 5;
roman['I'] = 1;*/
checker(s);
int res = 0;
for (int i = 0; i < s.length() - 1; ++i){
int num = convert(s,i);
res += num;
/**if (roman[s[i]] < roman[s[i+1]])
res -= roman[s[i]];
else
res += roman[s[i]];
}
res += roman[s[s.size()-1]];*/}
return res;
}
int convert(string roman, int i){
enum romans {I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000};
int num = 0;
char c = roman[0];
switch(c){
case 'M':
num = M; break;
case 'D':
if(i + 1 != roman.size() && roman[i+1] == 'M'){
num = M - D;break;
}
else
num = D; break;
case 'C':
if(i + 1 != roman.size() && roman[i+1] == 'M' || roman[i+1] == 'D'){
if(roman[i+1] == 'M') num = M - C; break;
if(roman[i+1] == 'D') num = D - C; break;
}
else
num = C; break;
case 'L':
if(i + 1 != roman.size() && roman[i+1] == 'M' || roman[i+1] == 'D' || roman[i+1] == 'C'){
if(roman[i+1] == 'M') num = M - L; break;
if(roman[i+1] == 'D') num = D - L; break;
if(roman[i+1] == 'C') num = C - L; break;
}
else
num = L; break;
case 'X':
if(i + 1 != roman.size() && roman[i+1] == 'M' || roman[i+1] == 'D' || roman[i+1] == 'C'|| roman[i+1] == 'L'){
if(roman[i+1] == 'M') num = M - X; break;
if(roman[i+1] == 'D') num = D - X; break;
if(roman[i+1] == 'C') num = C - X; break;
if(roman[i+1] == 'L') num = C - X; break;
}
num = X; break;
case 'V':
if(i + 1 != roman.size() && roman[i+1] == 'M' || roman[i+1] == 'D' || roman[i+1] == 'C'|| roman[i+1] == 'L' || roman[i+1] == 'X'){
if(roman[i+1] == 'M') num = M - V; break;
if(roman[i+1] == 'D') num = D - V; break;
if(roman[i+1] == 'C') num = C - V; break;
if(roman[i+1] == 'L') num = L - V; break;
if(roman[i+1] == 'X') num = X - V; break;
}
num = V; break;
case 'I':
if ( i + 1 != roman.size() && roman[i + 1] != 'I'){
if(roman[i+1] == 'M') num = M - I; break;
if(roman[i+1] == 'D') num = D - I; break;
if(roman[i+1] == 'C') num = C - I; break;
if(roman[i+1] == 'L') num = L - I; break;
if(roman[i+1] == 'X') num = X - I; break;
}
num =1; break;
}
return num;
}
** I have added the help of people on here. This is an edit to show an progress/congress.
Upvotes: 3
Views: 17409
Answers (5)
Reputation: 2186
This answer is an appendix to the answer posted here.
It provides source code listings for the program in that answer.
The appendix was created because there was not enough room in the original answer to post the five files it uses. Posting this code in the original answer triggers a Stack Overflow error: "character limit exceeded."
main.cpp
// main.cpp
#include <iomanip>
#include <iostream>
#include <limits>
#include <stdexcept>
#include <string>
#include "RomanNumeral.h"
#include "tbx.utility.h"
namespace
{
bool test_valid_Roman_numerals(std::ostream& log)
{
log << "Round-trip Conversion of Every Valid Roman Numeral\n\n";
int n_failures{};
for (int n{ 1 }; n <= 3999; ++n)
{
auto r{ roman_numeral::fromInteger(n) };
auto num{ roman_numeral::toDecimal(r) };
if (num != n)
++n_failures;
}
log << " Failure count: " << n_failures << "\n\n";
return n_failures == 0;
}
bool test_invalid_Roman_numeral(std::ostream& log, std::string const& r)
{
auto const d = roman_numeral::toDecimal(r);
auto const v = roman_numeral::isValid(r);
log << " " << std::left << std::setw(11) << std::quoted(r)
<< " " << std::right << std::setw(9) << d
<< " " << std::left << std::boolalpha << v
<< '\n';
return !v;
}
bool test_invalid_Roman_numerals(std::ostream& log)
{
log << "Detect Invalid Roman Numerals\n\n"
<< " " << "Roman\n"
<< " " << std::left << std::setw(11) << "Numeral"
<< " " << std::right << std::setw(9) << "toDecimal"
<< " " << std::left << "isValid"
<< "\n\n";
tbx::OneTimeToggle pass_all{ true };
pass_all = test_invalid_Roman_numeral(log, ""); // empty string
pass_all = test_invalid_Roman_numeral(log, "garbage"); // yeah, garbage
pass_all = test_invalid_Roman_numeral(log, "I I"); // space between symbols
pass_all = test_invalid_Roman_numeral(log, "IL"); // invalid subtraction
pass_all = test_invalid_Roman_numeral(log, "IC");
pass_all = test_invalid_Roman_numeral(log, "ID");
pass_all = test_invalid_Roman_numeral(log, "IM");
pass_all = test_invalid_Roman_numeral(log, "VX"); // only 'I`, 'X', and 'C'
pass_all = test_invalid_Roman_numeral(log, "VL"); // can be subtracted
pass_all = test_invalid_Roman_numeral(log, "VC");
pass_all = test_invalid_Roman_numeral(log, "VD");
pass_all = test_invalid_Roman_numeral(log, "VM");
pass_all = test_invalid_Roman_numeral(log, "XD");
pass_all = test_invalid_Roman_numeral(log, "XM");
pass_all = test_invalid_Roman_numeral(log, "LC");
pass_all = test_invalid_Roman_numeral(log, "LD");
pass_all = test_invalid_Roman_numeral(log, "LM");
pass_all = test_invalid_Roman_numeral(log, "DM");
pass_all = test_invalid_Roman_numeral(log, "IVIV"); // `I`, `X`, and `C` can only
pass_all = test_invalid_Roman_numeral(log, "IXIX"); // be subtracted once in any
pass_all = test_invalid_Roman_numeral(log, "IXIV"); // given Roman numeral
pass_all = test_invalid_Roman_numeral(log, "IVIX");
pass_all = test_invalid_Roman_numeral(log, "XCXL");
pass_all = test_invalid_Roman_numeral(log, "CDCM");
pass_all = test_invalid_Roman_numeral(log, "VV"); // only 'I`, 'X', 'C' and 'M'
pass_all = test_invalid_Roman_numeral(log, "LL"); // can be repeated
pass_all = test_invalid_Roman_numeral(log, "DD");
pass_all = test_invalid_Roman_numeral(log, "IIII"); // too many repeats
pass_all = test_invalid_Roman_numeral(log, "XXXX");
pass_all = test_invalid_Roman_numeral(log, "CCCC");
pass_all = test_invalid_Roman_numeral(log, "MMMM");
pass_all = test_invalid_Roman_numeral(log, "IXX"); // repetition and subtraction
pass_all = test_invalid_Roman_numeral(log, "XCC"); // cannot be combined
pass_all = test_invalid_Roman_numeral(log, "CMM");
pass_all = test_invalid_Roman_numeral(log, "IIV"); // "threshold" not increasing
pass_all = test_invalid_Roman_numeral(log, "IIX");
pass_all = test_invalid_Roman_numeral(log, "XXL");
pass_all = test_invalid_Roman_numeral(log, "XXC");
pass_all = test_invalid_Roman_numeral(log, "CCD");
pass_all = test_invalid_Roman_numeral(log, "CCM");
pass_all = test_invalid_Roman_numeral(log, "VIX");
pass_all = test_invalid_Roman_numeral(log, "LXC");
pass_all = test_invalid_Roman_numeral(log, "DCM");
log << "\n\n";
return pass_all;
}
int get_int(
std::string const& prompt,
int const min,
int const max,
std::istream& ist,
std::ostream& ost)
{
for (;;)
{
ost << prompt;
if (int n{}; !(std::cin >> n))
{
ost << "Invalid entry. Please reenter.\n\n";
ist.clear();
ist.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}
else if (n < min || n > max)
{
ost << "Invalid entry. Please reenter.\n"
<< "Entries must be between " << min << " and " << max << ".\n\n";
}
else
{
ist.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
return n;
}
}
}
std::string get_Roman_numeral(std::istream& ist, std::ostream& ost)
{
std::string r;
for (;;)
{
ost << "Enter a roman numeral: ";
ist >> r;
ost.put('\n');
if (roman_numeral::isValid(r))
break;
ost << "Invalid entry. Please reenter.\n\n";
}
ist.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
return r;
}
void select_error_processing_function(
std::ostream& log,
std::istream& ist,
std::string& r)
{
char const* const menu
{
" is not a valid Roman numeral."
"\n"
"\nSelect an error processing function:"
"\n"
"\n 1. Reenter the Roman numeral"
"\n 2. Throw an exception"
"\n\n"
};
enum { ReenterRomanNumeral = 1, ThrowException };
log << r << menu;
int choice{ get_int("Choice? ", 1, 2, ist, log) };
log.put('\n');
switch (choice)
{
case ReenterRomanNumeral:
r = get_Roman_numeral(ist, log);
break;
case ThrowException:
throw std::runtime_error("Malformed Roman numeral: \"" + r + '"');
default:
// std::unreachable();
break;
}
}
bool test_Roman_numeral_entered_by_user(
std::istream& ist,
std::ostream& log)
{
log << "Roman Numeral to Integer Converter\n\n"
" Enter a Roman numeral: ";
std::string r;
std::getline(ist, r);
log.put('\n');
int num{};
while ((num = roman_numeral::toDecimal(r)) == 0)
{
try { select_error_processing_function(log, ist, r); }
catch (std::exception const& e) {
log << " Exception caught in function "
"`test_Roman_numeral_entered_by_user`: "
<< e.what() << "\n\n";
return false;
}
}
log << " " << r << " = " << num << "\n\n";
return true;
}
}
int main()
{
auto& log{ std::cout }; // substitute log files, as needed
auto& ist{ std::cin };
int exit_code{}, shift{};
// Each of the three tests gets its own bit in the `exit_code`,
// where 0-valued bits indicate success.
exit_code |= test_valid_Roman_numerals(log) ? 0 : 1 << shift++;
exit_code |= test_invalid_Roman_numerals(log) ? 0 : 1 << shift++;
exit_code |= test_Roman_numeral_entered_by_user(ist, log) ? 0 : 1 << shift++;
return exit_code; // between 0 and 7
}
// end file: main.cpp
RomanNumeral.h
#pragma once
// RomanNumeral.h
// Functions designed per the specification at Stack Overflow
// https://stackoverflow.com/q/17724887/22193627
#include <string>
namespace roman_numeral
{
bool isValid(std::string const& r);
int value_from_map(char const symbol);
int value_from_switch(char const symbol);
int toDecimal(
std::string r,
int (*value)(char const symbol) = value_from_map);
std::string fromInteger(int const n);
}
// end file: RomanNumeral.h
RomanNumeral.cpp
// RomanNumeral.cpp
#include <cstddef>
#include <iterator>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include "RomanNumeral.h"
#include "tbx.utility.h"
namespace
{
//==================================================================
// is_repeatable
//==================================================================
bool is_repeatable(char const i)
{
return i == 'I'
|| i == 'X'
|| i == 'C'
|| i == 'M';
}
//==================================================================
// is_subtractive
//==================================================================
bool is_subtractive(char const i, char const vx)
{
return i == 'I' && vx == 'V'
|| i == 'I' && vx == 'X'
|| i == 'X' && vx == 'L'
|| i == 'X' && vx == 'C'
|| i == 'C' && vx == 'D'
|| i == 'C' && vx == 'M';
}
}
namespace roman_numeral
{
//==================================================================
// fromInteger
//==================================================================
std::string fromInteger(int const n)
{
if (n < 1 || n > 3999)
return ""; // sentinel value signals failure
static constexpr char const* const I[]{ "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" };
static constexpr char const* const X[]{ "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" };
static constexpr char const* const C[]{ "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" };
static constexpr char const* const M[]{ "", "M", "MM", "MMM" };
auto const v{ static_cast<std::size_t>(n) };
enum : std::size_t { fifteen = 15u };
std::string r;
r.reserve(fifteen); // room enough for "MMMDCCCLXXXVIII", the widest Roman numeral
r = M[v / 1000u];
r += C[(v % 1000u) / 100u];
r += X[(v % 100u) / 10u];
r += I[v % 10u];;
return r;
}
//==================================================================
// isValid
//==================================================================
bool isValid(std::string const& r)
{
return toDecimal(r, value_from_map) != 0;
}
//==================================================================
// toDecimal
//==================================================================
int toDecimal(std::string r, int (*value)(char const symbol))
{
r = tbx::to_upper(tbx::trim_whitespace(r));
// Fail if any of the characters in `r` are not valid Roman
// numeral symbols.
for (auto const& c : r)
if (value(c) == 0)
return 0; // sentinel value signals failure
// Handle short strings as special cases.
enum : std::size_t { zero, one };
switch (r.length())
{
case zero: return 0; // sentinel value signals failure
case one: return value(r.front());
default: break;
}
// Loop, scanning string `r` from right-to-left.
auto trailer{ r.crbegin() };
auto t{ *trailer };
auto vt{ value(t) };
auto leader{ std::next(r.crbegin()) };
auto l{ *leader };
auto vl{ value(l) };
int sum{ vt };
int n_repeats{ 1 };
int threshold{ vt };
std::unordered_set<char> already_subtracted;
while (leader != r.crend())
{
l = *leader; vl = value(l);
t = *trailer; vt = value(t);
if (vl < threshold)
{
if (!is_subtractive(l, t) || already_subtracted.count(l) || n_repeats != 1)
return 0; // sentinel value signals failure
sum -= vl;
already_subtracted.insert(l);
n_repeats = 0;
threshold = 10 * vl;
}
else if (vl == threshold)
{
if (!is_repeatable(l) || ++n_repeats > 3)
return 0; // sentinel value signals failure
sum += vl;
}
else // vl > threshold
{
sum += vl;
n_repeats = 1;
threshold = vl;
}
++leader; ++trailer;
}
return sum;
}
//==================================================================
// value_from_map
//==================================================================
int value_from_map(char const symbol)
{
static const std::unordered_map<char, int> values =
{
{ 'I', 1 },
{ 'V', 5 },
{ 'X', 10 },
{ 'L', 50 },
{ 'C', 100 },
{ 'D', 500 },
{ 'M', 1000 }
};
if (auto const it{ values.find(symbol) }; it == values.end())
return 0; // sentinel value signals failure
else
return it->second;
}
//==================================================================
// value_from_switch
//==================================================================
int value_from_switch(char const symbol)
{
switch (symbol)
{
case 'I': return 1;
case 'V': return 5;
case 'X': return 10;
case 'L': return 50;
case 'C': return 100;
case 'D': return 500;
case 'M': return 1000;
default: break;
}
return 0; // sentinel value signals failure
}
}
// end file: RomanNumeral.cpp
tbx.utility.h
#pragma once
// tbx.utility.h
#include <string>
#include <string_view>
namespace tbx
{
auto to_upper(std::string s) noexcept -> std::string;
void to_upper_in_place(std::string& s) noexcept;
auto trim_whitespace(std::string const& s) -> std::string;
auto trim_whitespace_view(std::string_view sv) noexcept -> std::string_view;
//==================================================================
// OneTimeToggle
//==================================================================
class OneTimeToggle
{
bool const initial_state;
bool state;
public:
constexpr OneTimeToggle(bool const b) noexcept
: initial_state{ b }, state{ b }
{}
constexpr bool operator() () const noexcept {
return state;
}
constexpr operator bool() const noexcept {
return state;
}
constexpr OneTimeToggle& operator= (bool const b) noexcept {
if (b != initial_state)
state = b;
return *this;
}
constexpr void reset() {
state = initial_state;
}
};
}
// end file: tbx.utility.h
tbx.utility.cpp
// tbx.utility.cpp
#include <algorithm>
#include <cctype>
#include <string>
#include <string_view>
#include "tbx.utility.h"
namespace tbx
{
//==================================================================
// to_upper
//==================================================================
std::string to_upper(std::string s) noexcept
{
tbx::to_upper_in_place(s);
return s;
}
//==================================================================
// to_upper_in_place
//==================================================================
void to_upper_in_place(std::string& s) noexcept
{
std::transform(s.begin(), s.end(), s.begin(),
[](unsigned char c) {
return static_cast<char>(std::toupper(c));
}
);
}
//==================================================================
// trim_whitespace
//==================================================================
auto trim_whitespace(std::string const& s) -> std::string
{
return std::string{ trim_whitespace_view(s) };
}
//==================================================================
// trim_whitespace_view
//==================================================================
auto trim_whitespace_view(std::string_view sv) noexcept -> std::string_view
{
// Trim leading and trailing whitespace from string_view `sv`.
enum : std::string_view::size_type { zero, one };
auto const first{ sv.find_first_not_of(" \f\n\r\t\v") };
if (first == std::string_view::npos)
return sv.substr(zero, zero);
auto const last{ sv.find_last_not_of(" \f\n\r\t\v") };
return sv.substr(first, (last - first + one));
}
}
// end file: tbx.utility.cpp
Upvotes: -2
Reputation: 2186
None of the answers provided so far satisfy the requirement to detect invalid Roman numerals. This answer does! If you want to skip ahead, you will find the finished version of function toDecimal at the end of this answer.
At this late date (2024), it should be okay to solve this exam problem, without compromising the OP's academic integrity.
The top-down solution presented here uses five files:
- main.cpp – Driver and test code. Error processing functions.
- RomanNumeral.h – Declares Roman numeral functions.
- RomanNumeral.cpp – Implements Roman numeral functions.
- tbx.utility.h – Declares utility functions. These are previously written functions from my "toolbox." Of the many functions provided by this header, only three are used by this program:
OneTimeToggle,to_upper, andtrim_whitespace. - tbx.utility.cpp – Implements utility functions. The abridged version here includes only the three functions mentioned above.
Roman numeral functions are placed in namespace roman_numeral. Although longer than most namespace names, it makes for readable, self-documenting code. We like names such as roman_numeral::isValid and roman_numeral::toDecimal.
Here is the finished code for file RomanNumeral.h:
#pragma once
// RomanNumeral.h
// Functions designed per the specification at Stack Overflow
// https://stackoverflow.com/q/17724887/22193627
#include <string>
namespace roman_numeral
{
bool isValid(std::string const& r);
int value_from_map(char const symbol);
int value_from_switch(char const symbol);
int toDecimal(
std::string r,
int (*value)(char const symbol) = value_from_map);
std::string fromInteger(int const n);
}
// end file: RomanNumeral.h
The problem spec requires that function toDecimal accept a pointer to a function that converts Roman numeral letters to their integer equivalents. This is unusual, because it brings an implementation detail into the interface.
Given the declarations above, function toDecimal might be invoked as follows:
auto const year = roman_numeral::toDecimal("MMXXIV", value_from_map); // 2024
auto const whoops = roman_numeral::toDecimal("garbage", value_from_switch); // 0
Function toDecimal returns 0 when it fails, so we expect variable whoops to have that value.
In order to allow a more natural syntax, parameter value in function toDecimal was given a default value. Thus, it is not necessary to specify value_from_map or value_from_switch when calling toDecimal.
auto const year = roman_numeral::toDecimal("MMXXIV"); // 2024
auto const whoops = roman_numeral::toDecimal("garbage"); // 0
Function roman_numeral::fromInteger, declared above, is not required by the problem spec. We include it, however, so that "round-trip" conversions, from integer to Roman numeral, and back again, can be made during testing.
Stub functions and test routines
Top-down design uses stub functions as placeholders for functions that will be coded later on. A stub is an empty or minimal function that returns a fake (but realistic) value that can be used by callers during development.
Here are the stubs for RomanNumeral.cpp. The only finished function is isValid, which we will be using subsequently.
// RomanNumeral.cpp
#include <cstddef>
#include <iterator>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include "RomanNumeral.h"
#include "tbx.utility.h"
namespace
{
// Helper functions will be placed in an anonymous namespace,
// so that they are not exported to the linker.
}
namespace roman_numeral
{
//==================================================================
// fromInteger
//==================================================================
std::string fromInteger(int const n)
{
return ""; // sentinel value signals failure
}
//==================================================================
// isValid
//==================================================================
bool isValid(std::string const& r)
{
return toDecimal(r, value_from_map) != 0;
}
//==================================================================
// toDecimal
//==================================================================
int toDecimal(std::string r, int (*value)(char const symbol))
{
return 0; // sentinel value signals failure
}
//==================================================================
// value_from_map
//==================================================================
int value_from_map(char const symbol)
{
return 0; // sentinel value signals failure
}
//==================================================================
// value_from_switch
//==================================================================
int value_from_switch(char const symbol)
{
return 0; // sentinel value signals failure
}
}
// end file: RomanNumeral.cpp
Function main can also be coded with stubs, but notice, our testing strategy is completely "implemented," even at this early stage.
// main.cpp
#include <iomanip>
#include <iostream>
#include <limits>
#include <stdexcept>
#include <string>
#include "RomanNumeral.h"
#include "tbx.utility.h"
namespace
{
bool test_valid_Roman_numerals(std::ostream& log)
{
return false;
}
bool test_invalid_Roman_numeral(std::ostream& log, std::string const& r)
{
return false;
}
bool test_invalid_Roman_numerals(std::ostream& log)
{
return false;
}
bool test_Roman_numeral_entered_by_user(
std::istream& ist,
std::ostream& log)
{
return false;
}
}
int main()
{
auto& log{ std::cout }; // substitute log files, as needed
auto& ist{ std::cin };
int exit_code{}, shift{};
// Each of the three tests gets its own bit in the `exit_code`,
// where 0-valued bits indicate success.
exit_code |= test_valid_Roman_numerals(log) ? 0 : 1 << shift++;
exit_code |= test_invalid_Roman_numerals(log) ? 0 : 1 << shift++;
exit_code |= test_Roman_numeral_entered_by_user(ist, log) ? 0 : 1 << shift++;
return exit_code; // between 0 and 7
}
// end file: main.cpp
We plan to code function test_Roman_numeral_entered_by_user last. That way, we don't have to type a Roman numeral every time we run the program.
And, by the way, the program does run. All three tests failed, and the exit_code was 7.
Round-trip conversion of every valid Roman numeral
Using the standard form for Roman numerals, the symbols I, V, X, L, C, D, and M produce values between 1 and 3,999. There are so few that it makes sense to test them all.
Function test_valid_Roman_numerals performs a round-trip conversion of each one, and counts the number of failures.
bool test_valid_Roman_numerals(std::ostream& log)
{
log << "Round-trip Conversion of Every Valid Roman Numeral\n\n";
int n_failures{};
for (int n{ 1 }; n <= 3999; ++n)
{
auto r{ roman_numeral::fromInteger(n) };
auto num{ roman_numeral::toDecimal(r) };
if (num != n)
++n_failures;
}
log << " Failure count: " << n_failures << "\n\n";
return n_failures == 0;
}
Once again, we can compile and run the program, which is one of the main advantages of top-down design. The program runs, from day one. The stub for function toDecimal still returns 0 in all cases, so the failure count for this run was 3999.
A bevy of invalid Roman numerals
Function test_invalid_Roman_numerals attempts to convert a host of invalid Roman numerals. Comments suggest what is wrong in each case.
tbx::OneTimeToggle is a class from tbx.utility.h. It's a toggle that can only be flipped once. It is constructed with the value true. If any of the tests below fails, it will flip to false, and once it flips, it cannot be flipped back.
bool test_invalid_Roman_numeral(std::ostream& log, std::string const& r)
{
auto const d = roman_numeral::toDecimal(r);
auto const v = roman_numeral::isValid(r);
log << " " << std::left << std::setw(11) << std::quoted(r)
<< " " << std::right << std::setw(9) << d
<< " " << std::left << std::boolalpha << v
<< '\n';
return !v;
}
bool test_invalid_Roman_numerals(std::ostream& log)
{
log << "Detect Invalid Roman Numerals\n\n"
<< " " << "Roman\n"
<< " " << std::left << std::setw(11) << "Numeral"
<< " " << std::right << std::setw(9) << "toDecimal"
<< " " << std::left << "isValid"
<< "\n\n";
tbx::OneTimeToggle pass_all{ true };
pass_all = test_invalid_Roman_numeral(log, ""); // empty string
pass_all = test_invalid_Roman_numeral(log, "garbage"); // yeah, garbage
pass_all = test_invalid_Roman_numeral(log, "I I"); // space between symbols
pass_all = test_invalid_Roman_numeral(log, "IL"); // invalid subtraction
pass_all = test_invalid_Roman_numeral(log, "IC");
pass_all = test_invalid_Roman_numeral(log, "ID");
pass_all = test_invalid_Roman_numeral(log, "IM");
pass_all = test_invalid_Roman_numeral(log, "VX"); // only 'I`, 'X', and 'C'
pass_all = test_invalid_Roman_numeral(log, "VL"); // can be subtracted
pass_all = test_invalid_Roman_numeral(log, "VC");
pass_all = test_invalid_Roman_numeral(log, "VD");
pass_all = test_invalid_Roman_numeral(log, "VM");
pass_all = test_invalid_Roman_numeral(log, "XD");
pass_all = test_invalid_Roman_numeral(log, "XM");
pass_all = test_invalid_Roman_numeral(log, "LC");
pass_all = test_invalid_Roman_numeral(log, "LD");
pass_all = test_invalid_Roman_numeral(log, "LM");
pass_all = test_invalid_Roman_numeral(log, "DM");
pass_all = test_invalid_Roman_numeral(log, "IVIV"); // `I`, `X`, and `C` can only
pass_all = test_invalid_Roman_numeral(log, "IXIX"); // be subtracted once in any
pass_all = test_invalid_Roman_numeral(log, "IXIV"); // given Roman numeral
pass_all = test_invalid_Roman_numeral(log, "IVIX");
pass_all = test_invalid_Roman_numeral(log, "XCXL");
pass_all = test_invalid_Roman_numeral(log, "CDCM");
pass_all = test_invalid_Roman_numeral(log, "VV"); // only 'I`, 'X', 'C' and 'M'
pass_all = test_invalid_Roman_numeral(log, "LL"); // can be repeated
pass_all = test_invalid_Roman_numeral(log, "DD");
pass_all = test_invalid_Roman_numeral(log, "IIII"); // too many repeats
pass_all = test_invalid_Roman_numeral(log, "XXXX");
pass_all = test_invalid_Roman_numeral(log, "CCCC");
pass_all = test_invalid_Roman_numeral(log, "MMMM");
pass_all = test_invalid_Roman_numeral(log, "IXX"); // repetition and subtraction
pass_all = test_invalid_Roman_numeral(log, "XCC"); // cannot be combined
pass_all = test_invalid_Roman_numeral(log, "CMM");
pass_all = test_invalid_Roman_numeral(log, "IIV"); // "threshold" not increasing
pass_all = test_invalid_Roman_numeral(log, "IIX");
pass_all = test_invalid_Roman_numeral(log, "XXL");
pass_all = test_invalid_Roman_numeral(log, "XXC");
pass_all = test_invalid_Roman_numeral(log, "CCD");
pass_all = test_invalid_Roman_numeral(log, "CCM");
pass_all = test_invalid_Roman_numeral(log, "VIX");
pass_all = test_invalid_Roman_numeral(log, "LXC");
pass_all = test_invalid_Roman_numeral(log, "DCM");
log << "\n\n";
return pass_all;
}
When the program was run, toDecimal returned 0 for each invalid Roman numeral, and, correspondingly, isValid returned false for each one, as well.
At this point, the main test routines are complete.
Function test_Roman_numeral_entered_by_user still remains as a stub, but that was our plan. You can see its source code in the appendix to this answer.
Test-driven design
The top-down design used here incorporates testing as an integral part of the design process. It is not an accident that the test routines were finished, before any attempt at coding function toDecimal was made.
In subsequent stages, toDecimal will be given the naive implementation used by other posters here (and all across the Interwebs). The result will fail spectacularly when run against invalid Roman numerals.
With failure data in hand, the definition of toDecimal will be successively refined, removing the failures one by one. Without the test data, this would be impossible. In total, five iterations of function toDecimal will be needed before the last failure has been eliminated.
Note that this design process is only as good as the test data. It is possible that there are failure modes that are not revealed by the test data. At this point, that possibility is remote, but it exists, nonetheless.
If a new failure mode is discovered in the future, then the offending (invalid) Roman numeral strings will be added to the test data, and new round of refinement applied to function toDecimal.
Function roman_numeral::fromInteger
Function roman_numeral::fromInteger converts one place at a time, using a simple lookup strategy.
The digit in a given place is used as a subscript into a lookup array. The digit in the hundreds place, for instance, is found as (n % 1000) / 100. The digits in other places are found in a similar manner.
std::string fromInteger(int const n)
{
if (n < 1 || n > 3999)
return ""; // sentinel value signals failure
static constexpr char const* const I[]{ "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" };
static constexpr char const* const X[]{ "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" };
static constexpr char const* const C[]{ "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" };
static constexpr char const* const M[]{ "", "M", "MM", "MMM" };
auto const v{ static_cast<std::size_t>(n) };
enum : std::size_t { fifteen = 15u };
std::string r;
r.reserve(fifteen); // room enough for "MMMDCCCLXXXVIII", the widest Roman numeral
r = M[v / 1000u];
r += C[(v % 1000u) / 100u];
r += X[(v % 100u) / 10u];
r += I[v % 10u];;
return r;
}
Functions value_from_map and value_from_switch
These functions return 0 when they fail.
int value_from_map(char const symbol)
{
static const std::unordered_map<char, int> values =
{
{ 'I', 1 },
{ 'V', 5 },
{ 'X', 10 },
{ 'L', 50 },
{ 'C', 100 },
{ 'D', 500 },
{ 'M', 1000 }
};
if (auto const it{ values.find(symbol) }; it == values.end())
return 0; // sentinel value signals failure
else
return it->second;
}
int value_from_switch(char const symbol)
{
switch (symbol)
{
case 'I': return 1;
case 'V': return 5;
case 'X': return 10;
case 'L': return 50;
case 'C': return 100;
case 'D': return 500;
case 'M': return 1000;
default: break;
}
return 0; // sentinel value signals failure
}
The main show: roman_numeral::toDecimal
The most popular algorithm for converting Roman numeral strings into integers is to scan across them, from right-to-left, and sum the values of the symbols encountered. The exception occurs when the value of a symbol is less than the value of the symbol that follows it. In that case the value is subtracted from the sum.
In the code below, short strings (of length 0 and 1) are handled as special cases, before entering a loop that sums the values. In the loop, two reverse iterators, leader and trailer, scan across the Roman numeral string (from right-to-left). *trailer is the character that follows *leader.
When the value of *leader is less than the value of *trailer, the value of *leader is subtracted from the sum. Otherwise, it is added.
int toDecimal(std::string r, int (*value)(char const symbol))
{
r = tbx::to_upper(tbx::trim_whitespace(r));
// Fail if any of the characters in `r` are not valid Roman
// numeral symbols.
for (auto const& c : r)
if (value(c) == 0)
return 0; // sentinel value signals failure
// Handle short strings as special cases.
enum : std::size_t { zero, one };
switch (r.length())
{
case zero: return 0; // sentinel value signals failure
case one: return value(r.front());
default: break;
}
// Loop scans string `r` from right-to-left.
auto trailer{ r.crbegin() };
auto t{ *trailer };
auto vt{ value(t) };
auto leader{ std::next(r.crbegin()) };
auto l{ *leader };
auto vl{ value(l) };
int sum{ vt };
while (leader != r.crend())
{
l = *leader; vl = value(l);
t = *trailer; vt = value(t);
if (vl < vt)
{
sum -= vl;
}
else if (vl == vt)
{
sum += vl;
}
else // vl > vt
{
sum += vl;
}
++leader; ++trailer;
}
return sum;
}
This is a routine that works well with valid Roman numerals.
Note that the if-else-if statements that compare vl and vt could be more compactly coded, or even replaced with a ternary expression. We use this form, however, because more code will be added below.
Atrocious handling of malformed Roman numerals
The test routines are now doing their jobs. All valid Roman numerals pass through the round-trip conversion sucessfully. Few, however, of the malformed Roman numerals are detected as invalid.
The decimal values below are similar to those produced by the routines found in the other answers posted for this question.
Round-trip Conversion of Every Valid Roman Numeral
Failure count: 0
Detect Invalid Roman Numerals
Roman
Numeral toDecimal isValid
"" 0 false
"garbage" 0 false
"I I" 0 false
"IL" 49 true
"IC" 99 true
"ID" 499 true
"IM" 999 true
"VX" 5 true
"VL" 45 true
"VC" 95 true
"VD" 495 true
"VM" 995 true
"XD" 490 true
"XM" 990 true
"LC" 50 true
"LD" 450 true
"LM" 950 true
"DM" 500 true
"IVIV" 8 true
"IXIX" 18 true
"IXIV" 13 true
"IVIX" 13 true
"XCXL" 130 true
"CDCM" 1300 true
"VV" 10 true
"LL" 100 true
"DD" 1000 true
"IIII" 4 true
"XXXX" 40 true
"CCCC" 400 true
"MMMM" 4000 true
"IXX" 19 true
"XCC" 190 true
"CMM" 1900 true
"IIV" 5 true
"IIX" 10 true
"XXL" 50 true
"XXC" 100 true
"CCD" 500 true
"CCM" 1000 true
"VIX" 14 true
"LXC" 140 true
"DCM" 1400 true
Refinement 1: Restricting subtractive forms
There are only six valid subtractive pairs. They are: 'IV, IX, XL, XC, CD, and CM. Other forms, such as ICandXD`, are invalid.
Function is_subtractive returns true when its two arguments form a valid subtractive pair. It resides in an anonymous namespace within file RomanNumeral.cpp, so that it won't be exported to the linker.
namespace
{
bool is_subtractive(char const i, char const vx)
{
return i == 'I' && vx == 'V'
|| i == 'I' && vx == 'X'
|| i == 'X' && vx == 'L'
|| i == 'X' && vx == 'C'
|| i == 'C' && vx == 'D'
|| i == 'C' && vx == 'M';
}
}
Function is_subtractive should be called before subtracting from the sum in function toDecimal.
if (vl < vt)
{
if (!is_subtractive(l, t))
return 0; // sentinel value signals failure
sum -= vl;
}
else if (vl == vt)
{
sum += vl;
}
else // vl > threshold
{
sum += vl;
}
With this change, 15 more invalid Roman numerals are detected (and rejected).
Detect Invalid Roman Numerals
Roman
Numeral toDecimal isValid
"IL" 0 false
"IC" 0 false
"ID" 0 false
"IM" 0 false
"VX" 0 false
"VL" 0 false
"VC" 0 false
"VD" 0 false
"VM" 0 false
"XD" 0 false
"XM" 0 false
"LC" 0 false
"LD" 0 false
"LM" 0 false
"DM" 0 false
Refinement 2: One bite at subtraction
I, X, and C can each be subtracted only once within a Roman numeral.
Thus, IXIV is invalid, because I can only be subtracted once.
MCMXLIV, however, is fine, because: I is subtracted only once, X is subtracted only once, and C is subtracted only once.
Using an unordered_set is a good way to keep track of which symbols have already been subtracted.
std::unordered_set<char> already_subtracted;
while (leader != r.crend())
{
l = *leader; vl = value(l);
t = *trailer; vt = value(t);
if (vl < vt)
{
if (!is_subtractive(l, t) || already_subtracted.count(l))
return 0; // sentinel value signals failure
sum -= vl;
already_subtracted.insert(l);
}
else if (vl == vt)
{
sum += vl;
}
else // vl > threshold
{
sum += vl;
}
++leader; ++trailer;
}
This gets rid of an additional six of the invalid Roman numerals.
Detect Invalid Roman Numerals
Roman
Numeral toDecimal isValid
"IVIV" 0 false
"IXIX" 0 false
"IXIV" 0 false
"IVIX" 0 false
"XCXL" 0 false
"CDCM" 0 false
Refinement 3: V, L, and D can never be repeated.
I, X, C, and M are the only symbols that can be repeated. This fact is encoded in function is_repeatable.
namespace
{
bool is_repeatable(char const i)
{
return i == 'I'
|| i == 'X'
|| i == 'C'
|| i == 'M';
}
}
Adding this to the if-statement in function toDecimal gives:
if (vl < vt)
{
if (!is_subtractive(l, t) || already_subtracted.count(l))
return 0; // sentinel value signals failure
sum -= vl;
already_subtracted.insert(l);
}
else if (vl == vt)
{
if (!is_repeatable(l))
return 0; // sentinel value signals failure
sum += vl;
}
else // vl > threshold
{
sum += vl;
}
This test knocks off three more of the invalid Roman numerals.
Detect Invalid Roman Numerals
Roman
Numeral toDecimal isValid
"VV" 0 false
"LL" 0 false
"DD" 0 false
Refinement 4: Three repeats at most
The standard form of a Roman numeral allows a maximum of three repeats in a row. III is okay, but things like XIIII are invalid.
Trapping for this entails initializing a counter, n_repeats, before the loop, and carefully updating it within. n_repeats is adjusted on all three branches of the if-else-if statment.
Note, as well, that subtractive forms are only allowed when n_repeats is 1. Thus, XCC is invalid, because C is repeated.
int sum{ vt };
int n_repeats{ 1 };
std::unordered_set<char> already_subtracted;
while (leader != r.crend())
{
l = *leader; vl = value(l);
t = *trailer; vt = value(t);
if (vl < vt)
{
if (!is_subtractive(l, t) || already_subtracted.count(l) || n_repeats != 1)
return 0; // sentinel value signals failure
sum -= vl;
already_subtracted.insert(l);
n_repeats = 0;
}
else if (vl == vt)
{
if (!is_repeatable(l) || ++n_repeats > 3)
return 0; // sentinel value signals failure
sum += vl;
}
else // vl > threshold
{
sum += vl;
n_repeats = 1;
}
++leader; ++trailer;
}
These changes eliminate another seven of the invalid Roman numerals.
Detect Invalid Roman Numerals
Roman
Numeral toDecimal isValid
"IIII" 0 false
"XXXX" 0 false
"CCCC" 0 false
"MMMM" 0 false
"IXX" 0 false
"XCC" 0 false
"CMM" 0 false
Refinement 5: "Threshold" should be increasing
Here is what remains:
Detect Invalid Roman Numerals
Roman
Numeral toDecimal isValid
"IIV" 5 true
"IIX" 10 true
"XXL" 50 true
"XXC" 100 true
"CCD" 500 true
"CCM" 1000 true
"VIX" 14 true
"LXC" 140 true
"DCM" 1400 true
They involve what I have termed the "threshold."
Except for subtractive forms, as you scan from right to left, the values of the symbols you encounter should be the same or increasing. They should not be decreasing. In each of the examples above, the rightmost two symbols are a subtractive form that sets the threshold, and the leftmost symbol violates it.
In general, the threshold for a given symbol is that symbol's value.
Subtractive forms are an exception. In a subtractive form, the threshold is ten times the value of the symbol that is subtracted. Thus, the thresholds of IV and IX are both 10. Any symbol appearing to the left of IV or IX must have a threshold of at least 10. I and V are thus precluded.
Similarly, for CD and CM, the threshold is 1000. Any symbol appearing to the left of CD or CM must have a threshold of at least 1000, and, therefore, can only be M.
The logic to classfy the character *leader should test against the threshold, rather than against *trailer. Instead of vl < vt and vl == vt, function toDecimal should use vl < threshold and vl == threshold.
Here is the final version of function toDecimal. It incorporates variable threshold to knock out the final group of invalid Roman numerals listed above.
int toDecimal(std::string r, int (*value)(char const symbol))
{
r = tbx::to_upper(tbx::trim_whitespace(r));
// Fail if any of the characters in `r` are not valid Roman
// numeral symbols.
for (auto const& c : r)
if (value(c) == 0)
return 0; // sentinel value signals failure
// Handle short strings as special cases.
enum : std::size_t { zero, one };
switch (r.length())
{
case zero: return 0; // sentinel value signals failure
case one: return value(r.front());
default: break;
}
// Loop, scanning string `r` from right-to-left.
auto trailer{ r.crbegin() };
auto t{ *trailer };
auto vt{ value(t) };
auto leader{ std::next(r.crbegin()) };
auto l{ *leader };
auto vl{ value(l) };
int sum{ vt };
int n_repeats{ 1 };
int threshold{ vt };
std::unordered_set<char> already_subtracted;
while (leader != r.crend())
{
l = *leader; vl = value(l);
t = *trailer; vt = value(t);
if (vl < threshold)
{
if (!is_subtractive(l, t) || already_subtracted.count(l) || n_repeats != 1)
return 0; // sentinel value signals failure
sum -= vl;
already_subtracted.insert(l);
n_repeats = 0;
threshold = 10 * vl;
}
else if (vl == threshold)
{
if (!is_repeatable(l) || ++n_repeats > 3)
return 0; // sentinel value signals failure
sum += vl;
}
else // vl > threshold
{
sum += vl;
n_repeats = 1;
threshold = vl;
}
++leader; ++trailer;
}
return sum;
}
Upvotes: 0
Reputation: 21
int romanToInt(string s)
{
unordered_map<char, int> roman;
roman['I'] = 1;
roman['V'] = 5;
roman['X'] = 10;
roman['L'] = 50;
roman['C'] = 100;
roman['D'] = 500;
roman['M'] = 1000;
int num = 0, prev = 0, curr;
for (int i = s.length() - 1; i >= 0; i--)
{
curr = roman[s[i]];
num += (curr >= prev ? 1 : -1) * curr;
prev = curr;
}
return num;
}
Upvotes: 1
Reputation: 11403
The solution provided by Annie Kim works, but it uses a std::map, querying it several times for the same character, and I fail to see a reason for it.
int convert_roman_digit(char d)
{
switch (d)
{
case 'M': return 1000;
case 'D': return 500;
case 'C': return 100;
case 'L': return 50;
case 'X': return 10;
case 'V': return 5;
case 'I': return 1;
default: throw std::invalid_argument("Invalid digit");
}
}
int roman_to_int(const std::string& roman)
{
int result = 0, last_added = 0;
for (auto it = roman.rbegin(); it != roman.rend(); ++it)
{
const int value = convert_roman_digit(*it);
if (value >= last_added)
{
result += value;
last_added = value;
}
else
{
result -= value;
}
}
return result;
}
Caveat: the function happily accepts some invalid inputs (e.g. IMM) including "negative" numbers (e.g. IIIIIIIIIIIIIX), there are no overflow checks, and it throws. Feel free to improve it.
Upvotes: 3
Reputation: 905
This is the code that I use to convert Roman (smaller than 3999) to Integer. You may check if it works for larger numbers.
int romanToInt(string s) {
map<char, int> roman;
roman['M'] = 1000;
roman['D'] = 500;
roman['C'] = 100;
roman['L'] = 50;
roman['X'] = 10;
roman['V'] = 5;
roman['I'] = 1;
int res = 0;
for (int i = 0; i < s.size() - 1; ++i)
{
if (roman[s[i]] < roman[s[i+1]])
res -= roman[s[i]];
else
res += roman[s[i]];
}
res += roman[s[s.size()-1]];
return res;
}
Hope this could help you.
Upvotes: 13
Related Questions
- Roman Numeral to Integer Conversion Problem
- Converting integer to Roman Numeral
- Convert Hex in Char Pointer to Decimal
- Using std::hex to convert hex to decimal
- Converting roman numerals to decimals c++
- c program that converts numbers to roman numerals
- How can i get a result in my Roman numeral to decimal converter?
- c++ Roman Additive Form Conversion
- Roman numbers to decimal numbers, getting garbage value
- Numeric conversion