Last active
March 5, 2017 12:40
-
-
Save LYP951018/3f83ddf8414c088a51e1f8d6234e8b37 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Text; | |
using System.Diagnostics; | |
using System.Diagnostics.Contracts; | |
namespace Calculator | |
{ | |
enum SyntaxKind | |
{ | |
Plus, | |
Minus, | |
Star, | |
Carot, | |
BinOp, | |
OpenBracket, | |
CloseBracket, | |
Number, | |
End, | |
} | |
struct Token | |
{ | |
public Token(SyntaxKind kind, object value) | |
{ | |
Kind = kind; | |
Value = value; | |
} | |
public SyntaxKind Kind { get; } | |
public object Value { get; } | |
} | |
public class EvalException : Exception | |
{ | |
public EvalException() { } | |
} | |
enum Association | |
{ | |
Left, Right, | |
} | |
public static class Calculator | |
{ | |
public static int Eval(string expr) | |
{ | |
var tokens = Tokenize(expr).GetEnumerator(); | |
int EatNumber() | |
{ | |
//TODO: there must be a better way. | |
var token = tokens.Current; | |
int sign = 1; | |
switch (token.Kind) | |
{ | |
case SyntaxKind.Minus: | |
sign = -1; | |
goto case SyntaxKind.Plus; | |
case SyntaxKind.Plus: | |
if (!tokens.MoveNext()) | |
ThrowEval(); | |
token = tokens.Current; | |
if (token.Kind == SyntaxKind.Number) | |
{ | |
goto case SyntaxKind.Number; | |
} | |
if (token.Kind == SyntaxKind.OpenBracket) | |
{ | |
goto case SyntaxKind.OpenBracket; | |
} | |
break; | |
case SyntaxKind.Number: | |
return checked(sign * (int)token.Value); | |
case SyntaxKind.OpenBracket: | |
if (!tokens.MoveNext()) | |
ThrowEval(); | |
return checked(sign * EvalImpl(0, SyntaxKind.CloseBracket)); | |
default: | |
throw new EvalException(); | |
} | |
throw new EvalException(); | |
} | |
bool IsOP(SyntaxKind kind) | |
{ | |
return kind < SyntaxKind.BinOp; | |
} | |
int GetPred(SyntaxKind kind) | |
{ | |
Contract.Requires(IsOP(kind)); | |
switch (kind) | |
{ | |
case SyntaxKind.Plus: | |
case SyntaxKind.Minus: | |
return 1; | |
case SyntaxKind.Star: | |
return 2; | |
case SyntaxKind.Carot: | |
return 3; | |
default: | |
Debug.Assert(false); | |
break; | |
} | |
int fuckCSharp = 0; | |
return fuckCSharp; | |
} | |
int Pow(int left, int right) | |
{ | |
int result = 1; | |
for (int i = 0; i < right; ++i) | |
result = checked(result * left); | |
return result; | |
} | |
int CalculateBinOp(int left, int right, SyntaxKind op) | |
{ | |
Contract.Requires(IsOP(op)); | |
switch (op) | |
{ | |
case SyntaxKind.Plus: | |
return checked(left + right); | |
case SyntaxKind.Minus: | |
return checked(left - right); | |
case SyntaxKind.Star: | |
return checked(left * right); | |
case SyntaxKind.Carot: | |
return Pow(left, right); | |
default: | |
throw new EvalException(); | |
} | |
} | |
Association GetAssociation(SyntaxKind kind) | |
{ | |
Contract.Requires(IsOP(kind)); | |
switch (kind) | |
{ | |
case SyntaxKind.Carot: | |
return Association.Right; | |
default: | |
return Association.Left; | |
} | |
} | |
void ThrowEval() | |
{ | |
throw new EvalException(); | |
} | |
int EvalImpl(int pred, SyntaxKind endToken) | |
{ | |
var left = EatNumber(); | |
if (!tokens.MoveNext()) | |
ThrowEval(); | |
while (true) | |
{ | |
var token = tokens.Current; | |
if (token.Kind == endToken) | |
return left; | |
if (token.Kind == SyntaxKind.End | |
&& SyntaxKind.End != endToken) | |
{ | |
ThrowEval(); | |
} | |
var curPred = GetPred(token.Kind); | |
if (curPred >= pred) | |
{ | |
int nextPred = curPred; | |
if (GetAssociation(token.Kind) == Association.Left) | |
nextPred = curPred + 1; | |
if (!tokens.MoveNext()) | |
ThrowEval(); | |
var right = EvalImpl(nextPred, endToken); | |
left = CalculateBinOp(left, right, token.Kind); | |
} | |
else | |
return left; | |
} | |
} | |
if (!tokens.MoveNext()) | |
ThrowEval(); | |
return EvalImpl(0, SyntaxKind.End); | |
} | |
static IEnumerable<Token> Tokenize(string expr) | |
{ | |
int current = 0; | |
void SkipSpace() | |
{ | |
while (char.IsWhiteSpace(expr[current])) | |
{ | |
++current; | |
} | |
} | |
Token ParseNumber() | |
{ | |
var stringBuilder = new StringBuilder(20); | |
while (current < expr.Length && char.IsDigit(expr[current])) | |
{ | |
stringBuilder.Append(expr[current]); | |
++current; | |
} | |
--current; | |
return new Token(SyntaxKind.Number, int.Parse(stringBuilder.ToString())); | |
} | |
while (current < expr.Length) | |
{ | |
SkipSpace(); | |
switch (expr[current]) | |
{ | |
case '+': | |
yield return new Token(SyntaxKind.Plus, '+'); | |
break; | |
case '-': | |
yield return new Token(SyntaxKind.Minus, '-'); | |
break; | |
case '*': | |
yield return new Token(SyntaxKind.Star, '*'); | |
break; | |
//case '/' | |
case '^': | |
yield return new Token(SyntaxKind.Carot, '^'); | |
break; | |
case '(': | |
yield return new Token(SyntaxKind.OpenBracket, '('); | |
break; | |
case ')': | |
yield return new Token(SyntaxKind.CloseBracket, ')'); | |
break; | |
case '0': | |
case '1': | |
case '2': | |
case '3': | |
case '4': | |
case '5': | |
case '6': | |
case '7': | |
case '8': | |
case '9': | |
yield return ParseNumber(); | |
break; | |
default: | |
throw new EvalException(); | |
} | |
++current; | |
} | |
yield return new Token(SyntaxKind.End, null); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment