codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
/** * Convert a roman numeral into equivalent decimal number * If the number is invalid numeral or out of range (1-1000) * return 0 * Also check: http://codepad.org/2LG4SbjJ */ #include <stdio.h> #include <stdlib.h> #include <assert.h> /* #define const */ int rtoimap[128] = {0}; /* Roman to indices */ enum /* ERomanIntLetters */ { I = 0, V,X,L,C,M,D, TOTAL_ROMAN_INT_TYPE }; /** * Idea is, tree has many children * Each children correspond to one next roman numeral */ struct tree_node { int value; struct tree_node *children[TOTAL_ROMAN_INT_TYPE]; }; struct tree_node *head; /* Export */ int toDecimal(char *rn); /* Locals */ static void init_roman(void); static struct tree_node *getTreeNode(void); static void freeTreeNode(struct tree_node *h); static void registerNumber(int n, char *h, char *t, char *u); static void clean_roman(void); /** * Register a roman numeral into tree for fast search * * @param [in] n Number * @param [in] h, t, u Roman numeral string is formed by concatenating these strings */ static void registerNumber(int n, char *h, char *t, char *u) { struct tree_node *cur = head; char *rns[] = {h, t, u, 0}; char **prns = rns; if(!n || !h || !t || !u || !cur) return; while(*prns) { char *s = *prns; while(*s != '\0') { const int index = rtoimap[*s]; assert(-1 != index); if(NULL == cur->children[index]) cur->children[index] = getTreeNode(); cur = cur->children[index]; ++s; } ++prns; } assert(NULL != cur); cur->value = n; } /** * Get a new tree node * This node is initialized to zero value and all children are initialized to NULL * * @return New node * @warning Caller should free the memory of node by calling free */ static struct tree_node *getTreeNode(void) { int i; struct tree_node *ret = malloc( sizeof(struct tree_node) ); ret->value = 0; for(i = 0; i < TOTAL_ROMAN_INT_TYPE; ++i) ret->children[i] = NULL; return ret; } /** * Delete a tree node * Recursively delete all children of a node by freeing their memory * * @param [in] h Head node to release */ static void freeTreeNode(struct tree_node *h) { int i; for(i = 0; i < TOTAL_ROMAN_INT_TYPE; ++i) { struct tree_node *c = h->children[i]; if(c) freeTreeNode(c); free(c); } } /** * Inititalize roman lookup tree */ static void init_roman(void) { int n, h, t, u; char *units [] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}; char *tens [] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}; char *hundreds[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}; for(n = 0; n < 128; ++n) rtoimap[n] = -1; rtoimap['I'] = I; rtoimap['V'] = V; rtoimap['X'] = X; rtoimap['L'] = L; rtoimap['C'] = C; rtoimap['M'] = M; rtoimap['D'] = D; head = getTreeNode(); for(n = 0, h = 0; h < 10; ++h) for(t = 0; t < 10; ++t) for(u = 0; u < 10; ++u) { registerNumber(n++, hundreds[h], tens[t], units[u]); } registerNumber(n, "M", tens[0], units[0]); /* Hack */ /* #define INCLUDE_EXTENDED_LIST */ #ifdef INCLUDE_EXTENDED_LIST registerNumber(4, hundreds[0], tens[0], "IIII"); /* Found on the dial pads of clocks */ #endif } /** * Cleanup roman lookup tree */ static void clean_roman(void) { freeTreeNode(head); free(head); head = NULL; } /** * Convert a string to roman decimal * * @param [in] rn_string Roman numeral string to convert * @return Equivalent decimal number */ int toDecimal(char *rn_string) { char *rn = rn_string; struct tree_node *cur = head; if(!rn || !cur) return 0; while(*rn != '\0') { const int index = rtoimap[*rn++]; if(-1 == index) cur = NULL; else cur = cur->children[index]; if(!cur) { cur = head; break; } } printf("%s: %d\n", rn_string, cur->value); return cur->value; } /** * Entry point of the program (For unit testing) * * @param [in] argc Command line argument count * @param [in] argv Command line argument vector * @return Program status */ int main(int argc, char *const *argv) { init_roman(); if(argc > 1) { int i; for(i = 1; i < argc; ++i) toDecimal(argv[i]); } else { // dummy run toDecimal("Mohit"); toDecimal("IX"); toDecimal("X"); toDecimal("IXI"); toDecimal("XL"); toDecimal("IIII"); toDecimal(""); toDecimal(NULL); toDecimal("DCCCLXXXVIII"); /* Big length */ toDecimal("CMXCIII"); toDecimal("CMXCIX"); toDecimal("M"); toDecimal("MI"); toDecimal("MIB"); /* Men in black */ } clean_roman(); return 0; }
Private
[
?
]
Run code
Submit