EvalArithmetic.cs

// desc eval arithmetic
// note improve error handling
// maintainer hugoyu

using System;
using System.Diagnostics;
using System.Collections.Generic;

public class EvalArithmetic
{
	public enum Token
	{
		Num, // '123' etc.
		Add, // '+'
		Sub, // '-'
		Mul, // '*'
		Div, // '/'
		LP,  // '('
		RP,  // ')'
		Unknown,
	}
	
	bool IsSpace(char c)
	{
		return c == ' ' || c == '\t' || c == '\r' || c == '\n';
	}
	
	bool IsNum(char c)
	{
		return c >= '0' && c <= '9';
	}
	
	int ToNum(char c)
	{
		return c - '0';
	}
	
	bool IsOp(char c)
	{
		return c == '+' || 
			   c == '-' ||
			   c == '*' ||
			   c == '/' ||
			   c == '(' ||
			   c == ')';
	}
	
	Token OpToken(char c)
	{
		switch (c)
		{
			case '+':
				return Token.Add;
			case '-':
				return Token.Sub;
			case '*':
				return Token.Mul;
			case '/':
				return Token.Div;
			case '(':
				return Token.LP;
			case ')':
				return Token.RP;
		}
		
		return Token.Unknown;
	}
	
	bool ReachEnd(string expression, int checkIndex)
	{
		return checkIndex >= expression.Length;
	}
	
	void SkipSpace(string expression, ref int startIndex)
	{
		Debug.Assert(startIndex >= 0);
		var length = expression.Length;
		while (startIndex < length)
		{
			if (IsSpace(expression[startIndex]))
		    {
		    	++startIndex;
		    }
			else
			{
				break;
			}
		}
	}
	
	bool IsCalcToken(Token token)
	{
		return token == Token.Add ||
			   token == Token.Sub ||
			   token == Token.Mul ||
			   token == Token.Div;
	}
	
	int CompOp(Token a, Token b)
	{
		Debug.Assert(a != Token.Num && b != Token.Num && 
		             a != Token.RP && b != Token.RP);
		if (b == Token.LP)
		{
			// LP has lowest priority, even comp to LP itself
			return 1;
		}
		else if (a == Token.Add || a == Token.Sub)
		{
			return (b == Token.Add || b == Token.Sub) ? 0 : -1;
		}
		else
		{
			return (b == Token.Add || b == Token.Sub) ? 1 : 0;
		}
	}
	
	bool ParseNum(string expression, ref int startIndex, ref int parsedNum)
	{
		const int radix = 10;
		bool parsed = false;
		int num = 0;
		
		while (!ReachEnd(expression, startIndex))
		{
			var c = expression[startIndex];
			if (IsNum(c))
			{
				parsed = true;
				num = num * radix + ToNum(c);
				++startIndex;
			}
			else
			{
				break;
			}
		}
		
		if (parsed)
		{
			parsedNum = num;
		}
		
		return parsed;
	}
	
	bool ParseOp(string expression, ref int startIndex, ref Token opToken)
	{
		if (!ReachEnd(expression, startIndex))
		{
			char c = expression[startIndex];
			var op = OpToken(c);
			if (op != Token.Unknown)
			{
				// NOTE all op takes one char space now
				++startIndex;
				opToken = op;
				return true;
			}
		}
		
		return false;
	}
	
	bool ParseToken(string expression, ref int startIndex, ref TokenValue tokenValue)
	{
		int num = 0;
		Token token = Token.Unknown;
		
		if (ParseNum(expression, ref startIndex, ref num))
		{
			tokenValue.Token = Token.Num;
			tokenValue.Value = num;
			return true;
		}
		else if(ParseOp(expression, ref startIndex, ref token))
		{
			tokenValue.Token = token;
			// set value to 0 ? not so sure ...
			tokenValue.Value = 0;
			return true;
		}
		
		// just support num and op now
		return false;
	}
	
	bool IsZero(float value)
	{
		return Math.Abs(value) <= float.Epsilon;
	}
	
