segmentation fault, recursive palindrome

Please support our C++ advertiser: Intel Parallel Studio Home
Thread Solved

Join Date: Oct 2008
Posts: 11
Reputation: DragonReborn225 is an unknown quantity at this point 
Solved Threads: 0
DragonReborn225 DragonReborn225 is offline Offline
Newbie Poster

segmentation fault, recursive palindrome

 
0
  #1
Oct 31st, 2008
hey guys, I'm having some difficulty with finding out whether a user inputted string is a palindrome. It doesn't have to identify pure palindromes either, just the basics. Everything was going great, and just as it was looking like I'd get to bed before 3 am, I got hit with a segmentation fault. I messed around with it alot, and bypassed that error, but now it cuts a letter off the user inputted string.

for example:

say I input ffaff
It will read faff, and tell me no palindrome exists.

I have a feeling it has something to do with the arrays, as I'm not very knowledgeable on that front because we've yet to cover them in class. Thanks in advance!!!



  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. bool Palindrome(string pal, int index, int length)
  6. {
  7. int total;
  8.  
  9. pal[index] = 30;
  10.  
  11. if ((length == 0 || length == 1))
  12. {
  13. cout << pal << ", is infact a palindrome." << endl;
  14. return true;
  15. }
  16. if (pal[index] == pal[length - 1 - index])
  17.  
  18. return Palindrome(pal, index++, length);
  19.  
  20. else
  21. {
  22. cout << pal << ", is infact not a palindrome." << endl;
  23. return false;
  24. }
  25. }
  26.  
  27. int main () {
  28.  
  29. string word;
  30.  
  31. cout << "Enter your prospective palindrome." << endl;
  32. cin >> word;
  33. Palindrome(word, 0, word.length());
  34.  
  35. return 0;
  36. }
Reply With Quote Quick reply to this message  
Join Date: Jun 2008
Posts: 973
Reputation: Alex Edwards is a jewel in the rough Alex Edwards is a jewel in the rough Alex Edwards is a jewel in the rough Alex Edwards is a jewel in the rough 
Solved Threads: 107
Alex Edwards's Avatar
Alex Edwards Alex Edwards is offline Offline
Posting Shark

Re: segmentation fault, recursive palindrome

 
0
  #2
Oct 31st, 2008
Here's something I managed to whip up thanks to your logic--

  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4.  
  5. using std::cout;
  6. using std::cin;
  7. using std::endl;
  8. using std::flush;
  9. using std::string;
  10. using std::vector;
  11.  
  12. bool isPalindrome(const string&);
  13. const char* result(bool);
  14.  
  15. int main(){
  16.  
  17. vector<string> values;
  18.  
  19. values.push_back("mom");
  20. values.push_back("ffaff");
  21. values.push_back("dad");
  22. values.push_back("nonPalindrome");
  23. values.push_back("blah");
  24. values.push_back("A");
  25. values.push_back("");
  26.  
  27. for(vector<string>::iterator i = values.begin(); i != values.end(); i++)
  28. cout << (*i) << " is a Palindrome? - " << result(isPalindrome((*i))) << endl;
  29.  
  30. cout << "\n\nEnter a word to be determined as a palindrome" << endl;
  31.  
  32. values[0].clear();
  33. cin >> values[0];
  34. cout << values[0] << " is a Palindrome? - " << result(isPalindrome(values[0])) << endl;
  35.  
  36. cin.ignore();
  37. cin.get();
  38. return 0;
  39. }
  40.  
  41. /**
  42.  * Returns true if the argument string is a palindrome, returns false otherwise
  43.  */
  44. bool isPalindrome(const string& arg){
  45.  
  46. /*
  47.   * LOGIC:
  48.   * -If string length is 0 or 1
  49.   * -string is a palindrome, so return true
  50.   * -Else
  51.   * -If first and last indice of said string have the same char
  52.   * -generate a new string that is a substring of this string
  53.   * discluding the first and last indice of the previous string
  54.   * -Else
  55.   * -return false
  56.   */
  57. string temp (arg);
  58.  
  59. if(temp.length() == 0 || temp.length() == 1)
  60. return true;
  61. else{
  62. if(temp[0] == temp[temp.length() - 1]){
  63. string next = temp.substr(1, temp.length() - 2); // substring from indice 1 and up to (length() - 2) from 1
  64. // i.e. - ffaff, f is at [1] and length is 5, so from 1 go up to 2+1
  65. // because even though length() - 2 is 3, we go up to 3 but not at 3
  66. // so only 2 is added
  67. return isPalindrome(next); // checking to see if the parsed string is a palindrome or not
  68. }else return false;
  69. }
  70. }
  71.  
  72. /**
  73.  * Convenience method for returning a stringified version of a boolean argument.
  74.  */
  75. const char* result(bool arg){
  76. return arg ? "TRUE" : "FALSE";
  77. }

