Convert a string having Roman numerals to an integer

Question 27. Convert a string having Roman numerals into an integer


The integer equivalent for the roman numerals is given below

To find the integer equivalent of a string containing roman numerals, we process the string from the rear. This simplifies the computation. If the current roman numeral is greater than the next numeral, we add the current numeral to the result. For instance consider XI. When processing X, since X is greater than I, we add 10 to the result. If the current roman numeral is less than the next numeral, then we subtract the current numeral from the result. For instance consider IX. When processing I, since I is less than X, we subtract 1 from the result.

C/C++


/*Helper function that returns the numeric value of a Roman alphabet*/
int get_numeric_value(char c)
{
	int result;

	switch(c) {
		case 'I': result = 1; break;
		case 'V': result = 5; break;
		case 'X': result = 10; break;
		case 'L': result = 50; break;
		case 'C': result = 100; break;
		case 'D': result = 500; break;
		case 'M': result = 1000; break;
		default: result = 0; break;
	}
	return result;
}


/* 
Main function that converts a Roman string into an integer
str1: valid input string with Roman alphabets
Return value: integer equivalent of the Roman string
*/
int roman_to_int(char *str1) 
{
	int i, result;
	
	/*Process the string from the rear*/
	i = strlen(str1) - 1;
	if (i < 0)
		return 0;
	
	result = get_numeric_value(str1[i]);
	--i;
	while (i >= 0) {
		int cur_value = get_numeric_value(str1[i]);
		int next_value = get_numeric_value(str1[i+1]);

		if (cur_value < next_value)
			result -= cur_value;
		else
			result += cur_value;		
			
		--i;
	}
	
	return result;
}



Java


/*Helper function that returns the numeric value of a Roman alphabet*/
public static int getNumericValue(char c) {
	int result;

	switch(c) {
		case 'I': result = 1; break;
		case 'V': result = 5; break;
		case 'X': result = 10; break;
		case 'L': result = 50; break;
		case 'C': result = 100; break;
		case 'D': result = 500; break;
		case 'M': result = 1000; break;
		default: result = 0; break;
	}
	return result;
}

/* 
Main function that converts a Roman string into an integer
str1: valid input string with Roman alphabets
Return value: integer equivalent of the Roman string
*/
public static int romanToInt(char[] str1) {
	/*Process the string from the rear*/		
	int i = str1.length - 1;
	if (i < 0)
		return 0;

	int result = getNumericValue(str1[i]);
	--i;
	while (i >= 0) {
		int curDigitVal = getNumericValue(str1[i]);
		int nextDigitVal = getNumericValue(str1[i+1]);

		if (curDigitVal < nextDigitVal)
			result -= curDigitVal;
		else
			result += curDigitVal;		
		
		--i;
	}

	return result;
}



Python


#str1: valid input string with Roman alphabets
#Return value: integer equivalent of the Roman string
def roman_to_int(str1) :
	table = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
	
	i = len(str1) – 1 #Process the string from the rear
	if (i < 0):
		return 0

	result = table[str1[i]]
	i -= 1
	while (i >= 0) :
		cur_digit_val = table[str1[i]]
		next_digit_val = table[str1[i+1]]
		if (cur_digit_val < next_digit_val):
			result -= cur_digit_val
		else:
			result += cur_digit_val		
		i -= 1
	
	return result



Print a number in words

Question 26. Given a number from 0 to 999,999,999, print the number in words. So 200,145,700 should be printed as two hundred million one hundred forty five thousand seven hundred


We will break the input number into millions, thousands and the remaining 3 least significant digits. So in this case 200,145,700 gets broken down to 200, 145 and 700. Then we make use of a helper function that prints 3 consecutive digits.

C/C++


/* 
Helper function to print number from 1 to 999
number: number from 1 to 999
*/
void print_3_digits(int number)
{
	int hundreds_digit, tens_digit, unit_digit, remainder;

	/*basic_lookup[0] is empty. We want basic_lookup[1] to map to "One" 
	and so on. */
	char *basic_lookup[] = {"", "One", "Two", "Three", "Four", "Five", "Six",
			"Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", 
			"Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen",
			"Eighteen", "Nineteen"};

	/*tens_lookup[0] and tens_lookup[1] are empty.
	We want tens_lookup[2] to map to "Twenty" and so on. */
	char *tens_lookup[] = {"", "","Twenty", "Thirty", "Fourty", "Fifty", 
			"Sixty", "Seventy", "Eighty", "Ninety"};

	/*Suppose number is 987, then hundreds_digit is 9*/
	hundreds_digit = number / 100;
	if (hundreds_digit > 0) {
		printf("%s Hundred ", basic_lookup[hundreds_digit]);
	}
	
	/*Suppose number is 987, then remainder will be 87*/
	remainder = number % 100;
	if (remainder > 0) {
		if (remainder <= 19) {
			printf("%s ", basic_lookup[remainder]);			
		} else {
			tens_digit = remainder / 10;
			unit_digit = remainder % 10;
			printf("%s ", tens_lookup[tens_digit]);
			printf("%s ", basic_lookup[unit_digit]);
		}
	}
	
}
 
