Алгоритм маневрового двора с тригонометрическими функциями
Я работаю над реализацией алгоритма маневрового двора в C#. Хотя он хорошо разбирает математические выражения с символами ( +, * - / и ^). Но по некоторым причинам он не работает для функций синус-косинуса. Как например, если я пытаюсь вычислить грех (45), я получаю 0,707106 . Но когда я пытаюсь разобрать выражение как
sin(25)+cos(15+sin(25))+3 it gives me 0.43756 (Correct answer is: 2.19106879911)
sin(45)+cos(45) it gives me 0.715779 (Correct answer is: 1.414)
Я следовал за всеми шагами, которые упомянуты в этой статье в Википедии. Я пробовал это в течение нескольких дней, но я не могу заставить его работать идеально. Вот основная функция разбора
private void parse()
{
//scan the input string
for (int j = 0; j < input.Length; j++)
{
if (Char.IsDigit(input[j])) //if its a number
{
string number = extractNumber(input, j); //extracts multiple digit number
j = currentposition; //increment the counter according to length of the digit
postfix += number + " ";
Console.WriteLine(postfix);
}
//if its a function character
else if(Char.IsLetter(input[j]) )
{
//its a letter
string function = getFunction(j); //get the function name
operators.Push( function );
j = currentposition;
}
else if(input[j] == ',') //if its a comma
{
while(operators.Peek() != "(")
{
postfix += input[j] + " ";
}
}
else if (IsAnOperator(input[j])) // if we have got an operator
{
if (operators.Count != 0 && IsHigherPrecedence(operators.Peek().ToCharArray()[0], input[j]))
{
while ( ( operators.Count != 0 && IsHigherPrecedence(operators.Peek().ToCharArray()[0], input[j]) ) )
{
postfix += operators.Pop() + " ";
}
}
operators.Push(Char.ToString(input[j]));
}
else if (input[j] == '(')
operators.Push(Char.ToString(input[j]));
else if (input[j] == ')')
{
while (operators.Count != 0 && operators.Peek() != "(")
postfix += operators.Pop() + " ";
operators.Pop();
}
} // end for loop
while(operators.Count > 0 )
postfix +=operators.Pop() + " ";
//Conversion Logic (postfix to final answer )
postfixtokens.AddRange( postfix.Split(' ') ) ;
for (int j = 0; j < postfixtokens.Count-1; j++)
{
if (IsAnOperator(postfixtokens[j][0]) && basket.Count > 1)
{
Double second = Double.Parse( basket.Pop() );
Double first = Double.Parse(basket.Pop() );
char op = postfixtokens[j][0];
Double result = ApplyOperation(op,second, first);
// Console.WriteLine("{0} {1} {2} = {3}", first, op, second, result);
basket.Push( result.ToString());
}
else if (IsAnOperator(postfixtokens[j][0]) && basket.Count == 1)
{
Double second = Double.Parse(basket.Pop());
Double first = 0.0;
char op = postfixtokens[j][0];
Double result = ApplyOperation(op, second, first);
// Console.WriteLine("{0} {1} {2} = {3}", first, op, second, result);
basket.Push(result.ToString() );
}
else if (Char.IsDigit(postfixtokens[j][0]))
{
basket.Push( postfixtokens[j] );
}
else if( isAFunction(postfixtokens[j]) )
{
//if its a single argument function
if (AllowedFunctions[postfixtokens[j]] == 1)
{
//single arg logic
if (postfixtokens[j] == "sin")
{
Double result = Math.Sin( Double.Parse(basket.Pop() )*Math.PI/180.0 );
//result = Math.PI / 180;
basket.Push(result.ToString());
}
else if (postfixtokens[j] == "cos")
{
Double result = Math.Cos( Double.Parse(basket.Pop() )*Math.PI/180.0 );
//result = Math.PI / 180;
basket.Push(result.ToString());
}
}
}
}
}
Кроме того, вот вывод программы:
Input: 3+4*2/(1-5)^5^10
PostFix: 3 4 2 * 1 5 - 5 10 ^ ^ / +
Answer: 3
Input: 2+4
PostFix: 2 4 +
Answer: 6
Input Expression: -5-4
Input: -5-4
PostFix: 5 - 4 -
Answer: -9
Input: -4+3
PostFix: 4 - 3 +
Answer: -1
Input Expression: 4^(4^4)
Input: 4^(4^4)
PostFix: 4 4 4 ^ ^
Answer: 1.34078079299426E+154
Input: sin45
PostFix: 45 sin
Answer: 0.707106781186547 (correct)
// неисправные
Input: sin(25)+cos(15+sin(25))+3
PostFix: 25 15 25 sin + 3 + cos + sin
Answer: 0.437567038002202
Input: sin(45)+cos(45)
PostFix: 45 45 cos + sin
Answer: 0.71577935734684
Новые случаи:
Input: sin45+cos45
PostFix: 45 45 cos + sin
Answer: 0.71577935734684
Input: 2+sin30
PostFix: 2 30 sin +
Answer:2.5
Input: sin30+2
PostFix: 30 2 + sin
Answer: 0.529919264233205
Это все. Кто-нибудь может указать мне, что я делаю неправильно.
Редактировать:
Вот функция IsHigherPrecedance и перечисление precedance:
public enum Precedance { Plus =1,Minus=1,Multiply=2,Divide=2,Exponent=3,Unary = 4,Parenthesis=5 };
private bool IsHigherPrecedence(char a, char b)
{
Precedance f = getPrecedance(a);
Precedance s = getPrecedance(b);
if (f >= s)
return false;
else
return true;
}
public Precedance getPrecedance(char a)
{
if (a == '+')
return Precedance.Plus;
else if (a == '-')
return Precedance.Minus;
else if (a == '*')
return Precedance.Multiply;
else if (a == '/')
return Precedance.Divide;
else if (a == '^')
return Precedance.Exponent;
else if (Char.IsLetter(a))
return Precedance.Unary;
else if (a == '(' || a == ')')
return Precedance.Parenthesis;
else
return Precedance.Plus;
}
Теперь, когда эти тригонометрические функции являются функцией с одним аргументом, они будут проанализированы с какой-либо другой логикой, или этот маневровый алгоритм работает также и с такими функциями?
С уважением.
2 ответа
Здесь есть куча проблем, но основная из них заключается в том, что вы рассматриваете функции как операторы, хотя они и не являются (присуще то, что вы называете свой стек "операторами", как будто это единственное, что может быть на нем, не правда). В частности, эта ветка:
else if (IsAnOperator(input[j])) // if we have got an operator
{
if (operators.Count != 0 && IsHigherPrecedence(operators.Peek().ToCharArray()[0], input[j]))
{
while ( ( operators.Count != 0 && IsHigherPrecedence(operators.Peek().ToCharArray()[0], input[j]) ) )
{
postfix += operators.Pop() + " ";
}
}
operators.Push(Char.ToString(input[j]));
}
Необходимо проверить, является ли то, что находится в стеке "операторы", действительно оператором:
else if (IsAnOperator(input[j])) // if we have got an operator
{
while (operators.Count != 0
&& IsAnOperator(operators.Peek().ToCharArray()[0])
&& IsHigherPrecedence(operators.Peek().ToCharArray()[0], input[j]))
{
postfix += operators.Pop() + " ";
}
operators.Push(Char.ToString(input[j]));
}
Другие проблемы включают ветку, которая обрабатывает запятые:
else if (input[j] == ',') //if its a comma
{
while (operators.Peek() != "(")
{
// this isnt right, but its not the problem
postfix += input[j] + " ";
// should be this:
postfix += operators.Pop() + " ";
}
}
Если вы используете эту библиотеку: https://github.com/leblancmeneses/NPEG вы можете использовать эту грамматику для анализа вашего выражения.
Digit: (?<Digit>[0-9]+('.'[0-9]+)?);
(?<Trig>): 'sin(' Expr ')' / 'cos(' Expr ')';
Value: Digit / Trig / '(' Expr ')';
(?<Product>): Value ((?<Symbol>'*' / '/') Value)*;
(?<Sum>): Product ((?<Symbol>'+' / '-') Product)*;
(?<Expr>): Sum ;
Проверьте это здесь: http://www.robusthaven.com/blog/parsing-expression-grammar/npeg-language-workbench
cos(25)+cos(15+sin(25.333))+3
((((12/3)+5-2*(81/9))+1))
NuGet:
Инсталляционный пакет NPEG
чтобы увидеть пример оценки AST для булевой алгебры.