# Roman Numeral Algorithm Help



## char[] rager (Jan 13, 2011)

Here is my C++ code for something that converts a roman numeral sequence to its equivalent arabic numeral sequence:


```
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main()
{
	int sum = 0;
	string sequence;
	vector<int> list;
	
	for (;;)
	{
		cout << "Enter The Roman Numeral Sequence In Lowercase, e To Exit:  ";
		cin >> sequence;
		cout << endl;

		for (int counter = 0; counter < sequence.size(); counter++)
		{
			switch (sequence[counter])
			{
				case 'i':
					list.push_back(1);
					break;

				case 'v':
					list.push_back(5);
					break;

				case 'x':
					list.push_back(10);
					break;

				case 'l':
					list.push_back(50);
					break;

				case 'c':
					list.push_back(100);
					break;

				case 'd':
					list.push_back(500);
					break;

				case 'm':
					list.push_back(1000);
					break;
                                [COLOR="Green"]// Any letter not matching the
                                   above letters will stop the program[/COLOR]
				default:
					cout << "Error:  Unrecognized Letter" << endl;
					return 0;
			}
		}

		for (int counter = 1; counter < list.size(); counter++)
		{
			if (list[counter - 1] < list[counter])
			{
				list[counter - 1] = (list[counter - 1]) * (-1);
			}
		}

		for (int counter = 0; counter < list.size(); counter++)
		{
			sum += list[counter];
		}

		cout << sum << endl << endl;

		sum = 0;
		list.clear();
	}
	return 0;
}
```

The problem is when I go to verify any sequence with an online converter, my answers will be verified only most of the time. Can you help me find out what is wrong with my algorithm?


----------



## W1zzard (Jan 13, 2011)

if an individual character has a lower value than the character to its right, you need to subtract instead of add.

for example IX = 9, not 11


----------



## char[] rager (Jan 13, 2011)

I believe that is what I am doing.


```
for (int counter = 1; counter < list.size(); counter++)
{
	if (list[counter - 1] < list[counter])
	{
		list[counter - 1] = (list[counter - 1]) * (-1);
	}
}
```

I am traversing the vector, starting at index number 1. I then check to see if the number that is stored at the index before the current index is less than the number at the current index. If so, multiply that number by negative one and then use that number to replace the old number.

This is because, in the next for loop, I am adding all of the numbers up together, and when you add a negative number to a positive number, you are really subtracting.


----------



## Kreij (Jan 13, 2011)

Since you did not give us any examples of what numbers fail, I'll just take a shot at it.
Are you doing enough checking for valid character sequences?

For instance ... if I type in IVX, your program will return 4. (-1 + -5 + 10)
IVX is obviously not how one would write 4 in roman numerals.


----------



## char[] rager (Jan 13, 2011)

Kreij, you have exposed a major flaw in my algorithm. Thank You.

Simple checking to see if the number before is smaller is just not good enough. I will have to go back to the drawing boards


----------



## streetfighter 2 (Jan 13, 2011)

char[] rager said:


> I will have to go back to the drawing boards


With a program of this complexity, the drawing board must have lots of empty space. 

I (very half-assedly) rewrote the core function of the program found here to use your vector.  Give it a try if you like:

```
int len = list.size(),x,sum = 0;
x = len-1;
int last_level = list[x--];
sum = last_level;
while (x >= 0)
{
	if (last_level <= list[x])
		sum = sum + list[x];
	else
		sum = sum - list[x];
	last_level = list[x];
	x--;
}
```

"_arabic numeral sequence_"
Are you high?  I had to look this up just to figure out that I'm an idiot.  You could have just said "decimal" or "integer"...


----------



## Kreij (Jan 14, 2011)

streetfighter 2 said:


> "arabic numeral sequence"
> Are you high? I had to look this up just to figure out that I'm an idiot. You could have just said "decimal" or "integer"...



LOL ... I knew what it meant, but I've not seen it expressed that way in quite some time.
I guess it's those guys over at MIT 

@char[] : Also don't forget to sanitize (Trim) the input string of leading and/or trailing white space or the program will puke if someone types in " XIV " instead of just "XIV".


----------



## char[] rager (Jan 14, 2011)

Kreij, I am not questioning your intelligence, but is IVX even a legal roman numeral expression?

Different online roman numeral converters either give the arabic equivalent as 4, or 14 because they automatically convert the sequence to XIV, or don't even give an answer.

This converter gives the same answer as my algorithm gives for IVX:  4.

This converter automatically converts the input to XIV and then gives the answer as 14. I don't know why it changes the sequence from IVX to XIV, maybe because IVX is not a legal expression.

This converter gives the following message whenever you enter IVX:  "IVX is not a valid input"


----------



## FordGT90Concept (Jan 14, 2011)

char[] rager said:


> This converter automatically converts the input to XIV and then gives the answer as 14. I don't know why it changes the sequence from IVX to XIV, maybe because IVX is not a legal expression.
> 
> This converter gives the following message whenever you enter IVX:  "IVX is not a valid input"


Those two are right.  IVX is not valid; XIV is 14.  The first one ignored the X and processed it as IV.  There's only one way to write any number:







Hmm, I think I wanna write an app that does the same thing.  I never did much work with Roman Numerals and I'm bored. XD


----------



## char[] rager (Jan 14, 2011)

I was bored too. Hard to believe for a student such as myself during an active semester, but, classes just started and I was looking for something to do with programming as I don't have actual programming classes this semester, rather I have computer theory classes.

Thank You street fighter for that algorithm, but I want to do this myself, and I will get it to work. I am thinking, that even though my algorithm gives an answer for IVX when in actuality, IVX should not have an answer, my algorithm does work, as it gives the right answer for valid roman numeral sequences. I will continue to beautify it and post my completed program.

I await to see what your genius comes up with FordGT.


----------



## FordGT90Concept (Jan 14, 2011)

I can't really explain it but I can make my code output 4 or 14.  RomanNumeral is effectively the same as an integer.  It is making the conversions as necessary (e.g. M -> 1000).

This outputs 14 from IVX (which is correct according to Wikipedia):

```
private static RomanNumeral StringToNumeral(string value)
        {
            value = value.Trim();

            RomanNumeral output = new RomanNumeral();
            for (int i = 0; i < value.Length; i++)
            {
                RomanNumeral a = value[i];
                if (i == value.Length - 1)
                {
                    output += a;
                    return output;
                }
                else
                {
                    RomanNumeral b = value[i + 1];
                    [b]if (b > a)
                    {
                        [u]output += b - a;[/u]
                        [u]i++;[/u] // it is processing both at once so skip ahead.
                    }[/b]
                    else
                        output += a;
                }
            }
            return output;
        }
```

This outputs 4 out of IVX (erronous):

```
private static RomanNumeral StringToNumeral(string value)
        {
            value = value.Trim();

            RomanNumeral output = new RomanNumeral();
            for (int i = 0; i < value.Length; i++)
            {
                RomanNumeral a = value[i];
                if (i == value.Length - 1)
                {
                    output += a;
                    return output;
                }
                else
                {
                    RomanNumeral b = value[i + 1];
                    [b]if (b > a)
                        [u]output -= a;[/u][/b]
                    else
                        output += a;
                }
            }
            return output;
        }
```
Both produce 14 out of XIV.


How I came to that first code example is:


			
				Wikipedia said:
			
		

> For example, in MCMXLIV (1944), the symbols C, X and I each precede a symbol of higher value, and the result is interpreted as 1000 plus *(1000 minus 100)* plus *(50 minus 10)* plus *(5 minus 1)*.



Now I'm debating about adding the fractions (12ths) but then I have to convert from integers to decimals. 


I'm going to try adding some code which implements the following traps (same section as the URL above to Wikipedia):


			
				Wikipedia said:
			
		

> A numeral for 10n (I, X, or C) may not precede a numeral larger than 10n+1, where n is an integer.  That is, I may precede V and X, but not L or C; X may precede L or C, but not D or M. The numerals 5×10n (V, L, or D) may not be followed by a numeral of greater or equal value.  Any symbol that appears more than once consecutively may not be followed by a symbol of larger value.




Edit: IVX violates the second rule there: _The numerals 5×10n (V, L, or D) may not be followed by a numeral of greater or equal value._  X (10) is greater than V (5).  In my code, I added a selectable "ValidationLevel" which can be set to the following settings with subsequent results on input...

None:
XCIX = 99
IC = 99
IVX = 14
CCCCCM = 1400

Loose:
XCIX = 99
IC = 99
IVX = 14
CCCCCM = "Having two or more consecutive numerals followed by a numeral of greater value is considered illegal."