/*
Main function to print the number in words
number: any number from 0 to 999999999
*/
void print_num_in_words(int number)
{
	int millions, thousands, remainder;

	/*If number is 0, handle it here and return*/
	if (number == 0) {
		printf("Zero \n");
		return;
	}

	/*Suppose number is 123456789, then millions = 123, remainder = 456789*/
	millions = number / 1000000;
	remainder = number - (millions * 1000000);
	
	/*Suppose remainder = 456789, then thousands = 456, remainder = 789*/
	thousands = remainder / 1000;
	remainder = remainder - (thousands * 1000);

	if (millions > 0) {
		print_3_digits(millions);
		printf("Million ");
	}

	if (thousands > 0) {
		print_3_digits(thousands);
		printf("Thousand ");
	}

	if (remainder > 0) {
		print_3_digits(remainder);
	} 
	
	printf("\n");
}



Java


/* 
Helper function to print number from 1 to 999
number: number from 1 to 999
*/
public static void print3Digits(int number) {
	/*basicLookup[0] is empty. We want basicLookup[1] to map to "One"
	and so on. */
	String[] basicLookup = {"", "One", "Two", "Three", "Four", "Five", 
			"Six", "Seven", "Eight", "Nine", "Ten", "Eleven", 
			"Twelve", "Thirteen", "Fourteen", "Fifteen", 
			"Sixteen", "Seventeen",	"Eighteen", "Nineteen"};

	/*tensLookup[0] and tensLookup[1] are empty.
	We want tensLookup[2] to map to "Twenty" and so on. */
	String[] tensLookup = {"", "","Twenty", "Thirty", "Fourty", "Fifty",
			"Sixty", "Seventy", "Eighty", "Ninety"};

	/*Suppose number is 987, then hundredsDigit is 9*/
	int hundredsDigit = number / 100;
	if (hundredsDigit > 0) {
		System.out.print(basicLookup[hundredsDigit] + " Hundred ");
	}

	/*Suppose number is 987, then remainder will be 87*/
	int remainder = number % 100;
	if (remainder > 0) {
		if (remainder <= 19) {
			System.out.print(basicLookup[remainder] + " ");			
		} else {
			int tensDigit = remainder / 10;
			int unitDigit = remainder % 10;
			System.out.print(tensLookup[tensDigit] + " ");
			System.out.print(basicLookup[unitDigit] + " ");
		}
	}
}
 
/*
Main function to print the number in words
number: any number from 0 to 999999999
*/
public static void printNumInWords(int number) {
	/*If number is 0, handle it here and return*/
	if (number == 0) {
		System.out.println("Zero ");
		return;
	}

	/*Suppose number is 123456789, then millions = 123, remainder = 456789*/
	int millions = number / 1000000;
	int remainder = number - (millions * 1000000);

	/*Suppose remainder = 456789, then thousands = 456, remainder = 789*/
	int thousands = remainder / 1000;
	remainder = remainder - (thousands * 1000);

	if (millions > 0) {
		print3Digits(millions);
		System.out.print("Million ");
	}

	if (thousands > 0) {
		print3Digits(thousands);
		System.out.print("Thousand ");
	}

	if (remainder > 0) {
		print3Digits(remainder);
	} 

	System.out.println("");
}



Python


