362 lines
13 KiB
C#
362 lines
13 KiB
C#
using System;
|
|
using System.Collections.Generic;
|
|
using System.Linq;
|
|
using System.Text;
|
|
|
|
namespace GraphingCalculator
|
|
{
|
|
public class Expression
|
|
{
|
|
#region Token type
|
|
public enum Token
|
|
{
|
|
None, Literal, Variable, Operator, Function, FunctionArgumentSeparator,
|
|
LeftParanthesis, RightParanthesis
|
|
};
|
|
#endregion
|
|
|
|
#region Variables, properties
|
|
private string expressionString;
|
|
private bool isProcessed = false;
|
|
|
|
private List<KeyValuePair<Token, string>> tokens = new List<KeyValuePair<Token, string>>();
|
|
private List<KeyValuePair<Token, string>> output = new List<KeyValuePair<Token, string>>();
|
|
private Dictionary<string, double> variables = new Dictionary<string, double>();
|
|
|
|
protected List<KeyValuePair<Token, string>> Tokens { get { return tokens; } }
|
|
protected List<KeyValuePair<Token, string>> Output { get { return output; } }
|
|
public Dictionary<string, double> Variables { get { return variables; } }
|
|
|
|
public string ExpressionString
|
|
{
|
|
get { return expressionString; }
|
|
set
|
|
{
|
|
expressionString = value;
|
|
isProcessed = false;
|
|
}
|
|
}
|
|
#endregion
|
|
|
|
#region Other stuff
|
|
public void AddVariable(string name, double value)
|
|
{
|
|
variables[name] = value;
|
|
}
|
|
|
|
#endregion
|
|
|
|
#region Constructor
|
|
public Expression()
|
|
{
|
|
Variables.Add("pi", Math.PI);
|
|
Variables.Add("e", Math.E);
|
|
}
|
|
|
|
public Expression(string expr)
|
|
: this()
|
|
{
|
|
expressionString = expr;
|
|
}
|
|
#endregion
|
|
|
|
#region Processor
|
|
private void Tokenize()
|
|
{
|
|
tokens.Clear();
|
|
|
|
for (int i = 0; i < ExpressionString.Length; i++)
|
|
{
|
|
if (char.IsWhiteSpace(ExpressionString[i])) continue;
|
|
|
|
if (IsOperator(ExpressionString[i]))
|
|
{
|
|
// Unary minus
|
|
if (ExpressionString[i] == '-' && (tokens.Count == 0 || tokens.Last().Key == Token.LeftParanthesis || tokens.Last().Key == Token.Operator || tokens.Last().Key == Token.FunctionArgumentSeparator))
|
|
tokens.Add(new KeyValuePair<Token, string>(Token.Operator, "!-"));
|
|
|
|
// Any other operator
|
|
else tokens.Add(new KeyValuePair<Token, string>(Token.Operator, ExpressionString[i].ToString()));
|
|
|
|
}
|
|
|
|
else if (ExpressionString[i] == '(')
|
|
tokens.Add(new KeyValuePair<Token, string>(Token.LeftParanthesis, ExpressionString[i].ToString()));
|
|
|
|
else if (ExpressionString[i] == ')')
|
|
tokens.Add(new KeyValuePair<Token, string>(Token.RightParanthesis, ExpressionString[i].ToString()));
|
|
|
|
else if (ExpressionString[i] == ',')
|
|
tokens.Add(new KeyValuePair<Token, string>(Token.FunctionArgumentSeparator, ExpressionString[i].ToString()));
|
|
|
|
else if (Char.IsDigit(ExpressionString[i]))
|
|
tokens.Add(new KeyValuePair<Token, string>(Token.Literal, GetLiteral(ExpressionString, ref i)));
|
|
|
|
else if (Char.IsLetter(ExpressionString[i]))
|
|
{
|
|
if (IsFunction(ExpressionString, i)) tokens.Add(new KeyValuePair<Token, string>(Token.Function, GetVariable(ExpressionString, ref i)));
|
|
else tokens.Add(new KeyValuePair<Token, string>(Token.Variable, GetVariable(ExpressionString, ref i)));
|
|
}
|
|
|
|
else throw new Exception("Unrecognized character found!");
|
|
}
|
|
}
|
|
|
|
private void ShuntingYard()
|
|
{
|
|
Stack<KeyValuePair<Token, string>> stack = new Stack<KeyValuePair<Token, string>>();
|
|
|
|
foreach (var i in Tokens) switch (i.Key)
|
|
{
|
|
case Token.Variable:
|
|
case Token.Literal: output.Add(i); break;
|
|
|
|
case Token.Function: stack.Push(i); break;
|
|
|
|
case Token.FunctionArgumentSeparator:
|
|
|
|
while (stack.Peek().Key != Token.LeftParanthesis)
|
|
{
|
|
output.Add(stack.Pop());
|
|
if (stack.Count == 0) throw new Exception("Syntax error!");
|
|
}
|
|
|
|
break;
|
|
|
|
case Token.Operator:
|
|
|
|
if (IsLeftAssociative(i.Value))
|
|
{
|
|
while (stack.Count != 0 && Precedence(i.Value) <= Precedence(stack.Peek().Value))
|
|
output.Add(stack.Pop());
|
|
}
|
|
|
|
else
|
|
{
|
|
while (stack.Count != 0 && Precedence(i.Value) < Precedence(stack.Peek().Value))
|
|
output.Add(stack.Pop());
|
|
}
|
|
|
|
stack.Push(i);
|
|
break;
|
|
|
|
case Token.LeftParanthesis: stack.Push(i); break;
|
|
|
|
case Token.RightParanthesis:
|
|
|
|
while (stack.Peek().Key != Token.LeftParanthesis)
|
|
{
|
|
output.Add(stack.Pop());
|
|
if (stack.Count == 0) throw new Exception("Mismatched parantheses!");
|
|
}
|
|
|
|
stack.Pop(); // Pop paranthesis
|
|
if (stack.Count > 0 && stack.Peek().Key == Token.Function) output.Add(stack.Pop()); // Pop function
|
|
|
|
break;
|
|
}
|
|
|
|
while (stack.Count > 0)
|
|
{
|
|
if (stack.Peek().Key == Token.LeftParanthesis) throw new Exception("Mismatched parantheses!");
|
|
output.Add(stack.Pop());
|
|
}
|
|
}
|
|
|
|
public void Process()
|
|
{
|
|
if (!isProcessed)
|
|
{
|
|
tokens.Clear();
|
|
output.Clear();
|
|
|
|
Tokenize();
|
|
ShuntingYard();
|
|
}
|
|
}
|
|
|
|
public double Evaluate()
|
|
{
|
|
Process();
|
|
if (Output.Count == 0) return 0;
|
|
|
|
Stack<double> stack = new Stack<double>();
|
|
|
|
foreach (var i in Output)
|
|
switch (i.Key)
|
|
{
|
|
case Token.Variable:
|
|
if (!Variables.ContainsKey(i.Value)) throw new Exception("Undefined variable '" + i.Value + "'.");
|
|
stack.Push(Variables[i.Value]);
|
|
break;
|
|
|
|
case Token.Literal: stack.Push(double.Parse(i.Value)); break;
|
|
|
|
case Token.Operator:
|
|
switch (i.Value)
|
|
{
|
|
case "!-": stack.Push(stack.Pop() * -1); break;
|
|
case "+": stack.Push(stack.Pop() + stack.Pop()); break;
|
|
case "-":
|
|
{
|
|
double b = stack.Pop();
|
|
double a = stack.Pop();
|
|
stack.Push(a - b);
|
|
} break;
|
|
|
|
case "*": stack.Push(stack.Pop() * stack.Pop()); break;
|
|
case "/":
|
|
{
|
|
double b = stack.Pop();
|
|
double a = stack.Pop();
|
|
stack.Push(a / b);
|
|
} break;
|
|
|
|
case "%":
|
|
{
|
|
double b = stack.Pop();
|
|
double a = stack.Pop();
|
|
stack.Push(a % b);
|
|
} break;
|
|
|
|
case "^":
|
|
{
|
|
double b = stack.Pop();
|
|
double a = stack.Pop();
|
|
stack.Push(Math.Pow(a, b));
|
|
} break;
|
|
}
|
|
|
|
break;
|
|
|
|
case Token.Function:
|
|
EvaluateFunction(i.Value, ref stack);
|
|
break;
|
|
}
|
|
|
|
return stack.Pop();
|
|
}
|
|
#endregion
|
|
|
|
#region Helper routines
|
|
|
|
private void EvaluateFunction(string func, ref Stack<double> stack)
|
|
{
|
|
switch (func)
|
|
{
|
|
case "sin": stack.Push(Math.Sin(stack.Pop())); break;
|
|
case "sinh": stack.Push(Math.Sinh(stack.Pop())); break;
|
|
case "cos": stack.Push(Math.Cos(stack.Pop())); break;
|
|
case "cosh": stack.Push(Math.Cosh(stack.Pop())); break;
|
|
case "tan": stack.Push(Math.Tan(stack.Pop())); break;
|
|
case "tanh": stack.Push(Math.Tanh(stack.Pop())); break;
|
|
case "ctan": stack.Push(1 / Math.Tan(stack.Pop())); break;
|
|
|
|
case "arcsin": stack.Push(Math.Asin(stack.Pop())); break;
|
|
case "asin": stack.Push(Math.Asin(stack.Pop())); break;
|
|
case "arccos": stack.Push(Math.Acos(stack.Pop())); break;
|
|
case "acos": stack.Push(Math.Acos(stack.Pop())); break;
|
|
case "arctan": stack.Push(Math.Atan(stack.Pop())); break;
|
|
case "atan": stack.Push(Math.Atan(stack.Pop())); break;
|
|
|
|
case "truncate":
|
|
case "int": stack.Push(Math.Truncate(stack.Pop())); break;
|
|
case "floor": stack.Push(Math.Floor(stack.Pop())); break;
|
|
case "ceil":
|
|
case "ceiling": stack.Push(Math.Ceiling(stack.Pop())); break;
|
|
|
|
case "sqrt": stack.Push(Math.Sqrt(stack.Pop())); break;
|
|
case "cbrt": stack.Push(Math.Pow(stack.Pop(), 1.0 / 3.0)); break;
|
|
case "root": stack.Push(Math.Pow(stack.Pop(), 1 / stack.Pop())); break;
|
|
|
|
case "abs": stack.Push(Math.Abs(stack.Pop())); break;
|
|
case "max": stack.Push(Math.Max(stack.Pop(), stack.Pop())); break;
|
|
case "min": stack.Push(Math.Min(stack.Pop(), stack.Pop())); break;
|
|
case "round": {
|
|
double dec = stack.Pop(), val = stack.Pop();
|
|
dec = Math.Max(0, dec);
|
|
dec = Math.Min(15, dec);
|
|
|
|
stack.Push(Math.Round(val, Convert.ToInt32(dec)));
|
|
break;
|
|
}
|
|
|
|
case "lg": stack.Push(Math.Log10(stack.Pop())); break;
|
|
case "log": stack.Push(Math.Log(stack.Pop(), stack.Pop())); break;
|
|
case "ln": stack.Push(Math.Log(stack.Pop(), Math.E)); break;
|
|
|
|
default: throw new Exception("Undefined function '" + func + "'.");
|
|
}
|
|
}
|
|
|
|
private static bool IsLeftAssociative(string op)
|
|
{
|
|
return (op != "^");
|
|
}
|
|
|
|
private static int Precedence(string op)
|
|
{
|
|
switch (op)
|
|
{
|
|
case "+":
|
|
case "-": return 1;
|
|
|
|
case "*":
|
|
case "/":
|
|
case "%": return 2;
|
|
|
|
case "^": return 3;
|
|
|
|
case "!-": return 10;
|
|
|
|
default: return 0;
|
|
}
|
|
}
|
|
|
|
private static bool IsOperator(char c)
|
|
{
|
|
const string operators = "+-*/%^";
|
|
return operators.Contains(c);
|
|
}
|
|
|
|
private static bool IsFunction(string s, int index)
|
|
{
|
|
// Skip function/variable name
|
|
while (index < s.Length && char.IsLetterOrDigit(s[index])) index++;
|
|
while (index < s.Length && char.IsWhiteSpace(s[index])) index++;
|
|
|
|
// End of string? Than it's a variable
|
|
if (index >= s.Length) return false;
|
|
|
|
// If an operator, function separator, or ), variable
|
|
if (s[index] == '(') return true;
|
|
return false;
|
|
}
|
|
|
|
private static string GetVariable(string s, ref int index)
|
|
{
|
|
StringBuilder str = new StringBuilder();
|
|
|
|
while (index < s.Length && (char.IsLetterOrDigit(s[index])))
|
|
str.Append(s[index++]);
|
|
|
|
index -= 1;
|
|
return str.ToString();
|
|
}
|
|
|
|
private static string GetLiteral(string s, ref int index)
|
|
{
|
|
StringBuilder str = new StringBuilder();
|
|
|
|
while (index < s.Length && (char.IsDigit(s[index]) || s[index] == '.'))
|
|
str.Append(s[index++]);
|
|
|
|
index -= 1;
|
|
return str.ToString();
|
|
}
|
|
|
|
#endregion
|
|
|
|
}
|
|
}
|