shunting yard algorithm with trigonometric functions

Question

I am working on implementing shunting yard algorithm in C#. Although it parses mathematical expressions with symbols( + , * - / and ^) pretty well.But for some reason it is not working for sine cosine functions . Like for example if I try to calculate sin(45) I get 0.707106 . But when I try to parse expression like

---

   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)

I have followed all the steps that are mentioned in this article at Wikipedia . I have trying this for a few days now but I am unable to make it work perfectly. Here is the main parsing function

    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());
                }

            }

        }
    }
}

Moreover, Here is the output of the program:

   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)

//the faulty ones

   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

New Cases:

    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

Thats all.Can anybody point me what I am doing wrong.

Edit:

Here is the IsHigherPrecedance function and precedance enum :

    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;
}

Now that these trigonometric function are single argument function, are they going to be parsed with some other logic or does this shunting yard algo works with such functions as well as well?

Regards.

Answer 1

There are a copule of problems here, but the primary one is that you are treating functions as operators, though they are not (intrinsic to this is that you call your stack "operators" as though that is the only thing that can be on it, not true). In particular, this branch:

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]));
}

needs to check to see if what's on the "operators" stack is actually an operator:

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]));
}

---

Other issues include the branch that handles commas:

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() + " ";
    }

}

Answer 2

If you use this library: https://github.com/leblancmeneses/NPEG you could use this grammar to parse your expression.

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 ;

Test it out here: 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:

Install-Package NPEG

to see a sample evaluation of the AST for boolean algebra.