Odwrotna notacja polska - gotowiec
Deti
1 Wstęp
2 Podział na klasy
2.1 Klasa Token
2.2 Klasa NumberBase
2.3 Klasa FunctionBase
2.4 Klasa OperatorBase
2.5 Klasy LeftBracket i RightBracket
3 Wszystko razem - klasa TokenFactory
4 Interpreter
5 Przykład użycia
6 Funkcjonalność
7 Podsumowanie
Wstęp
W gotowcu znajdziecie moją implementację obliczania wyrażeń matematycznych w języku C# - czyli zamianę skomplikowanych wyrażeń, np. (2+5*10)/3^2 do wartości, jaka temu odpowiada. Gotowiec działa na podstawie odwrotnej notacji polskiej (ONP). Więcej tutaj: http://pl.wikipedia.org/wiki/Odwrotna_notacja_polska
Podział na klasy
Aby zapewnić dużą rozszerzalność kodu, wzmianki wymaga podział na klasy. Poniżej deklaracje oraz krótki opis najważniejszych z nich:
Klasa Token
Klasa Token reprezentuje każdą atomiczną część wyrażenia matematycznego (może to być dowolna liczba, funkcja, operator, lewy nawias, prawy nawias itd). Jest to klasa abstrakcyjna. Pole Entry zawiera reprezentację tekstową tokenu (np. "sin" dla funkcji sinus).
public abstract class Token {
public readonly string Entry;
public Token(string entry) {
Entry=entry;
}
}
Klasa NumberBase
NumberBase dziedziczy bezpośrednio po Token i oznacza dowolną liczbę. Wartość jest przechowywana w polu Value (typ double - można stosować liczby zmiennoprzecinkowe).
abstract class NumberBase: Token {
public abstract double Value {
get;
}
public NumberBase(string value)
:base(value){
}
}
Abstrakcyjna klasa NumberBase może mieć wiele implementacji : np. w postaci klasy Number (oznaczającą liczbę zapisaną w postaci cyfr...)
class Number: NumberBase {
public override double Value {
get {
return double.Parse(Entry);
}
}
public Number(double value)
:this(value.ToString()) {
}
public Number(string value)
:base(value){
}
}
Lub też liczba zapisana w postaci liter, jak liczba "Pi":
class Pi: NumberBase {
public override double Value {
get {
return Math.PI;
}
}
public Pi(string value)
:base(value){
}
}
W ten sposób możemy rozszerzyć program o dowolne elementy.
Klasa FunctionBase
Kolejna klasa, która dziedziczy po Token - jest to odpowiednik dowolnej funkcji (jak np. sinus, cosinus, abs, sqrt, Exp itd).
abstract class FunctionBase: Token{
public virtual int OperandsCount {
get {
return 1;
}
}
public FunctionBase(string value)
: base(value) {
}
public abstract double Calculate(params double[] args);
}
Istotną metodą jest tu metoda Calculate, która po prostu zwraca wynik działania funkcji odpowiednio do podanych argumentów. Umówmy się, że zignorujecie pole OperandsCount (która miała określać ile argumentów przyjmuje funkcja, ale nie dokończyłem tego .. dlatego też każda funkcja będzie przyjmowała jeden argument - np. sin(3.14), abs(-3), sqrt(9), itd... - świetne zadanie do samodzielnej analizy :)
A tak wyglądają przykładowe implementacje klasy FunctionBase:
class Sinus: FunctionBase {
public Sinus(string value)
: base(value) {
}
public override double Calculate(params double[] args) {
return Math.Sin(args[0]);
}
}
class Sqrt: FunctionBase {
public Sqrt(string value)
: base(value) {
}
public override double Calculate(params double[] args) {
return Math.Sqrt(args[0]);
}
}
Klasa OperatorBase
Klasa ta jest abstrakcją dla dowolnego operatora, to jest: +,-,*,/,^ itd.
abstract class OperatorBase: Token{
public virtual int Precedence {
get {
return 1;
}
}
public virtual Associativity Associativity {
get {
return Associativity.Left;
}
}
public OperatorBase(string value)
:base(value) {
}
public abstract double Calculate(double left,double right);
}
Metoda Calculate oblicza wartość wyrażenia "left OPERATOR right". Pole Precedence oznacza "ważność" operatora, który domyślnie ma wartość 1. O tym za chwilę.
Pole Associativity jest typu Enum, który może przyjmować jedną z dwóch wartości:
enum Associativity {
Left, Right
}
.. i oznacza czy działania ma łączność lewostronną czy prawostronną. O tym również za chwilę.
Poniżej kilka implementacji klasy OperatorBase:
class Addition:OperatorBase {
public Addition(string value):base(value){
}
public override double Calculate(double left,double right) {
return left+right;
}
}
class Subtraction:OperatorBase {
public Subtraction(string value): base(value) {
}
public override double Calculate(double left,double right) {
return left-right;
}
}
class Multiplication:OperatorBase {
public override int Precedence {
get {
return 2;
}
}
public Multiplication(string value): base(value) {
}
public override double Calculate(double left,double right) {
return left*right;
}
}
class Power:OperatorBase {
public override int Precedence {
get {
return 3;
}
}
public override Associativity Associativity {
get {
return Associativity.Right;
}
}
public Power(string value): base(value) {
}
public override double Calculate(double left,double right) {
return Math.Pow(left,right);
}
}
Po krótkim przeanalizowaniu powinno się wyjaśnić jak działa pole Precedence. Dodawanie i odejmowanie nie nadpisuje wartości (czyli ma wartość równą 1). Mnożenie jest wykonywane przed dodawaniem, więc ma większą wartość (równą 2). Jednak potęgowanie powinno być obliczone jeszcze wcześniej, więc jego ważność przyjęta jako 3.
Przykład: 2+3*2^8.
Najpierw wykona się potęgowanie 28, następnie wynik zostanie pomnożony przez 3, a na końcu dopiero do wszystkiego zostanie dodane 2 (niezależnie od kolejności zapisu, chyba że byłyby nawiasy). Associativity "Right" w przypadku Power oznacza, że potęgowanie jest wykonywane zawsze od prawej do lewej (np. 22^3).
Klasy LeftBracket i RightBracket
Dla porządku:
class LeftBracket: Token {
public LeftBracket(string value): base(value) {
}
}
class RightBracket: Token {
public RightBracket(string value): base(value) {
}
}
Wszystko razem - klasa TokenFactory
Skoro już długi i męczący (jednak konieczny!) wstęp mamy za sobą - czas do konkretów. Klasa TokenFactory zwraca konkretny Token na podstawie danego tekstu.
class TokenFactory {
Dictionary<Func<string,bool>,Type> RegisteredTokens;
public TokenFactory() {
RegisteredTokens=new Dictionary<Func<string,bool>,Type>();
string separator=CultureInfo.CurrentCulture.NumberFormat.NumberDecimalSeparator;
string reqexSeparator=Regex.Escape(separator);
//basic operators
RegisterToken<Addition>(x => x=="+");
RegisterToken<Subtraction>(x => x=="-");
RegisterToken<Multiplication>(x => x=="*");
RegisterToken<Division>(x => x=="/" || x==@"\");
RegisterToken<Modulus>(x => x=="%");
RegisterToken<Power>(x => x=="^");
//Numbers
RegisterToken<Pi>(x => Match(x, "pi","π"));
RegisterToken<E>(x => x=="e");
RegisterToken<Number>(x => {
string[] patterns=new string[] {
string.Format(@"^(\d+({0}\d*)?)$",reqexSeparator), //dec/float
@"^0[xX][0-9a-fA-F]+$" // hex
};
return patterns.Any(p=> Regex.Match(x,p).Success);
});
//brackets
RegisterToken<LeftBracket>(x => x=="(" || x=="[" || x=="{");
RegisterToken<RightBracket>(x => x==")" || x=="]" || x=="}");
//functions
RegisterToken<Sinus>(x => Match(x,"sin"));
RegisterToken<Cosinus>(x => Match(x,"cos"));
RegisterToken<Tangent>(x => Match(x,"tan","tg"));
RegisterToken<ABS>(x => Match(x,"abs"));
RegisterToken<Sqrt>(x => Match(x,"sqrt"));
RegisterToken<ArcTangent>(x => Match(x,"atan","atg"));
RegisterToken<ArcSinus>(x => Match(x,"asin"));
RegisterToken<ArcCosinus>(x => Match(x,"acos"));
RegisterToken<Ceil>(x => Match(x,"ceil"));
RegisterToken<Floor>(x => Match(x,"floor"));
RegisterToken<Round>(x => Match(x,"round","rnd"));
RegisterToken<Exp>(x => Match(x,"Exp"));
RegisterToken<Logarithm>(x => Match(x,"log","ln"));
RegisterToken<Logarithm10>(x => Match(x,"log10"));
}
public Token GetToken(string exact) {
Token toret=null;
foreach(var kvp in RegisteredTokens) {
if(kvp.Key(exact)) {
toret=(Token)Activator.CreateInstance(kvp.Value,exact);
break;
}
}
return toret;
}
bool Match(string cand,params string[] names) {
foreach(string name in names) {
if(name.Equals(cand,StringComparison.InvariantCultureIgnoreCase))
return true;
}
return false;
}
void RegisterToken<T>(Func<string,bool> match) where T:Token {
if(RegisteredTokens.ContainsKey(match))
throw new NotSupportedException("Token for predicate already added");
RegisteredTokens[match]=typeof(T);
}
}
Kilka słów komentarza: powyżej zostały zaimplementowane funkcje, których nie ma w opisie wyżej. Możecie albo je usunąć, lub też ściągnąć pełną wersje mojej biblioteki - o tym później.
Interpreter
.. czyli klasa, która składa wszystko do przysłowiowej "kupy" i wykonuje magiczne liczenie (czysty ONP).
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Globalization;
namespace HAKGERSoft {
public class Interpreter {
const string InvalidMessage="Invalid input";
public double Calculate(string input) {
if(input==null)
throw new ArgumentNullException("input");
if(input==string.Empty)
throw new ArgumentException(InvalidMessage);
string expression=FormatExpression(input);
TokenFactory tf=new TokenFactory();
Queue<Token> postfix=GetPostFix(expression,tf);
return ProcessPostfix(postfix);
}
Queue<Token> GetPostFix(string input,TokenFactory tokenFactory) {
Queue<Token> output=new Queue<Token>();
Stack<Token> stack=new Stack<Token>();
int position=0;
while(position<input.Length) {
Token token=GetNextToken(ref position,input,tokenFactory);
if(token==null)
break;
if(token is NumberBase)
output.Enqueue(token);
else if(token is FunctionBase)
stack.Push(token);
else if(token is LeftBracket)
stack.Push(token);
else if(token is RightBracket) {
while(true) {
Token taken=stack.Pop();
if(!(taken is LeftBracket))
output.Enqueue(taken);
else {
break;
}
}
} else if(token is OperatorBase) {
if(stack.Count>0) {
Token top=stack.Peek();
bool nested=true;
while(nested) {
if(top==null || !(top is OperatorBase))
break;
OperatorBase o1=(OperatorBase)token;
OperatorBase o2=(OperatorBase)top;
if(o1.Associativity==Associativity.Left && (o2.Precedence>=o1.Precedence))
output.Enqueue(stack.Pop());
else if(o2.Associativity==Associativity.Right && (o2.Precedence>o1.Precedence))
output.Enqueue(stack.Pop());
else
nested=false;
top=(stack.Count>0)?stack.Peek():null;
}
}
stack.Push(token);
}
}
while(stack.Count>0) {
Token next=stack.Pop();
if(next is LeftBracket || next is RightBracket) {
throw new ArgumentException(InvalidMessage);
}
output.Enqueue(next);
}
return output;
}
double ProcessPostfix(Queue<Token> postfix){
Stack<Token> stack=new Stack<Token>();
Token token=null;
while(postfix.Count>0) {
token=postfix.Dequeue();
if(token is NumberBase)
stack.Push(token);
else if(token is OperatorBase){
NumberBase right=(NumberBase)stack.Pop();
NumberBase left=(NumberBase)stack.Pop();
double value=((OperatorBase)token).Calculate(left.Value,right.Value);
stack.Push(new Number(value));
}
else if(token is FunctionBase){
NumberBase arg=(NumberBase)stack.Pop();
double value=((FunctionBase)token).Calculate(arg.Value);
stack.Push(new Number(value));
}
}
double toret=((NumberBase)stack.Pop()).Value;
if(stack.Count!=0)
throw new ArgumentException(InvalidMessage);
return toret;
}
Token GetNextToken(ref int position,string input, TokenFactory tokenFactory) {
Token toret=null;
Type found=null;
string rest=input.Substring(position);
int count=0;
int pos=0;
while(count++<rest.Length) {
string cand=rest.Substring(0,count);
Token latest=tokenFactory.GetToken(cand);
if(latest!=null) {
//if(found!=null && latest.GetType()!=found)
//break;
found=latest.GetType();
toret=latest;
pos=count;
}
else {
//break;
}
}
if(toret!=null)
position+=pos;
return toret;
}
string FormatExpression(string input) {
string toret=input;
toret=toret.Replace(" ",string.Empty);
string separator=CultureInfo.CurrentCulture.NumberFormat.NumberDecimalSeparator;
toret=toret.Replace(".",separator);
toret=toret.Replace(",",separator);
toret=Regex.Replace(toret,@"^\-",@"0-");
toret=Regex.Replace(toret,@"\(\-",@"(0-");
return toret;
}
}
}
Przykład użycia
Nic prostszego - budujemy instancję klasy Interpreter i wykonujemy metodę Calculate:
Interpreter Inp=new Interpreter();
string result=Inp.Calculate(@"(1+ sin(pi/2) + ln(e^3) - sqrt(9) * log10(10) +0xE) / (20.34323354+floor(2.6))");
// result== 0.002
Funkcjonalność
- oblicza dowolnej długości wyrażenia (pod warunkiem, że są prawidłowe)
- jeśli wyrażenie jest nieprawidłowe - wystąpi wyjątek
- biblioteka bardzo łatwo rozszerzalna - wystarczy dodać klasę dziedziczącą po Token oraz wykonać RegisterToken()
- niewrażliwość na spacje
- dowolny typ nawiasów
- obliczanie wartości zmiennoprzecinkowych, funkcji, stałych matematycznych, wartości hexalnych
Podsumowanie
To co widzicie powyżej to jedynie fragment z większego projektu o nazwie HInterpreter. Moduł jest w pełni darmowy.
Download: HInterpreter.rar
Wszelkie konstruktywne komentarze mile widziane.
ufff poprawiłem i tera juz działa
dziekuje za brak odpowiedzi , :)
sorrki , ale nie bardzo działa np string "sin(0)+1", i podobnie funkcja +liczba nie daje dobrego wyniku
sin(0)+1 powinno być 1 a wychodzi 0,841
Racja, już poprawione (łącznie z całym gotowcem)
Złego przykładu użyłeś :)
sin(pi) jest równe zero, a co za tym idzie dzielisz przez zero. Wynik nie może być -179,736.