--though it's probably not nearly as efficient as your implementation.

What you may want to consider is recursively calling your function by pre-incrementing index and pre-decrementing the length so you can simply check the characters of a string based on the parameters of your method and not have to mess around with arrays much.

It's just a suggestion, but I think you'll find things much easier that way =)
Reply With Quote Quick reply to this message  
Join Date: Oct 2008
Posts: 118
Reputation: chococrack is on a distinguished road 
Solved Threads: 14
chococrack's Avatar
chococrack chococrack is offline Offline
Junior Poster

Re: segmentation fault, recursive palindrome

 
0
  #3
Oct 31st, 2008
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. bool Palindrome(string pal, int index, int length)
  6. {
  7.  
  8. while(index < length)
  9. {
  10. if (length == 0 || length == 1)
  11. return true;
  12.  
  13. if (pal[index] != pal[length - index])
  14. return false;
  15. index++;
  16. }
  17.  
  18. return true;
  19.  
  20. }
  21.  
  22. int main () {
  23.  
  24. string word;
  25.  
  26. cout << "Enter your prospective palindrome." << endl;
  27. cin >> word;
  28. bool result = Palindrome(word, 0, word.length()-1);
  29. cout << word << "is";
  30. if(!result)
  31. cout << "NOT";
  32. cout << " a Palindrome." << endl;
  33. return 0;
  34. }

And for the record, I love the "Correct indentation" function of both Notepad++ and Eclipse Ganymede <3<3<3
Last edited by chococrack; Oct 31st, 2008 at 2:34 am. Reason: I posted the wrong codes pshew
I would love to change the world, but they won't give me the source code
Reply With Quote Quick reply to this message  
Join Date: Oct 2008
Posts: 11
Reputation: DragonReborn225 is an unknown quantity at this point 
Solved Threads: 0
DragonReborn225 DragonReborn225 is offline Offline
Newbie Poster

Re: segmentation fault, recursive palindrome

 
0
  #4
Oct 31st, 2008
lmao sorry about the indentation, and THANKS GUYS!!!!!!!!!!
Reply With Quote Quick reply to this message  
Join Date: Aug 2007
Posts: 1,674
Reputation: vmanes is a splendid one to behold vmanes is a splendid one to behold vmanes is a splendid one to behold vmanes is a splendid one to behold vmanes is a splendid one to behold vmanes is a splendid one to behold vmanes is a splendid one to behold 
Solved Threads: 193
vmanes's Avatar
vmanes vmanes is offline Offline
Posting Virtuoso

Re: segmentation fault, recursive palindrome

 
1
  #5
Oct 31st, 2008
What's the purpose of pal[index] = 30; ? You're changing the first character, thus making a test always fail?

Two things missing from your logic:
- The initial test of length == 0 only works on first call. Subsequent recursive calls must compare your shortened "word" length, which really should indicate index of character being compared, not actual string length. So, something like length-index== 0 is what you need.

- When making the recursive call, you must move in both the starting and ending points (index and length), and you must use preincrement/predecrement operators. Using post increment, as you do for index++, send the current value to the next call, not the update that you want to send.

Chococrack - your solution is iterative, while the OP seems to want/need a recursive solution. That said, your loop does twice the work it should, try while ( index < length/2 ) , and your line 13 has the infamous OBO error.
if (pal[index] != pal[length - index -1]) solves that - remember that length is count of items, last valid item in a zero-based counting is length-1.
"We Americans got so tired of being thought of as dumb by the rest of the world that we went to the polls last November and removed all doubt."
~~~~~~~~~~~~~~~~~~
Looking for an exciting graduate degree? Robotics and Intelligent Autonomous Systems (RIAS) at SDSM&T See the program brochure here.
Reply With Quote Quick reply to this message  
Join Date: Aug 2007
Posts: 1,674
Reputation: vmanes is a splendid one to behold vmanes is a splendid one to behold vmanes is a splendid one to behold vmanes is a splendid one to behold vmanes is a splendid one to behold vmanes is a splendid one to behold vmanes is a splendid one to behold 
Solved Threads: 193
vmanes's Avatar
vmanes vmanes is offline Offline
Posting Virtuoso

Re: segmentation fault, recursive palindrome

 
0
  #6
