7 Replies - 975 Views - Last Post: 05 November 2012 - 06:45 PM Rate Topic: -----

#1 Xente  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 36
  • Joined: 31-January 12

Converting C++ to C (Phone Mnemonics)

Posted 04 November 2012 - 01:19 PM

I'm trying to make a phone mnemonic generator. If a string is "23", the output should be AD, AE, AF, BD, BE, BF, CD, CE, CF. I have the following C++ code that works just fine:

void permute(string prefix, string post) {
	  if (post.length() == 0){
		 cout << prefix << endl;
	  }
	  else {
		 string letters = getChar(post[0]);
		 for (int i = 0; i < letters.length(); i++){
			permute(prefix + letters[i], post.substr(1));
		}
	}
}

string getChar(char ch) {
	  switch (ch) {
		case '2': return ("ABC");
		case '3': return ("DEF");
		case '4': return ("GHI");
		case '5': return ("JKL");
		case '6': return ("MNO");
		case '7': return ("PRS");
		case '8': return ("TUV");
		case '9': return ("WXY");
		default: cout << "Not a valid char" << endl;
	}
}




Now, I'm trying to get it to work using C, but I'm running into problems. This is the code is C:

void permute(char* prefix, char* post) {
    if (strlen(post) == 0)
        printf("%s\n", prefix);
    else {
        char* letters = getChar(*post);
        for (int i = 0; i < strlen(letters); i++) {
            permute(prefix + letters[i], post + 1);
        }
    }
}




The getChar method is mostly untouched except it returns char* and the cout has been changed to printf.
It's not printing out the proper results, instead, it's mostly just blank new lines. But I have noticed that it prints out the right amount of blank lines, for example, in the C++ code there are nine results, and in C it prints out nine blank new lines.

Is This A Good Question/Topic? 0
  • +

Replies To: Converting C++ to C (Phone Mnemonics)

#2 Oler1s  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1395
  • View blog
  • Posts: 3,884
  • Joined: 04-June 09

Re: Converting C++ to C (Phone Mnemonics)

Posted 04 November 2012 - 01:53 PM

Quote

It's not printing out the proper results,
A note on asking for help. We have no idea what "wrong" means. You need to give us observations and expected results.

For example, your input, expected output, and actual output.

On to the code I see (C version): permute(prefix + letters[i], post + 1) . What do you think this does?

Let's pick apart prefix + letters[i]. What is the type of prefix? What is the type of letters[i]? What is the effect of the + operator on these two types?
Was This Post Helpful? 0
  • +
  • -

#3 Xente  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 36
  • Joined: 31-January 12

Re: Converting C++ to C (Phone Mnemonics)

Posted 04 November 2012 - 08:46 PM

Ok, I'm sorry for the ambiguous "proper results," but I was in a bit of a rush when I posted the question.

Thanks for the insight, I learned to program in Java where + concatenated two strings, and I completely forgot about how strings are handled in C. I always able to fix the problem by using strcat in lieu of '+' and using another method substring that modifies strncpy a bit. For the sake of education, here's the code in case anyone else has a similar problem.

void permute(char* prefix, char* post) {
   if (strlen(post) == 0)
        printf("%s\n", prefix);
    else {
        char* letters = getChar(*post);
        for (int i = 0; i < strlen(letters); i++) {

            //strings needed for recursive premute call
            char *combined = calloc(sizeof(char), 50);
            char *prefix_new = substring(letters, i, 1);
            char *postfix_new = substring(post, 1, strlen(post));

            //combines the strings
            strcat(combined, prefix);
            strcat(combined, prefix_new);
            
            permute(combined, postfix_new);

            //frees allocated memory
            free(combined);
            free(prefix_new);
            free(postfix_new);
        }
        free(letters);
    }
}




Here's the substring method

char *substring(char *s, int start, int end) {
    char *result = calloc(sizeof(char), 50);
    return strncpy(result, s + start, end);
}



I'm pretty sure it may not be the most elegant solution, but here are the results

AD
AE
AF
BD
BE
BF
CD
CE
CF



which are the wanted results, plus no memory leaks--which is always good.

Thanks for the help
Was This Post Helpful? 1
  • +
  • -

#4 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6107
  • View blog
  • Posts: 23,661
  • Joined: 23-August 08

