2. Program a parser to evaluate the string.
An example of the string that I need to execute is:
" (5 == 8) && (320 > 840) && (400.00 > 1000.00)"
A parser that can evaluate this is not difficult to program, if you know
how. For example, I coded the following, which can do what you're asking
for, in 35 minutes; it can easily enough be extended to handle variables
/ constants, functions, even assignment.
---8<---
using System;
class Program
{
static void Main()
{
for (;
{
Console.Write("eval> ");
Console.Out.Flush(); // for Cygwin rxvt
string line = Console.ReadLine();
if (line == null)
break;
try
{
Console.WriteLine(
QuickEvaluator.Evaluate(line));
}
catch (Exception ex)
{
Console.Error.WriteLine(ex.Message);
}
}
}
}
class QuickEvaluator
{
enum Token
{
Eof,
Identifier, Number,
Plus, Minus, Asterisk, Slash,
EqualTo, NotEqual, LessThan, GreaterThan,
LessEqual, GreaterEqual,
LParen, RParen,
BoolAnd, BoolOr, BoolNot
}
Token _token;
string _source;
int _currPos;
string _tokenAsString;
private QuickEvaluator(string source)
{
_source = source;
NextToken();
}
Token NextToken()
{
return _token = GetNextToken();
}
bool IsEof
{
get { return _currPos >= _source.Length; }
}
public static object Evaluate(string expression)
{
QuickEvaluator eval = new QuickEvaluator(expression);
object result = eval.EvalExpr(false);
eval.Expect(Token.Eof);
return result;
}
// Force non short-circuit operation
bool And(bool left, bool right)
{
return left && right;
}
bool Or(bool left, bool right)
{
return left || right;
}
object EvalExpr(bool skip)
{
object result = EvalCompareExpr(skip);
for (;
switch (_token)
{
case Token.BoolAnd:
result = And((bool) result,
(bool) EvalCompareExpr(true));
break;
case Token.BoolOr:
result = Or((bool) result,
(bool) EvalCompareExpr(true));
break;
default:
return result;
}
}
object EvalCompareExpr(bool skip)
{
object result = EvalAddExpr(skip);
for (;
switch (_token)
{
case Token.EqualTo:
result = object.Equals(result,
EvalAddExpr(true));
break;
case Token.NotEqual:
result = !object.Equals(result,
EvalAddExpr(true));
break;
case Token.LessThan:
result = ((double) result) <
((double) EvalAddExpr(true));
break;
case Token.GreaterThan:
result = ((double) result) >
((double) EvalAddExpr(true));
break;
case Token.LessEqual:
result = ((double) result) <=
((double) EvalAddExpr(true));
break;
case Token.GreaterEqual:
result = ((double) result) <=
((double) EvalAddExpr(true));
break;
default:
return result;
}
}
object EvalAddExpr(bool skip)
{
object result = EvalTerm(skip);
for (;
switch (_token)
{
case Token.Plus:
result = ((double) result) +
((double) EvalTerm(true));
break;
case Token.Minus:
result = ((double) result) -
((double) EvalTerm(true));
break;
default:
return result;
}
}
object EvalTerm(bool skip)
{
object result = EvalFactor(skip);
for (;
switch (_token)
{
case Token.Asterisk:
result = ((double) result) *
((double) EvalFactor(true));
break;
case Token.Slash:
result = ((double) result) /
((double) EvalFactor(true));
break;
default:
return result;
}
}
object EvalFactor(bool skip)
{
if (skip)
NextToken();
object result;
switch (_token)
{
case Token.Number:
result = double.Parse(_tokenAsString);
NextToken();
return result;
case Token.LParen:
result = EvalExpr(true);
Eat(Token.RParen);
return result;
case Token.Minus:
return - (double) EvalFactor(true);
case Token.Plus:
return EvalFactor(true);
case Token.BoolNot:
return ! ((bool) EvalFactor(true));
default:
throw new FormatException("Invalid factor.");
}
}
void Expect(Token token)
{
if (_token != token)
throw new FormatException(
string.Format("Expected {0}, got {1}.",
token, _token));
}
void Eat(Token token)
{
Expect(token);
NextToken();
}
Token GetNextToken()
{
// Skip whitespace
while (!IsEof && char.IsWhiteSpace(_source, _currPos))
++_currPos;
if (IsEof)
return Token.Eof;
// Identifier
if (char.IsLetter(_source, _currPos))
{
int start = _currPos;
while (!IsEof &&
char.IsLetterOrDigit(_source, _currPos))
++_currPos;
_tokenAsString =
_source.Substring(start, _currPos - start);
return Token.Identifier;
}
// Number
if (char.IsDigit(_source, _currPos))
{
int start = _currPos;
while (!IsEof && char.IsDigit(_source, _currPos))
++_currPos;
if (!IsEof && _source[_currPos] == '.')
{
++_currPos;
if (IsEof || !char.IsDigit(_source, _currPos))
throw new FormatException(
"Invalid floating-point number.");
while (!IsEof && char.IsDigit(_source, _currPos))
++_currPos;
if (!IsEof &&
"eE".IndexOf(_source[_currPos]) >= 0)
{
++_currPos;
if (!IsEof &&
"-+".IndexOf(_source[_currPos]) >= 0)
++_currPos;
if (IsEof)
throw new FormatException(
"Invalid floating-point number.");
while (!IsEof &&
char.IsDigit(_source, _currPos))
++_currPos;
}
}
_tokenAsString =
_source.Substring(start, _currPos - start);
return Token.Number;
}
// Single-character operator
switch (_source[_currPos++])
{
case '(': return Token.LParen;
case ')': return Token.RParen;
case '+': return Token.Plus;
case '-': return Token.Minus;
case '*': return Token.Asterisk;
case '/': return Token.Slash;
case '<':
if (!IsEof && _source[_currPos] == '=')
{
++_currPos;
return Token.LessEqual;
}
return Token.LessThan;
case '>':
if (!IsEof && _source[_currPos] == '=')
{
++_currPos;
return Token.GreaterEqual;
}
return Token.GreaterThan;
case '!':
if (!IsEof && _source[_currPos] == '=')
{
++_currPos;
return Token.NotEqual;
}
return Token.BoolNot;
// I'm not dealing with = versus == but
// it is similar
}
if (IsEof)
throw new FormatException(
"Invalid character in expression.");
// Two-character operator
string pair = _source.Substring(_currPos - 1, 2);
++_currPos;
switch (pair)
{
case "&&": return Token.BoolAnd;
case "||": return Token.BoolOr;
case "==": return Token.EqualTo;
}
throw new FormatException(
"Invalid character in expression.");
}
}
--->8---
-- Barry
