0

I request you to please read this before marking as Duplicate.

I have referred to below:

After understanding, I have designed following algorithm to convert roman to decimal.

  • Let Roman String be ......

  • Replace string contents of length = 4 with appropriate content

    • Length = 4, Roman numerals are VIII = 8

  • Replace string contents of length = 3 with appropriate content

    • Length = 3, Roman numerals are MMM = 3000, XXX = 30, VII = 7, III = 3
  • Replace string contents of length = 2 with appropriate content
    • Length = 2, Roman numerals are MM = 2000, XX = 20, XI = 11, IX = 9, VI = 6, IV = 4, II = 2
  • Once this is done, then follow below rules:
    • Subtract digits from each other
      • I can be subtracted (absolute) from V or X
      • X can be subtracted (absolute) from L or C
      • C can be subtracted (absolute) from D or M
    • Finally there will be a bunch of digits. Add all of them to get the answer

My questions are :

  • Is the algorithm correct ?
  • I am planning to optimize the algorithm. Does anyone have any tips ?
Community
  • 1
SimpleGuy
  • 101
  • Well, don't u think this question should be on Stackoverflow or Computer ScienceSE or some other place? – Mayank M. Aug 27 '16 at 16:20
  • It is on this because it has to do with math than to do with computer science. I want people who have knowledge of math to verify this. Do u still think I shud move it ? – SimpleGuy Aug 27 '16 at 17:41
  • Well, when you used the word "Algorithm" I thought about that. I'll comment again, let me think about it for a while. Okay, I just wanna know, do you want coding of this algorithm or we have to just find out flaws? – Mayank M. Aug 30 '16 at 14:50
  • If you need the flaws then I can tell you but even then a tint of programming will come here. That's why I recommended you that. Also would you please elaborate your algo. with an example. Some of your steps are absurd. – Mayank M. Aug 30 '16 at 14:56
  • @MayankM. I don't want you to tell me to about the tint of programming. This isn't a programming site and neither I am expecting you to tell me how to code. The term algorithm by definition is not a programming term. So, just because algo is used, it does not mean that it relates to programming. In simple words, it means solving something step by step. Do remember this. All I want, is, people to tell me if this is functionally correct or not. – SimpleGuy Sep 01 '16 at 08:41
  • MMCMXCIV = 2994 is a rather awkward but legitimate and valid number representation. Your algorithm having an upper limit of 4 will break it at MMCMX|CIV and interpret it as 2910 + 104 = 3014. – fleablood Sep 01 '16 at 16:35
  • Why does it never occur to people to have their algorithms read right to left rather than left to right? Think about it. The difficult to quantify rule is that symbols go (left to right) from highest to lowest with the difficulty being that a change in order is a subtraction but its hard to tell if subtraction is of the immediate next term which you havent gotten to or further off because you get the subtracted term before the main term. If you go right to left you always get the main term first. In any event, IMO, length is worst possible thing to consider first. – fleablood Sep 01 '16 at 16:41
  • @fleablood First, the algo will replace strings of length 4 with appropriate content. Strings of length four as per algo are VIII = 8, no such string found in input string. Next it will move to replace length 3. Again no string of length three found in input. Next it will move to replace length 2 strings. MM and IV found, replaced with numbers 2000 and 4. So input now is 2000 CMXC 4. Now move with subtraction. C-M [100 - 1000] and X-C [10-100] all absolute. So input string is now 2000 900 90 4. Finally algo says add them all. So we get 2994 – SimpleGuy Sep 02 '16 at 02:38
  • @fleablood reading from right to left is a nice one.. I will include that – SimpleGuy Sep 02 '16 at 02:43
  • Ah, I misunderstood about string of four. But how will the algorithm determine which chars belong to what groups? – fleablood Sep 02 '16 at 04:33
  • @fleablood I would say that is left for the user to decide how to implement. I have my own implementation (in programming language) of this algo. Since people would not like programmming here, so i have posted a way to convert to roman.. – SimpleGuy Sep 02 '16 at 11:48
  • @SimpleGuy have you got the answer from somewhere? I'm also interested in knowing about a fool proof algo. for this task. I'll recommend you to ask your colleges, teachers, friends, etc. for this question! On Math.SE you can also answer your own question. BTW, I find my answer very appropriate, please tell if there is something wrong. – Mayank M. Sep 05 '16 at 16:18

1 Answers1

1

I know very well what is an algorithm, and neither I'm interested in giving the codes on Math.SE.

If I'm not wrong in understanding your algo., in those steps of replacing you must keep in mind the precedence of replacement, for example, take $XIX$, you'll first replace XI (as you've typed) with 11, then subtract 10($X$), from 11, thus answer comes 1.

But if you add $XIX$ in the $length=3$ list then you may get the perfect answer.

But, even then, you cannot just write all possible exceptions, 'cause exceptions come due to lack of knowledge or due to improper steps of algorithm. And, due to that "precedence" I said to you that it has a "tint" (only a tint) of programming.

And, just to remove this small flaw($XIX$), you've to take in mind of grouping or at least the correct precedence of replacement.

Well, I found this link of your's very useful. They have the correct precedence.

[EDIT]
Algorithm for it can be recursive in nature and can go like this:
1) Start reading the characters from left.
2) If there is any value you come upon which is less than the earlier value then divide the expression in two, one for left side and one for right side.
3) Find value of left expression using your replace conditions, and repeat the steps for the right side.
4) Finally add all the values.

I checked it for $XIX$ and it works, provided you take the precedence of replacement same as in that link.

[EDIT2]
Well, I found that $V, L, D$ cannot be used as subtracting elements from here and BTW, our algorithms nearly match, why didn't you took a reference from there?

Community
  • 1
Mayank M.
  • 689
  • Thanks ! I will add the precedence part when replacing strings with roman in a same length category. For that, I will form the strings by reading chars from right to left – SimpleGuy Sep 02 '16 at 02:43