A long time ago I implemented a game state system based on an article/tutorial I found on the web. It was a lot like this one, but I don't think it was exactly this article:
http://gamedevgeek.com/tutorials/managing-game-states-in-c/

Anyway, that's the rough design of it, though I don't have the stack of states (although looking at the downloaded code... I couldn't immediately see what advantage the stack gave but maybe I'm tired) like in that one.

As you can see, whenever a state changes, the new stats has its init() function called which initializes the state. That's fine but now I've come across problems when you want to return to already created states when certain things should only occur once and I'm not totally sure how to approach reorganizing things.

For example, I have my GameplayState that handles the in-game state of my program. The init() function clears any keyboard/mouse input handlers set up by previous states and sets up its own (which should happen every time the state is changed back to GameplayState) but it also does a few other things, one of which is loading XML data about game Tiles and another is loading the game's first level from XML.
Clearly, that's going to cause major problems if they're being called every time the state changes back. Right now I'm implementing level transitions so when the player gets to a certain location in level 1, the game moves to level 2. I'm doing that by first entering an intermediate InterLevelState which will consist of a black screen with some info on it, then the user presses return to proceed to the next level.
Now obviously, if level 1 is finished, then the new level is loaded somehow and the state changed to InterLevelState... as soon as it changes back to GameplayState it's just going to call the original loadMap() function and start again on level 1.

How should I approach this? I've a few partially-developed ideas but I don't know which approach makes more sense.
Do I really NEED the ability to call some things the first time a state is run, or should that be structured differently altogether so that it's hopefully unnecessary?
I'm thinking, I could have a "currentLevel" variable of some kind and then GamePlayState could just call that to load the level all the time or something, but then what about loading data from XML? If it's only required for GameplayState, then surely I shouldn't load it any earlier... but if it never changes then I shouldn't load it needlessly so I can't see a way around that.

Another related question: Say I have a top down shooter where WASD controls a player character. Then I want to implement some kind of purchasing system where the player does something that brings up a menu where WASD now serves to alter the menu selections. Seems to me that making that a different state would be inappropriate (especially if you hypothetically wanted to pop the menu up with the gameplay still in the background) so what then is a neat way of handling the different input "states" within the same program state? Some kind of simple variable/enum system that determines what the keys do?

if( gameplay )
{
WASD = movement
}
else if( menu )
{
WASD = menu
}

Something like that?

I assume your creating states each time?

Right now every state is a singleton, so when changing state I just set the Engine's currentState member to the static instance of the appropriate state.

So every state is created at startup I suppose...

Here's an idea:
On level change, GamePlayState creates a new "LevelTransitionState" (the loading screen), passes in the object that contains the level data and information required to load the new level and then pushes the new state onto the state manager or whatever you have. The LevelTransitionState then does what ever it does, loads up a new level, displays some progress bar or whatever you want. Once its complete maybe it has a button saying "Ready". You press ready and it just pops itself off the stack. GamePlayState just continues as normal (no reloading required) just this time it has new level data all ready.

Yeah, I'd considered using some kind of parameters for the level transition, though the way I have it implemented now... I couldn't really pass data into its constructor but I suppose just as good would be for the transition state to access some data in the GameplayState maybe.

As for your top down shooter, I would create a new state (The shop menu) and push it onto the stack. My GameStateMachine takes input and just passes it to whatever state is on the top of the stack (no need for things to deregister/reregister for key input). Each GameState has its own mouse move/key press methods and so can handle input completely differently. When your finished shopping, just pop off the stack.

What if hypothetically you wanted something like... a pop-up window that only filled part of the screen? You'd need the game to continue in the background (or pause but remain visible) so would a new state be impractical in that situation?

EDIT: I've been thinking about the stack of states...
Is it supposed to get around the problem of initializing a state multiple times? So that you just pop the current state and then go right back to the previous?

That's what I thought when I heard of it originally but that article seems to implement it in a rather pointless-looking way.
This is his changeState function:

void CGameEngine::ChangeState(CGameState* state)
{
// cleanup the current state
if ( !states.empty() ) {
states.back()->Cleanup();
states.pop_back();
}

// store and init the new state
states.push_back(state);
states.back()->Init();
}

It really confuses me because it seems as though the stack is essentially doing nothing. Every time the state is changed, the current state is popped off and the new one is put on and initialized. It seems to be no better than my current way of just having a pointer to the current state.

PopState seems to imply differently:

void CGameEngine::PopState()
{
// cleanup the current state
if ( !states.empty() ) {
states.back()->Cleanup();
states.pop_back();
}

// resume previous state
if ( !states.empty() ) {
states.back()->Resume();
}
}

But when changing to a new state always gets rid of the previous one... how could there ever be a state left on the stack to resume?

I'm confused

EDIT2: Never mind... it seems his changeState() function isn't to be used when moving between states all the time. He calls PushState() to go from the playState to the menuState and then PopState() to get back, but changeState() is used to get from the introState to the playState. I think I understand it now... hmmmm.