#Helper function to print number from 1 to 999
#number: number from 1 to 999
def print_3_digits(number) :
	#basic_lookup[0] is empty. We want basic_lookup[1] to map to 'One'
	#and so on. 
	basic_lookup = ['', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 
			'Seven', 'Eight', 'Nine', 'Ten', 'Eleven', 'Twelve',
			'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 
			'Seventeen', 'Eighteen', 'Nineteen']

	#tens_lookup[0] and tens_lookup[1] are empty.
	#We want tens_lookup[2] to map to 'Twenty' and so on. 
	tens_lookup = ['', '','Twenty', 'Thirty', 'Fourty', 'Fifty', 'Sixty',
			'Seventy', 'Eighty', 'Ninety']

	#Suppose number is 987, then hundreds_digit is 9
	hundreds_digit = number // 100
	if (hundreds_digit > 0) :
		print(basic_lookup[hundreds_digit] + ' Hundred ', end='')
	

	#Suppose number is 987, then remainder will be 87
	remainder = number % 100
	if (remainder > 0) :
		if (remainder <= 19) :
			print(basic_lookup[remainder] + ' ', end='')
		else :
			tens_digit = remainder // 10
			unit_digit = remainder % 10
			print(tens_lookup[tens_digit] + ' ', end='')
			print(basic_lookup[unit_digit] + ' ', end='')
 
#Main function to print the number in words
#number: any number from 0 to 999999999
def print_num_in_words(number) :
	#If number is 0, handle it here and return
	if (number == 0) :
		print('Zero ')
		return
	
	#Suppose number is 123456789, then millions = 123, remainder = 456789
	millions = number // 1000000
	remainder = number - (millions * 1000000)

	#Suppose remainder = 456789, then thousands = 456, remainder = 789
	thousands = remainder // 1000
	remainder = remainder - (thousands * 1000)

	if (millions > 0) :
		print_3_digits(millions)
		print('Million ', end='')
	
	if (thousands > 0) :
		print_3_digits(thousands)
		print('Thousand ', end='')
	
	if (remainder > 0) :
		print_3_digits(remainder)
	 
	print('')




Convert a string to an integer

Question 25. Convert a string to an integer without using built-in functions


The function for converting a string to an integer is given below:

C/C++


/*
str: string to be converted to an integer
Result: integer value of the string
*/
int function_atoi(const char * str)
{
	int i, length; 
	int val = 0;
	int is_negative = 0;

	if (!str)
		return 0;

	length = strlen(str);
	i = 0;
	if (str[0] == '-') {
		is_negative = 1;
		++i;
	} 

	while (i < length ) {
		if (str[i] >= '0' && str[i] <= '9') {
			val = (val * 10) + (str[i] - '0');
		}
		else {
			break;
		}
		++i;
	}
	
	if (is_negative)
		val = -1 * val;

	return val;
}



Java


/*
str1: string to be converted to integer
result: integer value of string
*/
public static int strToInt(char[] str1) {
	int result = 0;
	boolean isNegative = false;
	int count = 0;
	
	for (char c : str1) {
		if (c == '-' && count == 0)
			isNegative = true;
		
		if ('0' <= c && c <= '9') 
			result = (result * 10) + (c - '0');

		count++; 
	}

	if (isNegative)
		result = -1 * result;

	return result;
}



Python


#str1: string to be converted to integer
#result: integer value of string
def str_to_int(str1):
	result = 0
	count = 0
	is_negative = False

	for c in str1:
		if (c == '-' and count == 0):
			is_negative = True

		if ('0' <= c and c <= '9'):
			result = (result * 10) + (ord(c) - ord('0'))

		count += 1

	if (is_negative):
		result = -1 * result 
		
	return result



Count number of words in a string

Question 24. Count the number of words in a string


We will define a word as a collection of one or more characters from a-z and A-Z. The words in a string can be separated by multiple spaces, tabs, punctuation marks etc. To count the number of words, as we traverse the string we will keep track of the previous character and the current character. If the previous character is not an alphabet from a-z and A-Z and the current character is an alphabet from a-z and A-Z, then we have encountered a new word and we increase the word count by 1.

C/C++


/*
str1: string in which the number of words have to be counted
Return value: number of words in the string
*/
int count_words(char *str1) 
{
	int num_words, pos;
	char cur_char, is_prev_char_alphabet;

	if (!str1)
		return 0;

	num_words = 0;
	pos = 0;
	cur_char = str1[pos];
	is_prev_char_alphabet = 0;
	while (cur_char != '\0') {
		int is_cur_char_alphabet = is_alphabet(cur_char);

		/*If previous character is not an alphabet and current character
		is an alphabet then we have found a new word*/
		if (!is_prev_char_alphabet && is_cur_char_alphabet) {
			++num_words;
		}

		is_prev_char_alphabet = is_cur_char_alphabet;
		
		pos++;
		cur_char = str1[pos];		
	}

	return num_words;
}

/*Helper function which checks if a character is an alphabet(a-zA-Z)*/
int is_alphabet(char c)
{
	if (c >= 'A' && c <= 'Z')
		return 1;

	if (c >= 'a' && c <= 'z')
		return 1;

	return 0;		
}



Java


/*
str1: string in which the number of words have to be counted
Return value: number of words in the string
*/
public static int countWords(char[] str1) {
	if (str1 == null)
		return 0;

	int numWords = 0;
	boolean isPrevCharAlphabet = false;
	for (char c : str1) {
		boolean isCurCharAlphabet = isAlphabet(c);

		/*If previous character is not an alphabet and current character is 
		an alphabet then we have found a new word*/
		if (!isPrevCharAlphabet && isCurCharAlphabet) 
			++numWords;

		isPrevCharAlphabet = isCurCharAlphabet;
	}

	return numWords;
}

/*Helper function which checks if a character is an alphabet(a-zA-Z)*/
public static boolean isAlphabet(char c)	{
	if (c >= 'A' && c <= 'Z')
		return true;

	if (c >= 'a' && c <= 'z')
		return true;

	return false;		
}



Python


#str1: string in which the number of words have to be counted
#Return value: number of words in the string
def count_words(str1) :
	if (str1 == None):
		return 0

	num_words = 0
	is_prev_char_alphabet = False
	for c in str1 :
		is_cur_char_alphabet = is_alphabet(c)

		#If previous character is not an alphabet and current character is 
		#an alphabet then we have found a new word
		if (not is_prev_char_alphabet and is_cur_char_alphabet) :
			num_words += 1
		
		is_prev_char_alphabet = is_cur_char_alphabet
	
	return num_words

#Helper function which checks if a character is an alphabet(a-zA-Z)
def is_alphabet(c):
	if (c >= 'A' and c <= 'Z'):
		return True

	if (c >= 'a' and c <= 'z'):
		return True

	return False



Find if two strings are anagrams

Question 23. Find if two string words are anagrams of each other


Two strings are anagrams of each other if re-arrangement of characters in one string results in the other string. This implies that two string words are anagrams if for each character, the number of times the character occurs in the first string is equal to the number of times it occurs in the second string. The code for finding if two words are anagrams is given below

C/C++


/*str1, str2: the two non-NULL strings which we want to compare
Return value: 1 if the two strings are anagrams, 0 otherwise
*/
int are_strings_anagrams( char *str1, char *str2)
{
	int count1[NUM_CHARACTERS], count2[NUM_CHARACTERS];
	int is_anagram, i;

	/*Initilize the counts to zero */
	memset(count1, 0, sizeof(int) * NUM_CHARACTERS);
	memset(count2, 0, sizeof(int) * NUM_CHARACTERS);
	
	/*Compute the character counts for str1 and str2*/
	while (*str1) {
		count1[(int)*str1]++;
		str1++;
	}
	
	while (*str2) {
		count2[(int)*str2]++;
		str2++;
	}
	
	/*Compare the counts*/
	is_anagram = 1;
	for (i = 0; i < NUM_CHARACTERS; ++i) {
		if (count1[i] != count2[i]) {
			is_anagram = 0;
			break;
		}
	}
	return is_anagram;
}



Java


/*
str1, str2: the two strings which we want to compare
Return value: true if the two strings are anagrams, false otherwise
*/
public static boolean areAnagrams( char[] str1, char[] str2) 	{
	/*Initilize the counts to zero */
	int[] count1 = new int[NUM_CHARACTERS]; //NUM_CHARACTERS is 256
	int[] count2 = new int[NUM_CHARACTERS];

	/*Compute the character counts for str1 and str2*/
	for (char c: str1) 
		count1++;

	for (char c : str2) 
		count2++;

	/*Compare the counts*/
	boolean isAnagram = true;
	for (int i = 0; i < NUM_CHARACTERS; ++i) {
		if (count1[i] != count2[i]) {
			isAnagram = false;
			break;
		}
	}

	return isAnagram;
}



Python


#str1, str2: the two strings which we want to compare
#Return value: True if the two strings are anagrams, False otherwise
def are_anagrams(str1, str2) :	
	count1 = [0] * NUM_CHARACTERS #NUM_CHARACTERS is 256
	count2 = [0] * NUM_CHARACTERS

	#Compute the character counts for str1 and str2
	for  c in str1:
		count1[ord(c)] += 1
	

	for  c in str2:
		count2[ord(c)] += 1
	
	#Compare the counts
	is_anagram = True
	if (count1 != count2):
		is_anagram = False
		
	return is_anagram