Oct 31st, 2008
Originally Posted by chococrack View Post
And for the record, I love the "Correct indentation" function of both Notepad++ and Eclipse Ganymede <3<3<3
Visual C++ can also automatically indent, and correct code that's gotten out of whack. Select the code, use ctrl-k f. I don't care for the exact way it handles switches, but it does the bulk of the work fine.
"We Americans got so tired of being thought of as dumb by the rest of the world that we went to the polls last November and removed all doubt."
~~~~~~~~~~~~~~~~~~
Looking for an exciting graduate degree? Robotics and Intelligent Autonomous Systems (RIAS) at SDSM&T See the program brochure here.
Reply With Quote Quick reply to this message  
Join Date: Oct 2008
Posts: 11
Reputation: DragonReborn225 is an unknown quantity at this point 
Solved Threads: 0
DragonReborn225 DragonReborn225 is offline Offline
Newbie Poster

Re: segmentation fault, recursive palindrome

 
0
  #7
Oct 31st, 2008
The reason for the index = 30 thing was because I was getting segmentation faults, and I figured there wasn't enough space available or something after a quick google of those faults.

And maybe its just late, but I have no idea what you mean by preincrement/predecrement operators. Could you please give an example if your still around? Thanks.

edit: I'm thinking you mean index = index + 1, but isn't that the same thing as index++, so I guess I still don't know what you mean lol.
Last edited by DragonReborn225; Oct 31st, 2008 at 3:14 am.
Reply With Quote Quick reply to this message  
Join Date: Aug 2007
Posts: 1,674
Reputation: vmanes is a splendid one to behold vmanes is a splendid one to behold vmanes is a splendid one to behold vmanes is a splendid one to behold vmanes is a splendid one to behold vmanes is a splendid one to behold vmanes is a splendid one to behold 
Solved Threads: 193
vmanes's Avatar
vmanes vmanes is offline Offline
Posting Virtuoso

Re: segmentation fault, recursive palindrome

 
0
  #8
Oct 31st, 2008
return Palindrome(pal, index++, length) when this call is made, the current value of index is passed, then index is incremented (made larger by 1)

Putting the ++ after the variable, as you've done, is postincrementing - use the value, then increment it. Putting the ++ in front of the variable preincments - changes the value, then uses the new value. In order to pass the value of (index+1) to the recursive function call, you need the preincrement.

For that matter, you could have clearly shown intent (and not gotten any possible confusion) by writing the call as return Palindrome(pal, index+1, length-1)

Try this:
  1. int x = 5;
  2. cout << x << endl; //shows 5
  3. cout << x++ << endl; //still shows 5
  4. cout << x << endl; //now we see 6
  5.  
  6. cout << ++x << endl; //shows 7
"We Americans got so tired of being thought of as dumb by the rest of the world that we went to the polls last November and removed all doubt."
~~~~~~~~~~~~~~~~~~
Looking for an exciting graduate degree? Robotics and Intelligent Autonomous Systems (RIAS) at SDSM&T See the program brochure here.
Reply With Quote Quick reply to this message  
Join Date: Oct 2008
Posts: 11
Reputation: DragonReborn225 is an unknown quantity at this point 
Solved Threads: 0
DragonReborn225 DragonReborn225 is offline Offline
Newbie Poster

Re: segmentation fault, recursive palindrome

 
0
  #9
Oct 31st, 2008
thanks for the added help man. Just one question though, whats the point of post-incrementing if pre-incrementing is instantaneous? also did you see any tell tale signs that led to my segmentation faults?? thanks again, and no matter if you didn't see any, you've wasted enough time on this already lol.

edit: working perfectly!!! thanks everyone.
Last edited by DragonReborn225; Oct 31st, 2008 at 3:31 am.
Reply With Quote Quick reply to this message  
Join Date: Oct 2008
Posts: 118
Reputation: chococrack is on a distinguished road 
Solved Threads: 14
chococrack's Avatar
chococrack chococrack is offline Offline
Junior Poster

Re: segmentation fault, recursive palindrome

 
0
  #10
Oct 31st, 2008
Originally Posted by vmanes View Post
Visual C++ can also automatically indent, and correct code that's gotten out of whack. Select the code, use ctrl-k f. I don't care for the exact way it handles switches, but it does the bulk of the work fine.

I have a tendency to work away from Visual C++, no idea why. I think its not aesthetically pleasing enough for me and I find it a bit cumbersome.

I usually work with Notepad++ for small pieces of code, Eclipse Ganymede for usual everyday projects.

I know what you mean about the switch statements, it seems to be universal in the way it gets indented.

  1. switch(num)
  2. {
  3. case 1:
  4. {
  5. }
  6. case 2:
  7. {
  8. }
  9. default:
  10. {
  11. }
  12. }

so ugly.
I would love to change the world, but they won't give me the source code
Reply With Quote Quick reply to this message  
Reply

This thread has been marked solved.
Perhaps start a new thread instead?
Message:



Other Threads in the C++ Forum
Thread Tools Search this Thread



About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC