Contents

• State
• A Formal Definition of a State Machine
• Basic Pattern
• Example using BooleanInterpreter
• Final comments

From GoF: Allow an object to alter its behaviour when its internal state changes. The object will appear to change its class.

Use State when an object's behaviour is a function of its state and it must hange its behaviour at run-time depending on that state. Examples of such objects are usually parsers of some sort: objects which translate one structure into another such as an object which takes an expression like 'A & (B v C & (!D v A)) & E' and restructures as the BooleanExpression Interpreter pattern we looked at.

State is an implementation of a Finite State Machine.

The State Pattern is a Finite State Machine (FSM), a concept from Computer Science. A definition of an FSM from America's NIST:

• Context sets up required data, and reads the source structure one element at a time.
• For each element, it calls the current state object passing the element read.
• The State object processes the element and translates it as required, passing the result back to a property or method of Context. Depending on the results of its processing, it creates an instance of the appropriate State object to process the next element and passes it back as a return.
• The Context receives the new state object and uses it to process the next element.
• At the end, the Context returns the new structure built by the state objects.

• How is the next State object decided?
• How do the State objects store their output in the Context?

The first depends on the grammar defined for the input and output structures. The second is a matter of convenience � any way that makes sense. The first will generally be helped by a State Diagram. This is one for the BooleanExpression parser:

This leads us to 4 possible States:

• StartState: expecting the start of a binary operation. Valid characters are a Variable name, "(", and "!". The former transitions to OperatorState where an Operator is expected. "!" is pushed onto the Stack and the State is unchanged. "(" is discarded and the state is unchanged.
• OperatorState: Only valid operators are expected are "&" and "v". The operation is pushed onto the stack and the state changed to SecondState.
• SecondState: This expects the second Boolean in a binary expression. Valid characters are a Variable Name, "!", and "(". A Variable name it put on the stack and the stack collapsed into BooleanExpressions which are replaced on the stack; the State changes to EndState. A "!" is placed on the stack and the state remains unchanged. A "(" is discarded but the state changes to StartState.
• EndState: This covers various ways a Boolean binary can terminate. Valid characters are ")", and an operation. A ")" is discarded and the state changed to OperatorState. An Operation is put on the stack and the state changed to SecondState.

The CollapseStack method could have been in the Context object, but it was originally coded in SecondState as the only state which used it, and I haven't changed it. The code for the Context object (BooleanParser) and the states follows. Note the abstract BooleanState from which the concrete states inherit.

public class BooleanParser {
	protected string expression;
	public BooleanParser(string expression) {
		this.expression = expression.Replace(" ", "");
	}
	protected Stack stack;
	public BooleanExpression Parse() {
		stack = new Stack();
		BooleanState currentState = new StartState(this);	
		for (int i = 0; i < this.expression.Length; i++) {
			currentState = 
currentState.Handle(this.expression[i].ToString());
		}
		return stack.Pop() as BooleanExpression;
	}
	internal Stack Stack {
		get { return this.stack; }
	}
}
	
public abstract class BooleanState {
	public BooleanState(BooleanParser parser) {
		this.parser = parser;
	}
	protected BooleanParser parser;
	public virtual BooleanState Handle(string token) {
		switch (token) {
		case "&":
		case "v":
			return ProcessOp(token);
		case "!":
			return ProcessNot();
		case "(":
			return ProcessOpen();
		case ")":
			return ProcessClose();
		default:
			return ProcessVariable(token);
		}
	}
	public virtual BooleanState ProcessOp(string token) {
		throw new ApplicationException("Invalid expression");
	}
	public virtual BooleanState ProcessNot() {
		throw new ApplicationException("Invalid expression");
	}
	public virtual BooleanState ProcessOpen() {
		throw new ApplicationException("Invalid expression");
	}
	public virtual BooleanState ProcessClose() {
		throw new ApplicationException("Invalid expression");
	}
	public virtual BooleanState ProcessVariable(string token) {
		throw new ApplicationException("Invalid expression");
	}
}

public class StartState : BooleanState {
	public StartState(BooleanParser parser) : base(parser) {
	}
	public override BooleanState ProcessOp(string token) {
		throw new ApplicationException("Invalid expression");
	}
	public override BooleanState ProcessNot() {
		parser.Stack.Push("!");
		return this;
	}
	public override BooleanState ProcessOpen() {
		return this;
	}
	public override BooleanState ProcessClose() {
		throw new ApplicationException("Invalid expression");
	}
	public override BooleanState ProcessVariable(string token) {
		parser.Stack.Push(new VariableBooleanExpression(token));
		return new OperatorState(parser);
	}
}
public class OperatorState : BooleanState {
	public OperatorState(BooleanParser parser) : base(parser) {
	}
	public override BooleanState ProcessOp(string token) {
		parser.Stack.Push(token);
		return new SecondState(parser);
	}
}
public class SecondState : BooleanState {
	public SecondState(BooleanParser parser) : base(parser) {
	}
	public override BooleanState ProcessNot() {
		parser.Stack.Push("!");
		return this;
	}
	public override BooleanState ProcessOpen() {
		return new StartState(parser);
	}
	public override BooleanState ProcessVariable(string token) {
		parser.Stack.Push(token);
		CollapseStack();
		return new EndState(parser);
	}
	private void CollapseStack() {
		object second = parser.Stack.Pop();
		BooleanExpression secondExp = second as BooleanExpression;
		if (secondExp == null) {
				secondExp = new VariableBooleanExpresion(second as string);
		}
		string opA = parser.Stack.Pop() as string;
		if (opA == "!") {
			BooleanExpression innerExp = secondExp;
			secondExp = new NotBooleanExpression(innerExp);
			opA = parser.Stack.Pop() as string;
		}
		object first = parser.Stack.Pop();
		BooleanExpression firstExp = first as BooleanExpression;
		if (firstExp == null) {
			firstExp = new VariableBooleanExpression(first as string);
		}
		if ((parser.Stack.Count > 0)&&(parser.Stack.Peek() as string) == "!") {
			parser.Stack.Pop();
			BooleanExpression innerExp = firstExp;
			firstExp = new NotBooleanExpression(innerExp);
		}
		BooleanExpression finalExp = null;
		if (opA == "&") {
			finalExp = new AndBooleanExpression(firstExp, secondExp);
			} else {
			finalExp = new OrBooleanExpression(firstExp, secondExp);
		}
		parser.Stack.Push(finalExp);
		if (parser.Stack.Count > 1) {
			CollapseStack();
		}
	}
}
public class EndState : BooleanState {
	public EndState(BooleanParser parser) : base(parser) {
	}
	public override BooleanState ProcessOp(string token) {
		parser.Stack.Push(token);
		return new SecondState(parser);
	}
	public override BooleanState ProcessClose() {
		return new OperatorState(parser);
	}
}

This is a medium-complex instance of State: there are not many different States, but the processing (using a Stack and the CollapseStack method) is not entirely simple. However, I think that the code is reasonably clear. A much simpler example of State is given by Robert C Martin Robert C Martin) at Yonat Sharon's excellent OOTips site:

There is a specific design pattern that solves this problem.
It is called "State"; and can be found in the GOF book 
         |Account|<#>----|AccountState|
           ^                    A
           |                    |
           |              +-----+-----+
           |              |           |
           |       |OpenState|    |ClosedState|
           |           |               |
           +-----------+---------------+
Account contains a base class named AccountState.
There are two subclasses of AccountState named OpenState 
and ClosedState. Each of these contain a reference back 
to the |Account|. 
This allows methods of Account that are affected by the 
state to be delegated to the contained state object. 
The state object then calls the appropriate functions 
in the Account object.

• State behaviour is localised, simplifying changing or adding states
• State objects eliminate the need for complex if/switch structures, making the code easier to read and far more maintainable.
• State transitions are made explicit, as is state-dependant processing

• The States could be implemented as nested classes belonging to the Context class. They have no use outside that class, in this example, and could thus be declared within it. This is not uncommon.
• State classes do not contain state themselves and so can be Singletons or Flyweights
• The contents and structure of Context follow directly from a) its clients and b) what its State objects require from it. Usually the clients will require nothing more than a method similar to the Parse() method in the example. The requirements of the State objects depend on what is being achieved: in this case they needed a Stack to store temporary working data and which ended up containing the final structure.
• Context can make the decision on the successor state, rather than the state objects themselves. This would probably increase the communication needs between each State instance and the Context. Some people think that Context is the better or 'natural' place for that decision to be made. In all the examples I've done the natural place was in the State objects, but I may be missing something; it's probably a matter of style.
• If something only has two or three states, it is not overkill to use the State pattern.