Expression Parser

expression.cs

void Main() {
	EnsureFailure(
		"",
		"#",
		"1 + 2 +",
		"+",
		"(+)1",
		"()",
		"1 ()",
		"1 2"
		);
		
	Evaluate("-1");
	Evaluate("-1 + 2");
	Evaluate("1 + -2");
	Evaluate("1 + 2");
	Evaluate("1 + 2 * 3");
	Evaluate("1 * 2 * 3");
	Evaluate("1 * 2 + 3");
	Evaluate("1 * (2 + 3)");
	Evaluate("true");
	Evaluate("not true");
//	Evaluate("(123 + abc) / 2");
	Evaluate("-1 + -4 = -(2 + 3)");
	Evaluate("-1 + -4 = -(2 + 3) or true and false");
	Evaluate("--++---+++8");
}

void EnsureFailure(params string[] expressions) {
	foreach (var expression in expressions) {
		try {	        
			Evaluate(expression);
		} catch  {
			continue;
		}
		throw new Exception("Expression failed to fail: " + expression);
	}
}

void Evaluate(string expression) {
	expression.Dump("original");

	var tokens = Tokenize(expression);
	var postfix = ConvertToPostfix(tokens);
	
//	postfix.Select (p => p.ToString()).Dump(0);
	
	var ast = BuildAst(postfix);
	ast.ToString().Dump("ast");
	ast.GetExpressionType().Dump("type");
	ast.Evaluate().Dump();
}

Expression BuildAst(IList<StackInstruction> postfix) {
	var evaluationStack = new Stack<Expression>();
	
	foreach (var instruction in postfix) {
		evaluationStack.Push(instruction.ConvertToExpression(evaluationStack));
	}
	
	return evaluationStack.Single();
}

List<StackInstruction> ConvertToPostfix(IList<Token> tokens) {
	var shuntedOperators = new Stack<IShuntable>();
	var postfixOutput = new List<StackInstruction>();
	
	bool needExpression = true;
	
	foreach (var token in tokens) {
		if (token is OperatorToken) {
			var @operator = (OperatorToken)token;
			if (needExpression) {
				if ([email protected]) throw new Exception("needed value, found " + token.ToString());
			}
			while (!needExpression && shuntedOperators.Any()) {
				var shuntedOperator = shuntedOperators.Peek() as Operator;
				if (shuntedOperator == null) break;
				
				var thisOperator = (OperatorToken)token;
						
				if (shuntedOperator is BinaryOperator && thisOperator.Precedence > shuntedOperator.Token.Precedence) {
					break;
				}
				
				postfixOutput.Add(shuntedOperator);
				shuntedOperators.Pop();
			}

			if (needExpression) {
				// prefix unary operator
				shuntedOperators.Push(new UnaryOperator((OperatorToken)token));
			} else {
				// infix binary operator
				shuntedOperators.Push(new BinaryOperator((OperatorToken)token));
			}
			needExpression = true;
		
		} else if (token is CommaToken) {
			if (needExpression) throw new Exception("Unexpected " + token.ToString());
			needExpression = true;
			
		} else if (token is OpenParenToken) {
			shuntedOperators.Push(new ParenContext());
			if (!needExpression) throw new Exception("Unexpected " + token.ToString());
			
		} else if (token is CloseParenToken) {
			if (needExpression) throw new Exception("Unexpected " + token.ToString());
			for (var t = shuntedOperators.Pop(); t is Operator; t = shuntedOperators.Pop()) {
				postfixOutput.Add((Operator)t);
			}
		} else if (token is ValueToken) {
			if (!needExpression) throw new Exception("Unexpected " + token.ToString());
			postfixOutput.Add(new ValueInstruction((ValueToken)token));
			needExpression = false;
		} else {
			token.Dump();
			throw new Exception("Unexpected token type");
		}
	}
	
	if (needExpression) throw new Exception("unexpected end");
	
	while (shuntedOperators.Any()) postfixOutput.Add((Operator)shuntedOperators.Pop());
	
	return postfixOutput;
}