	bool Calc(float a, float b, Token op, ref float result)
	{
		switch (op)
		{
			case Token.Add:
				result = a + b;
				return true;
			case Token.Sub:
				result = a - b;
				return true;
			case Token.Mul:
				result = a * b;
				return true;
			case Token.Div:
				// can not divide 0
				if (!IsZero(b))
				{
				    result = a / b;
				    return true;
				}
				break;
		}
		
		return false;
	}
	
	public bool Eval(string expression, ref float result)
	{
		if (!string.IsNullOrEmpty(expression))
		{
			m_numStack.Clear();
			m_opStack.Clear();
				
			var startIndex = 0;
			var tokenValue = new TokenValue();
			var parseResult = false;
			
			while (!ReachEnd(expression, startIndex))
			{
			    SkipSpace(expression, ref startIndex);
			    parseResult = ParseToken(expression, ref startIndex, ref tokenValue);
			    if (!parseResult) return false;
			    
			    if (tokenValue.Token == Token.LP)
			    {
			    	// push LP token
			    	m_opStack.Push(Token.LP);
			    }
			    else if (tokenValue.Token == Token.RP)
			    {
			    	// pop op until LP token
			    	while (m_opStack.Count > 0)
			    	{
			    		var op = m_opStack.Pop();
			    		if (op == Token.LP)
			    		{
			    			// find match
			    			break;
			    		}
			    		else
			    		{
			    			// op stack will never have 'RP' and 'Num' token
			    			if (m_numStack.Count >= 2)
			    			{
			    				var rightValue = m_numStack.Pop();
			    				var leftValue = m_numStack.Pop();
			    				float opResult = 0;
			    				if (Calc(leftValue, rightValue, op, ref opResult))
			    				{
			    				    m_numStack.Push(opResult);
			    				}
			    				else
			    				{
			    					// calc error
			    					return false;
			    				}
			    			}
			    			else
			    			{
			    				// op and values no match
			    				return false;
			    			}
			    		}
			    	}
			    }
			    else if (tokenValue.Token == Token.Num)
			    {
			    	// push num
			    	m_numStack.Push(tokenValue.Value);
			    }
			    else
			    {
			    	var curOp = tokenValue.Token;
			    	
			    	if (m_opStack.Count > 0)
			    	{
			    		var lastOp = m_opStack.Peek();
			    		if (CompOp(curOp, lastOp) <= 0)
			    		{
			    			// means current is low or same priority op
			    			if (m_numStack.Count >= 2)
		    				{
				    			m_opStack.Pop();
		    					var rightValue = m_numStack.Pop();
			    				var leftValue = m_numStack.Pop();
			    				float opResult = 0;
			    				if (Calc(leftValue, rightValue, lastOp, ref opResult))
			    				{
			    				    m_numStack.Push(opResult);
			    				}
			    				else
			    				{
			    					// calc error
			    				    return false;
			    				}
			    			}
			    			else
		    				{
		    					// op and values no match
			    				return false;
			    			}
			    		}
			    	}
		    		
			    	// push current op
			    	m_opStack.Push(curOp);
			    }
			}
			
			// NOTE this cause right associate which is not correct,
			//      for example : a - b + c will result as a - (b + c),
			//      but here it is ok, since left associate (between same calc op) has already be handled before
			while (m_opStack.Count > 0)
			{
				if (m_numStack.Count >= 2)
				{
					var op = m_opStack.Pop();
					if (IsCalcToken(op))
					{
					    var rightValue = m_numStack.Pop();
    				    var leftValue = m_numStack.Pop();
    				    float opResult = 0;
	    				if (Calc(leftValue, rightValue, op, ref opResult))
	    				{
	    				    m_numStack.Push(opResult);
	    				}
	    				else
	    				{
	    					// calc error
	    				    return false;
	    				}
					}
					else
					{
						// unexpected op
						return false;
					}
				}
				else
				{
					// op and values no match
    				return false;
				}
			}
			
			if (m_numStack.Count == 1)
			{
			    result = m_numStack.Pop();
		        return true;
			}
			else
			{
				// error occur
				return false;
			}
		}
		
		// null or empty expression
		return false;
	}

	class TokenValue
	{
		public Token Token { get; set; }
		public int Value { get; set; }
	}
	
        Stack<float> m_numStack = new Stack<float>();
	Stack<Token> m_opStack = new Stack<Token>();
}