Strict:
XCIX = 99
IC = "I, X, C may not be followed by a numeral more than 10(n + 1) times higher."
IVX = "V, L, D may not be followed by a numeral of greater or equal value."
CCCCCM = "Having two or more consecutive numerals followed by a numeral of greater value is considered illegal."


Here's the validation code:

```
private static void Validate(string value)
        {
            if (VALID_LEVEL == ValidationLevel.None)
                return;

            RomanNumeral[] values = new RomanNumeral[value.Length];
            for (int i = 0; i < values.Length; i++)
                values[i] = new RomanNumeral(value[i]);

            if (VALID_LEVEL >= ValidationLevel.Loose)
            {
                for (int i = 2; i < values.Length; i++)
                {
                    if (values[i - 2] == values[i - 1])
                    {
                        if (values[i - 1] < values[i])
                            throw new ArgumentException("Having two or more consecutive numerals followed by a numeral of greater value is considered illegal.", "value");
                    }
                }
            }

            if (VALID_LEVEL >= ValidationLevel.Strict)
            {
                for (int i = 1; i < values.Length; i++)
                {
                    switch (values[i - 1])
                    {
                        case 5:
                        case 50:
                        case 500:
                            if (values[i] >= values[i - 1])
                                throw new ArgumentException("V, L, D may not be followed by a numeral of greater or equal value.", "value");
                            break;
                        default:
                            if (10 * (values[i - 1] + 1) < values[i])
                                throw new ArgumentException("I, X, C may not be followed by a numeral more than 10 times higher.");
                            break;
                    }
                }
            }
            return;
        }
```
VALID_LEVEL is defined as a constant in the class (currently set to ValidationLevel.Strict).


Edit: Now I'm working on RomanNumeral.ToString().  Problems occur at 4000 because there's no values greater than M (well there are, but not supported by ASCII).  I need to adapt my code to, at that point, switch to adding more and more M's.


Edit: It appears to work.  It can handle MMMMMMMMMCMXCIX -> 9999 -> MMMMMMMMMCMXCIX.  Theoretically, it could go up to 2,147,483,647 (1,000,000 is confirmed to work).

The only thing left to do, really, is to add fractions.  Looking at it more closely, I don't think it is worth it (no one uses them unless they're historians).


Edit: I attached a zip which has a ValidationLevel None, Loose, and Strict executable.  It accepts numbers and numerals. e.g. DCCCLXXX -> 880, 99 -> XCIX


----------



## char[] rager (Jan 14, 2011)

Looking good Ford


----------



## Kreij (Jan 14, 2011)

Yes, char[], I was aware that IVX was not valid. That's why I used it for the example.
If I were to write a program for this, I would not automatically convert it to XIV as that makes an assumption that may or may not be true. I would simply output that the sequence was invalid and then ask for input again.

Just my 2 cents.


----------



## Disparia (Jan 14, 2011)

That's not very Web 2.0 

Offer the user the possible corrections or have them input it again.


----------



## streetfighter 2 (Jan 14, 2011)

char[] rager said:


> I was bored too. Hard to believe for a student such as myself during an active semester, but, classes just started and I was looking for something to do with programming as I don't have actual programming classes this semester, rather I have computer theory classes.


Are you theorizing 'bout this?
http://www.tug.org/texshowcase/cheat.pdf



FordGT90Concept said:


> . . .The only thing left to do, really, is to add fractions.  Looking at it more closely, I don't think it is worth it (no one uses them unless they're historians). . .


I read your post and now I know how to read roman numerals.  I've lived my whole life up to this point without caring about numerals above XI.  Jerk. 

Tonight I'll have to blank out that useless knowledge with copious amounts of booze.


----------



## FordGT90Concept (Jan 14, 2011)

Heh, I really couldn't read them either but you can't write an application that does something you don't know how to do so naturally, I had to learn it.  Roman Numerals really aren't that complex. 


Oh, and I think the key is that negative doesn't exist in roman numerals.  If your output ever hits zero or less, it is invalid (methology is wrong).  This goes back to the code example above (output += b - a).


Edit: The source is 285 lines long and that includes a lot of code that is rarely used (e.g. sbyte -> RomanNumeral).


----------



## Kreij (Jan 14, 2011)

Jizzler said:


> That's not very Web 2.0
> 
> Offer the user the possible corrections or have them input it again.



Fooey. Make them figure out their own mistakes.


----------



## char[] rager (Jan 14, 2011)

Yeah, I did make a big mistake not telling them that a sequence is incorrect. I will fix it later, but I already have two freaking papers due, and semester just started


----------

