Skip to main content
GameDev.net gamedev.net
🔒 Locked

How does this work?

Started by whiz_kid Jan 10, 2005 at 9:56 PM 13 replies 2.3k views
Original Post
whiz_kid
whiz_kid
So I had to take a test in c++ today and part of the test was writing a program that would reverse a string. I had no idea what I was going to do when I started out, but soon enough I started typing and came up with something. The problem is, I have no idea how the program works and would like some kind of an explanation. The program really isn't that complicated. Here it is: 

#include <iostream>
#include <ctype.h>
using namespace std;

int main()
{
    //declare the array and counters
    char array[27] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    int counter,elements,letters;
    
    //display the original array
    cout << array << endl;
    
    //get the string length of the array and set elements equal to letters
    letters = strlen(array);
    elements = letters;

    //make a loop that uses each element of the array
    for(counter=0;counter <= letters-1;counter++)
    {
        //confused here?
        array[counter] = array[counter] + (elements - 1);
        elements = elements - 2;
    }

    //display the reversed array
    cout << array << endl;

    return(0);
}
Thanks!
--------------------------------A man of few words does not mean he does not have big ideas
Deyja
Deyja
What you are doing is flipping the ASCII value. This only works because your string happens to be ABCDEFGHIJKLMOPQRSTUVWXYZ. If you gave it ABC, you'd get ZYX, which is obviously wrong.

Do it this way instead:

std::string in = "Some string here.";std::string out;for (unsigned int i = in.length()-1; i >= 0; --i) out += in;


[edit]Does std::string have push_back? Oops.[/edit]

[Edited by - Deyja on January 10, 2005 10:01:36 PM]
choffstein
choffstein
Basically, where you are stuck, is with some tricky ASCII math.

So lets go through the algorithm to show how it works.

Elements is going to be equal to 26;
Counter begins at 0.

So we set
array[0] to the value at array 0 ('A') + (Elements-1)

Well, Elements-1 = 25, so the ASCII code 'A' + 25 is the ascii code 'Z'
Pretend 'A' is one. 1 + 25 = 26, so it makes sense that it is Z.

So then we decrement elements by 2, so it is 24.
We increment counter, so it is 1. Now we have:
array[1] = array[1] ('B') + (Elements -1)
array[1] = 'B' + 23

'B' + 23 is the ASCII code for 'Y'.
If B is 2, 2 + 23 = 25, which is Y, right?


And so on, and so forth. So what happens at the end of the array? Well, by that point, elements will be negative, so it will look something like:

array[26] = 'Z' + (elements - 1);
Z + ( -25) = 'A'



And that is how it works!
whiz_kid
whiz_kid
Thanks Visage! This is exactly what I needed.
--------------------------------A man of few words does not mean he does not have big ideas
Deyja
Deyja
Yes, that's how it works, but it does NOT reverse a string.

Prove it to yourself: Change the input string to just "ABC" and see what you get out.
Zahlman
Zahlman
Quote:
Original post by Deyja
Do it this way instead:

std::string in = "Some string here.";std::string out(in.rbegin(), in.rend());// for (unsigned int i = in.length()-1; i >= 0; --i) out += in;


[smile]
SiCrane
SiCrane
Or to reverse the string in place:
std::string in = "Some string here.";std::reverse(in.begin(), in.end());

It can even work on the original char array:
char array[27] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";std::reverse(array, array + 26);

Nice Coder
Nice Coder
:)

for future reference

*Beginning*end // These point to the beginning of the string, and the end of the new string. *(&end + 1) = '\0' //Shove a null at the end of the stringwhile(begin) {              //While were not at the end of the string       (*end--) = (*Begin++); //Do the copy, including moving the pointers};


Simple,
Effective
Fast.

Everything you'd want in code.

It basically runs like this:
You go, and you get the character which end points to, and you make it the character that begin points too.
You then move the end one chr down, and beginning one chr up.
If begin is 0, then your at the end of the first string

This basically reverses the string.

From,
Nice coder
Click here to patch the mozilla IDN exploit, or click Here then type in Network.enableidn and set its value to false. Restart the browser for the patches to work.
SiCrane
SiCrane
Quote:
Original post by Nice Coder
Everything you'd want in code.

No, what I'd want first is code that works. Yours doesn't.

while(begin) will loop until the value of the begin pointer equals 0, which it probably never will since your code will most likely seg fault before it wraps around to 0.

Assuming you tried to fix that bug by turning it into while(*begin), your code still won't reverse the string. It will reverse the string up to the point that the pointers will pass each and then the loop will then merrily write the original portion of the loop back into the first half, so what you end up with is a mangled palindrome string, not a reversed string.
Enigma
Enigma
Actually if you read his comments Nice Coder's algorithm uses two strings. It does not do in place reversal, so althought the failure to dereference is a bug, if this is fixed (and the incorrect operator& on the third line) the algorithm does work. But since this is C++ Deyja or SiCrane's solutions are the best.

Enigma
Nice Coder
Nice Coder
[grin] I'm not too got at C++.
Programming, yes.
C(++), no.
I keep forgetting part of the syntax...

So, it should be

*Beginning*end // These point to the beginning of the string, and the end of the new string, respectivelly.*(end + 1) = '\0' //Shove a null at the end of the string (which could just be an array), if ones not already therewhile(*begin) {              //While were not at the end of the string       (*end--) = (*Begin++); //Do the copy, including moving the pointers};// outputs, end is now the pointer to the new (reversed) copy of the first string. Beginning is now a pointer, to the null at the end of the first string.

?

And yes, it doesn't do in-place reversal.

// Added source tags
From,
Nice coder
Click here to patch the mozilla IDN exploit, or click Here then type in Network.enableidn and set its value to false. Restart the browser for the patches to work.
Deyja
Deyja
The problem with the academic setting is that if you used std::reverse and actually turned it in you'd probably get an F.
Zahlman
Zahlman
Quote:
Original post by SiCrane
Or to reverse the string in place:
std::string in = "Some string here.";std::reverse(in.begin(), in.end());

It can even work on the original char array:
char array[27] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";std::reverse(array, array + 26);


I knew something like that was hanging around, was only looking in the actual class methods though. Is std::reverse in or something? :)
whiz_kid
whiz_kid
Thanks for all the responses! But since our high school only has Visual C++ 1.52, I'm not able to use the string classes. Also, before I took the test, in an earlier assignment, I used a bubble sort to reverse the string. The problem was my teacher didn't think it plausible since it was something we hadn't learned yet. Otherwise, it would have been a lot easier for me.

Thanks!
--------------------------------A man of few words does not mean he does not have big ideas
rileyneedzhelp
rileyneedzhelp
hi,
I really need some help. In school i work with DrScheme, and i can't find a thread anywhere so maybe y'all can help me. I have to design a game in DrScheme under the beginning student with abbreviated lists teachpack. If anyone could help me that would be great or show me where i can get help

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.