Re: Converting C++ to C (Phone Mnemonics)

Posted 05 November 2012 - 04:00 AM

Just a note, in case you didn't know or for others' benefit. The only reason this works:

char *substring(char *s, int start, int end) {
    char *result = calloc(sizeof(char), 50);
    return strncpy(result, s + start, end);
}



is because calloc guarantees the array contents are initialized to 0s. strncpy does not automatically null-terminate strings, so if someone tries to use malloc here instead of calloc they're probably going to get bitten in the ass.
Was This Post Helpful? 1
  • +
  • -

#5 jimblumberg  Icon User is offline

  • member icon


Reputation: 4278
  • View blog
  • Posts: 13,437
  • Joined: 25-December 09

Re: Converting C++ to C (Phone Mnemonics)

Posted 05 November 2012 - 07:35 AM

The strncpy() doesn't guarantee that the end of string character is placed in the string if the destination string is not large enough to hold the string being copied, so even using calloc() will cause problems. But if the destination is larger than the string being copied strncpy() pads the destination string with zeros. So using calloc() to allocate memory then using strncpy() is a waste of CPU cycles because you waste time filling the allocated memory with zeros then copy the string, after which you fill the unused space with zeros again.

Jim

This post has been edited by jimblumberg: 05 November 2012 - 07:36 AM

Was This Post Helpful? 1
  • +
  • -

#6 Xente  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 36
  • Joined: 31-January 12

Re: Converting C++ to C (Phone Mnemonics)

Posted 05 November 2012 - 10:29 AM

View Postjimblumberg, on 05 November 2012 - 07:35 AM, said:

So using calloc() to allocate memory then using strncpy() is a waste of CPU cycles because you waste time filling the allocated memory with zeros then copy the string, after which you fill the unused space with zeros again.

Jim


Wow, that's really good to know. I'll definitely keep that in mind from now on. I'm learning C in my class called "Advanced Programming," after programming in C for about two months I can see where the "Advanced" comes from. C makes me appreciate OOP that much more, but there's something enticing about C :bigsmile:
Was This Post Helpful? 0
  • +
  • -

#7 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5932
  • View blog
  • Posts: 12,855
  • Joined: 16-October 07

Re: Converting C++ to C (Phone Mnemonics)

Posted 05 November 2012 - 02:31 PM

This is a great example of why C++ programmers have it too damn easy. ;)

Thanks for showing the code. However, the minute you start doing stuff like calloc, you need to take a step back. C makes you painfully aware of the resources demanded by a process. So painful, that you try your best not to use those resources.

Since you have an answer, this is how I'd do your code in C:
#include <stdio.h>

const char *getLetters(char ch) {
	switch (ch) {
		case '2': return "ABC";
		case '3': return "DEF";
		case '4': return "GHI";
		case '5': return "JKL";
		case '6': return "MNO";
		case '7': return "PRS";
		case '8': return "TUV";
		case '9': return "WXY";
		default:
			return NULL;
	}
}

void permute(char *prefix, int pos) {
	char originalChar = prefix[pos];
	if (originalChar == 0) {
		printf("%s\n", prefix);
	} else {
		const char *letters = getLetters(originalChar);
		if (letters==NULL) {
			prefix[pos] = '*';
			permute(prefix, pos + 1);
		} else {
			for(;*letters!=0; letters++) {
				prefix[pos] = *letters;
				permute(prefix, pos + 1);
			}
		}
		prefix[pos] = originalChar;
	}
}

int main(int argc, char** argv) {
	char s[] = "23";

	printf("- %s\n", s);
	permute(s, 0);
	printf("- %s\n", s);
	
	return 0;
}



Note that no string functions or dynamic allocation is used for this. We simply use the c-string itself as a buffer.
Was This Post Helpful? 0
  • +
  • -

#8 Xente  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 36
  • Joined: 31-January 12

Re: Converting C++ to C (Phone Mnemonics)

Posted 05 November 2012 - 06:45 PM

View Postbaavgai, on 05 November 2012 - 02:31 PM, said:

This is a great example of why C++ programmers have it too damn easy. ;)


Anyone who doesn't program in C or Assembly has it easy!

I'm learning both right now and I miss the old days of Java. Anything that involves arrays--and strings by extension--makes me wanna pull my hair out. But it's nice to learn a language you can do so much with.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1