電卓クラスの利用イメージ
using System;
using System.Collections.Generic;
public class Demo
{
public static void Main()
{
// basic
Assert(2, "1 + 1");
Assert(1, "4-3");
Assert(6, "2*3");
Assert(14, "2 + 3 * 4");
Assert(10, "2 * 3 + 4");
Assert(10, "(2 * 3) + 4");
Assert(14, "2 * (3 + 4)");
Assert(6, "1 + 2 + 3");
Assert(24, "2 * 3 * 4");
Assert(2.4, "1.2 + 1.2");
Assert(1, "7 % 3");
Assert(8, "2 ^ 3");
Assert(3, "9 ^ 0.5");
// variable
Dictionary<string, double> vars = new Dictionary<string, double>();
vars["one"] = 1;
vars["two"] = 2;
Assert(6, "one + two * two + one", vars);
Assert(6, "1 + one + two * 2", vars);
// if
Assert(1, "IF(1=1, 1, 2)");
Assert(2, "IF(1=2, 1, 2)");
Assert(2, "IF(2>2, 1, 2)");
Assert(2, "IF(2<2, 1, 2)");
Assert(1, "IF(2>=2, 1, 2)");
Assert(1, "IF(2<=2, 1, 2)");
// if + variable
Assert(1, "IF(one=1, 1, 2)", vars);
Assert(2, "IF(one=2, 1, 2)", vars);
Assert(3, "IF(one=3, 1, IF(one=2, 1, 3))", vars);
Assert(4, "IF(one=3, 1, IF(one=1, 4, 3))", vars);
// invalid expression
AssertEx(typeof(KeyNotFoundException), "1 ++");
AssertEx(typeof(FormatException), "1.2.2 + 1.2");
// left associative
Assert(0, "3 - 2 - 1");
Assert(1, "4 / 2 / 2");
// bugfix
Assert(1, "IF(2<=3, 1, 2)");
Console.ReadLine();
}
static void Assert(double expect, string exp, Dictionary<string, double> vars = null)
{
Calc c = new Calc(exp);
string tree = c.Show();
double ret = c.Eval(vars);
string mark = expect == ret ? "o" : "x";
Console.WriteLine(string.Format("{0}: {1,3} = {2,-32} | {3}",
mark,
ret,
exp,
tree
));
}
static void AssertEx(Type expect, string exp, Dictionary<string, double> vars = null)
{
try
{
Calc c = new Calc(exp);
c.Eval(vars);
}
catch (Exception e)
{
string mark = e.GetType() == expect ? "o" : "x";
Console.WriteLine("{0}: {1,-38} | {2}", mark, e.GetType().Name + " = " + exp, e.Message);
return;
}
throw new Exception("Not throw exception " + expect.Name + " : " + exp);
}
}
実行結果
o: 2 = 1 + 1 | Tree(+, Node(1), Node(1)) <tokens='1 + 1' pos=3 text=1+1>
o: 1 = 4-3 | Tree(-, Node(4), Node(3)) <tokens='4 - 3' pos=3 text=4-3>
o: 6 = 2*3 | Tree(*, Node(2), Node(3)) <tokens='2 * 3' pos=3 text=2*3>
o: 14 = 2 + 3 * 4 | Tree(+, Node(2), Tree(*, Node(3), Node(4))) <tokens='2 + 3 * 4' pos=5 text=2+3*4>
o: 10 = 2 * 3 + 4 | Tree(+, Tree(*, Node(2), Node(3)), Node(4)) <tokens='2 * 3 + 4' pos=5 text=2*3+4>
o: 10 = (2 * 3) + 4 | Tree(+, Tree(*, Node(2), Node(3)), Node(4)) <tokens='( 2 * 3 ) + 4' pos=7 text=(2*3)+4>
o: 14 = 2 * (3 + 4) | Tree(*, Node(2), Tree(+, Node(3), Node(4))) <tokens='2 * ( 3 + 4 )' pos=7 text=2*(3+4)>
o: 6 = 1 + 2 + 3 | Tree(+, Tree(+, Node(1), Node(2)), Node(3)) <tokens='1 + 2 + 3' pos=5 text=1+2+3>
o: 24 = 2 * 3 * 4 | Tree(*, Tree(*, Node(2), Node(3)), Node(4)) <tokens='2 * 3 * 4' pos=5 text=2*3*4>
o: 2.4 = 1.2 + 1.2 | Tree(+, Node(1.2), Node(1.2)) <tokens='1.2 + 1.2' pos=3 text=1.2+1.2>
o: 1 = 7 % 3 | Tree(%, Node(7), Node(3)) <tokens='7 % 3' pos=3 text=7%3>
o: 8 = 2 ^ 3 | Tree(^, Node(2), Node(3)) <tokens='2 ^ 3' pos=3 text=2^3>
o: 3 = 9 ^ 0.5 | Tree(^, Node(9), Node(0.5)) <tokens='9 ^ 0.5' pos=3 text=9^0.5>
o: 6 = one + two * two + one | Tree(+, Tree(+, Node(one), Tree(*, Node(two), Node(two))), Node(one)) <tokens='one + two * two + one' pos=7 text=one+two*two+one>
o: 6 = 1 + one + two * 2 | Tree(+, Tree(+, Node(1), Node(one)), Tree(*, Node(two), Node(2))) <tokens='1 + one + two * 2' pos=7 text=1+one+two*2>
o: 1 = IF(1=1, 1, 2) | If(Node(1) = Node(1), Node(1), Node(2)) <tokens='IF ( 1 = 1 , 1 , 2 )' pos=10 text=IF(1=1,1,2)>
o: 2 = IF(1=2, 1, 2) | If(Node(1) = Node(2), Node(1), Node(2)) <tokens='IF ( 1 = 2 , 1 , 2 )' pos=10 text=IF(1=2,1,2)>
o: 2 = IF(2>2, 1, 2) | If(Node(2) > Node(2), Node(1), Node(2)) <tokens='IF ( 2 > 2 , 1 , 2 )' pos=10 text=IF(2>2,1,2)>
o: 2 = IF(2<2, 1, 2) | If(Node(2) < Node(2), Node(1), Node(2)) <tokens='IF ( 2 < 2 , 1 , 2 )' pos=10 text=IF(2<2,1,2)>
o: 1 = IF(2>=2, 1, 2) | If(Node(2) >= Node(2), Node(1), Node(2)) <tokens='IF ( 2 >= 2 , 1 , 2 )' pos=10 text=IF(2>=2,1,2)>
o: 1 = IF(2<=2, 1, 2) | If(Node(2) <= Node(2), Node(1), Node(2)) <tokens='IF ( 2 <= 2 , 1 , 2 )' pos=10 text=IF(2<=2,1,2)>
o: 1 = IF(one=1, 1, 2) | If(Node(one) = Node(1), Node(1), Node(2)) <tokens='IF ( one = 1 , 1 , 2 )' pos=10 text=IF(one=1,1,2)>
o: 2 = IF(one=2, 1, 2) | If(Node(one) = Node(2), Node(1), Node(2)) <tokens='IF ( one = 2 , 1 , 2 )' pos=10 text=IF(one=2,1,2)>
o: 3 = IF(one=3, 1, IF(one=2, 1, 3)) | If(Node(one) = Node(3), Node(1), If(Node(one) = Node(2), Node(1), Node(3))) <tokens='IF ( one = 3 , 1 , IF ( one = 2 , 1 , 3 ) )' pos=19 text=IF(one=3,1,IF(one=2,1,3))>
o: 4 = IF(one=3, 1, IF(one=1, 4, 3)) | If(Node(one) = Node(3), Node(1), If(Node(one) = Node(1), Node(4), Node(3))) <tokens='IF ( one = 3 , 1 , IF ( one = 1 , 4 , 3 ) )' pos=19 text=IF(one=3,1,IF(one=1,4,3))>
o: KeyNotFoundException = 1 ++ | Not in scope '+' : Tree(+, Node(1), Node(+)) <tokens='1 + +' pos=3 text=1++>
o: FormatException = 1.2.2 + 1.2 | parse error token=. tokens='1.2 . 2 + 1.2' pos=1 text=1.2.2+1.2
o: 0 = 3 - 2 - 1 | Tree(-, Tree(-, Node(3), Node(2)), Node(1)) <tokens='3 - 2 - 1' pos=5 text=3-2-1>
o: 1 = 4 / 2 / 2 | Tree(/, Tree(/, Node(4), Node(2)), Node(2)) <tokens='4 / 2 / 2' pos=5 text=4/2/2>
o: 1 = IF(2<=3, 1, 2) | If(Node(2) <= Node(3), Node(1), Node(2)) <tokens='IF ( 2 <= 3 , 1 , 2 )' pos=10 text=IF(2<=3,1,2)>
電卓の実装
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
public interface INode
{
double Eval(Func<string, double> convert);
}
public class Node : INode
{
public readonly string Text;
public Node(string text)
{
Text = text;
}
public double Eval(Func<string, double> convert)
{
return convert(Text);
}
}
public class Tree : INode
{
public readonly string Operand;
public readonly INode Left;
public readonly INode Right;
public Tree(string operand, INode left, INode right)
{
Operand = operand;
Left = left;
Right = right;
}
public double Eval(Func<string, double> convert)
{
double l = Left.Eval(convert);
double r = Right.Eval(convert);
switch (Operand)
{
case "+": return l + r;
case "-": return l - r;
case "*": return l * r;
case "/": return l / r;
case "%": return l % r;
case "^": return Math.Pow(l, r);
default: throw new FormatException(Operand);
}
}
}
public class Cond
{
public readonly string Operand;
public readonly INode Left;
public readonly INode Right;
public Cond(string operand, INode left, INode right)
{
Operand = operand;
Left = left;
Right = right;
}
public bool Eval(Func<string, double> convert)
{
double l = Left.Eval(convert);
double r = Right.Eval(convert);
switch (Operand)
{
case "=": return l == r;
case ">": return l > r;
case "<": return l < r;
case "==": return l == r;
case ">=": return l >= r;
case "<=": return l <= r;
case "!=": return l != r;
case "<>": return l != r;
default: throw new FormatException(Operand);
}
}
}
public class If : INode
{
public readonly Cond Condition;
public readonly INode Left;
public readonly INode Right;
public If(Cond condition, INode left, INode right)
{
Condition = condition;
Left = left;
Right = right;
}
public double Eval(Func<string, double> convert)
{
return Condition.Eval(convert) ? Left.Eval(convert) : Right.Eval(convert);
}
}
public class Lex<T> where T : class
{
static readonly Regex tokenPattern = new Regex(@"\d+(\.\d+)?|[+-/*%^\(\)]|\w+|IF|,|(==|<=|>=|>|<|=)");
public readonly string Text;
readonly string[] tokens;
int pos;
public Lex(string text)
{
Text = text.Replace(" ", "");
tokens = tokenPattern.Matches(Text).Cast<Match>().Select(x => x.Value).ToArray();
pos = 0;
}
public void Next()
{
++pos;
}
public void Skip(string expect)
{
if (expect != Token())
{
throw new FormatException("expect=" + expect + " but token=" + Token() + " : " + Show());
}
Next();
}
public string Token()
{
if (Eof())
{
throw new IndexOutOfRangeException("EOF " + Show());
}
return tokens[pos];
}
public string TokenAndNext()
{
string token = Token();
Next();
return token;
}
public T Try(string expect, Func<T> callback)
{
if (!Eof() && Token() == expect)
{
Next();
return callback();
}
return null;
}
public T Try(string expect1, string expect2, Func<T> callback)
{
return Try(expect1, () => {
T ret = callback();
Skip(expect2);
return ret;
});
}
public bool Eof()
{
return pos >= tokens.Length;
}
public string Show()
{
return string.Format(
"tokens='{0}' pos={1} text={2}",
string.Join(" ", tokens),
pos,
Text);
}
}
public class Parser
{
public readonly INode Root;
readonly Lex<INode> lex;
public Parser(string text)
{
lex = new Lex<INode>(text);
Root = exp();
if (!lex.Eof())
{
throw new FormatException("parse error token=" + lex.Token() + " " + lex.Show());
}
}
public string Show()
{
return show(Root) + " <" + lex.Show() + ">";
}
string show(INode obj)
{
Node node = obj as Node;
if (node != null)
{
return "Node(" + node.Text + ")";
}
Tree tree = obj as Tree;
if (tree != null)
{
return string.Format(
"Tree({0}, {1}, {2})",
tree.Operand,
show(tree.Left),
show(tree.Right)
);
}
If if_ = obj as If;
if (if_ != null)
{
Cond c = if_.Condition;
return string.Format(
"If({0} {1} {2}, {3}, {4})",
show(c.Left),
c.Operand,
show(c.Right),
show(if_.Left),
show(if_.Right)
);
}
return "BUG";
}
INode exp(INode left=null)
{
left = left ?? term();
return
lex.Try("+", () => exp(new Tree("+", left, term()))) ??
lex.Try("-", () => exp(new Tree("-", left, term()))) ??
left;
}
INode term(INode left = null)
{
left = left ?? factor();
return
lex.Try("*", () => term(new Tree("*", left, factor()))) ??
lex.Try("/", () => term(new Tree("/", left, factor()))) ??
lex.Try("%", () => term(new Tree("%", left, factor()))) ??
lex.Try("^", () => term(new Tree("^", left, factor()))) ??
left;
}
INode factor()
{
return
lex.Try("IF", ")", () => cond()) ??
lex.Try("(", ")", () => exp()) ??
new Node(lex.TokenAndNext());
}
INode cond()
{
lex.Skip("(");
INode left = exp();
string operand = lex.TokenAndNext();
INode right = exp();
lex.Skip(",");
INode then_true = exp();
lex.Skip(",");
INode then_false = exp();
Cond cond = new Cond(operand, left, right);
return new If(cond, then_true, then_false);
}
}
public class Calc
{
readonly Parser parser;
readonly INode root;
Dictionary<string, double> vars;
public Calc(string text)
{
parser = new Parser(text);
root = parser.Root;
}
public string Show()
{
return parser.Show();
}
public double Eval()
{
return root.Eval(double.Parse);
}
public double Eval(Func<string, double> convert)
{
return root.Eval(convert);
}
public double Eval(Dictionary<string, double> vars_)
{
vars = vars_ ?? new Dictionary<string, double>();
return root.Eval(dictConvert);
}
double dictConvert(string name)
{
double v;
if (double.TryParse(name, out v))
{
return v;
}
else if (vars.TryGetValue(name, out v))
{
return v;
}
else
{
throw new KeyNotFoundException("Not in scope '" + name + "' : " + parser.Show());
}
}
}
感想
CSharpは??演算子(左辺がnullでないなら左辺を返し、nullなら右辺を評価して返す)が便利。
字句解析は正規表現で雑に済ませてしまった。