List<Token> Tokenize(string expression) {
	var tokens = new List<Token>();
	var index = -1;
	
	while (++index < expression.Length) {
		if (char.IsWhiteSpace(expression[index])) continue;
		switch (expression[index]) {
			case '(':
				tokens.Add(new OpenParenToken());
				continue;
			case ')':
				tokens.Add(new CloseParenToken());
				continue;
			case '+':
				tokens.Add(new PlusToken());
				continue;
			case '*':
				tokens.Add(new MultiplyToken());
				continue;
			case '-':
				tokens.Add(new MinusToken());
				continue;
			case '/':
				tokens.Add(new DivideToken());
				continue;
			case ',':
				tokens.Add(new CommaToken());
				continue;
			case '=':
				tokens.Add(new EqualsToken());
				continue;
		}
		
		if (char.IsWhiteSpace(expression[index])) continue;
		
		if (char.IsDigit(expression[index])) {
			int total = 0;
			while (index < expression.Length && char.IsDigit(expression[index])) {
				total = total * 10 + ((int)expression[index++] - (int)'0');
			}
			--index;
			tokens.Add(new NumberLiteralToken(total));
		}
		
		if (char.IsLetter(expression[index])) {
			var builder = new StringBuilder();
			while (index < expression.Length && char.IsLetterOrDigit(expression[index])) {
				builder.Append(expression[index++]);				
			}
			--index;
			
			string name = builder.ToString();
			switch (name) {
				case "and":
					tokens.Add(new AndToken());
					break;
				case "or":
					tokens.Add(new OrToken());
					break;
				case "true":
					tokens.Add(new BooleanLiteralToken(true));
					break;
				case "false":
					tokens.Add(new BooleanLiteralToken(false));
					break;
				case "not":
					tokens.Add(new NotToken());
					break;
				default:
					tokens.Add(new IdentifierToken(name));
					break;			
			}
		}
	}
	
	return tokens;
}

abstract class Token {
	public virtual Expression GenerateExpression(Stack<Token> evaluationStack) {
		throw new NotSupportedException();
	}
}

class OpenParenToken : Token {}

class CloseParenToken : Token {}

abstract class OperatorToken : Token {
	public readonly int Precedence;
	public readonly bool IsPrefixable;
	protected OperatorToken(int precedence, bool isPrefix = false) {
		this.Precedence = precedence;
		this.IsPrefixable = isPrefix;
	}

	public virtual ExpressionType GetResultType(ExpressionType operandType) {
		return ExpressionType.TypeError;
	}

	public virtual ExpressionType GetResultType(ExpressionType left, ExpressionType right) {
		return ExpressionType.TypeError;
	}
	
	public virtual object ApplyUnary(Expression operand) {
		throw new InvalidOperationException(this.GetType() + " does not support unary application");
	}

	public virtual object ApplyBinary(Expression left, Expression right) {
		throw new InvalidOperationException(this.GetType() + " does not support binary application");
	}
}

class MinusToken : OperatorToken {
	public MinusToken() : base(4, true) { }

	public override ExpressionType GetResultType(ExpressionType operandType) {
		switch (operandType) {
			case ExpressionType.Number: return ExpressionType.Number;
			default: return ExpressionType.TypeError;
		}
	}

	public override ExpressionType GetResultType(ExpressionType left, ExpressionType right) {
		if (left == ExpressionType.Number && right == ExpressionType.Number) {
			return ExpressionType.Number;
		} else {
			return ExpressionType.TypeError;
		}
	}
	
	public override object ApplyUnary(Expression operand) {
		return -(int)operand.Evaluate();
	}

	public override string ToString() { return "-"; }
}

class PlusToken : OperatorToken {
	public PlusToken() : base(4, true) { }

	public override ExpressionType GetResultType(ExpressionType operandType) {
		switch (operandType) {
			case ExpressionType.Number: return ExpressionType.Number;
			default: return ExpressionType.TypeError;
		}
	}

	public override ExpressionType GetResultType(ExpressionType left, ExpressionType right) {
		if (left == ExpressionType.Number && right == ExpressionType.Number) {
			return ExpressionType.Number;
		} else {
			return ExpressionType.TypeError;
		}
	}
	
	public override object ApplyBinary(Expression left, Expression right) {
		return (int)left.Evaluate() + (int)right.Evaluate();
	}

	public override object ApplyUnary(Expression operand) {
		return (int)operand.Evaluate();
	}

	public override string ToString() { return "+"; }
}

class DivideToken : OperatorToken {
	public DivideToken() : base(5) { }

	public override ExpressionType GetResultType(ExpressionType left, ExpressionType right) {
		if (left == ExpressionType.Number && right == ExpressionType.Number) {
			return ExpressionType.Number;
		} else {
			return ExpressionType.TypeError;
		}
	}

	public override object ApplyBinary(Expression left, Expression right) {
		return (int)left.Evaluate() / (int)right.Evaluate();
	}

	public override string ToString() { return "/"; }
}

class MultiplyToken : OperatorToken {
	public MultiplyToken() : base(5) { }

	public override ExpressionType GetResultType(ExpressionType left, ExpressionType right) {
		if (left == ExpressionType.Number && right == ExpressionType.Number) {
			return ExpressionType.Number;
		} else {
			return ExpressionType.TypeError;
		}
	}

	public override object ApplyBinary(Expression left, Expression right) {
		return (int)left.Evaluate() * (int)right.Evaluate();
	}

	public override string ToString() { return "*"; }
}

class AndToken : OperatorToken {
 	public AndToken() : base (2) {}

	public override ExpressionType GetResultType(ExpressionType left, ExpressionType right) {
		if (left == ExpressionType.Boolean && right == ExpressionType.Boolean) {
			return ExpressionType.Boolean;
		} else {
			return ExpressionType.TypeError;
		}
	}

	public override string ToString() { return "and"; }
}

class OrToken : OperatorToken {
	public OrToken() : base(1) {}

	public override ExpressionType GetResultType(ExpressionType left, ExpressionType right) {
		if (left == ExpressionType.Boolean && right == ExpressionType.Boolean) {
			return ExpressionType.Boolean;
		} else {
			return ExpressionType.TypeError;
		}
	}

	public override object ApplyBinary(Expression left, Expression right) {
		return (bool)left.Evaluate() || (bool)right.Evaluate();
	}

	public override string ToString() { return "or"; }
}

class NotToken : OperatorToken {
	public NotToken() : base(3, true) { }
	
	public override object ApplyUnary(Expression operand) {
		return !(bool)operand.Evaluate();
	}

	public override ExpressionType GetResultType(ExpressionType operandType) {
		switch (operandType) {
			case ExpressionType.Boolean: return ExpressionType.Boolean;
			default: return ExpressionType.TypeError;
		}
	}
	
	public override string ToString() {
		return "not";
	}
}

class EqualsToken : OperatorToken {
	public EqualsToken() : base(3) {}

	public override ExpressionType GetResultType(ExpressionType left, ExpressionType right) {
		if (left == right) {
			return ExpressionType.Boolean;
		} else {
			return ExpressionType.TypeError;
		}
	}
	
	public override object ApplyBinary(Expression left, Expression right) {
		return left.Evaluate().Equals(right.Evaluate());
	}

	public override string ToString() { return "="; }
}

class CommaToken : Token { }

abstract class ValueToken : Token {
	public abstract ExpressionType ValueType { get; }
	
	public abstract object GetValue();
}

class NumberLiteralToken : ValueToken {
	public readonly int Value;

	public override ExpressionType ValueType { 
		get { return ExpressionType.Number; } 
	}
	
	public NumberLiteralToken(int value) {
		this.Value = value;
	}

	public override object GetValue() {
		return this.Value;
	}
	
	public override string ToString() {
		return this.Value.ToString();
	}
}

class BooleanLiteralToken : ValueToken {
	public readonly bool Value;
	
	public override ExpressionType ValueType { 
		get { return ExpressionType.Boolean; } 
	}
	
	public BooleanLiteralToken(bool value) {
		this.Value = value;
	}
	
	public override object GetValue() {
		return this.Value;
	}
	
	public override string ToString() {
		return this.Value.ToString();
	}
}

class IdentifierToken : ValueToken {
	public readonly string Name;
	
	public IdentifierToken(string name) {
		this.Name = name;
	}
	
	public override ExpressionType ValueType { 
		get {  return ExpressionType.TypeError; } 
	}
	
	public override object GetValue() {
		throw new NotImplementedException();
	}
	
	public override string ToString() {
		return string.Format("[{0}]", this.Name);
	}
}

interface IShuntable { }

class ParenContext : IShuntable { }

abstract class StackInstruction { 
	public abstract Expression ConvertToExpression(Stack<Expression> evaluationStack);
}

class ValueInstruction : StackInstruction {
	public readonly ValueToken ValueToken;
	
	public ValueInstruction(ValueToken valueToken) {
		this.ValueToken = valueToken;
	}

	public override Expression ConvertToExpression(Stack<Expression> evaluationStack) {
		return new ValueExpression(this.ValueToken);
	}
}

abstract class Operator : StackInstruction, IShuntable {
	public readonly OperatorToken Token;
	
	public Operator(OperatorToken token) {
		this.Token = token;
	}
}

class BinaryOperator : Operator {
	public BinaryOperator(OperatorToken token) : base (token) { }

	public override Expression ConvertToExpression(Stack<Expression> evaluationStack) {
		return new BinaryExpression(base.Token, evaluationStack.Pop(), evaluationStack.Pop());
	}
}

class UnaryOperator : Operator {
	public UnaryOperator(OperatorToken token) : base(token) { }

	public override Expression ConvertToExpression(Stack<Expression> evaluationStack) {
		return new UnaryExpression(base.Token, evaluationStack.Pop());
	}
}

enum ExpressionType {
	TypeError,
	Number,
	Boolean,
	String,
	Date,
}

abstract class Expression {
	public abstract ExpressionType GetExpressionType();
	
	public abstract object Evaluate();
}

class ValueExpression : Expression {
	public readonly ValueToken ValueToken;
	
	public ValueExpression(ValueToken valueToken) {
		this.ValueToken = valueToken;	
	}
	
	public override ExpressionType GetExpressionType() {
		return this.ValueToken.ValueType;
	}
	
	public override object Evaluate() {
		return this.ValueToken.GetValue();
	}
	
	public override string ToString() {
		return this.ValueToken.ToString();
	}
}

class UnaryExpression : Expression {
	public readonly Expression Operand;
	public readonly OperatorToken Operator;
	
	public UnaryExpression(OperatorToken @operator, Expression operand) {
		this.Operator = @operator;
		this.Operand = operand;
	}
	
	public override ExpressionType GetExpressionType() {
		return this.Operator.GetResultType(this.Operand.GetExpressionType());
	}
	
	public override object Evaluate() {
		return this.Operator.ApplyUnary(this.Operand);
	}
	
	public override string ToString() {
		return string.Format("{0} {1}", this.Operator, this.Operand);
	}
}

class BinaryExpression : Expression {
	public readonly Expression Right;
	public readonly Expression Left;
	public readonly OperatorToken Operator;
	
	public BinaryExpression(OperatorToken @operator, Expression right, Expression left) {
		this.Operator = @operator;
		this.Right = right;
		this.Left = left;
	}

	public override ExpressionType GetExpressionType() {
		return this.Operator.GetResultType(this.Left.GetExpressionType(), this.Right.GetExpressionType());
	}
	
	public override object Evaluate() {
		return this.Operator.ApplyBinary(this.Left, this.Right);
	}
	
	public override string ToString() {
		return string.Format("({0} {1} {2})", this.Left, this.Operator, this.Right);
	}
}