Math Expression Evaluator Gone Wrong

Question

Hi guys,

I have started making this Math Expression Evaluator by using Dijkstra two Stack Algorithm , I think I have applied all the rules carefully but the problem is that it can evaluate some expression correctly and some wrong :/

//I made it in a Console project
 static void Main(string[] args)
        {
        string expression = "2*3+232+34*45/3-4*45+3";
        //remove all whitespaces
        expression = expression.Trim();

        //two stacks needed
        var values = new Stack<double>();
        var operators = new Stack<char>();
    Dictionary<char, OperatorInfo> operatorList = new Dictionary<char, OperatorInfo> 
    {
        {'+',new OperatorInfo('+',"Add",2,OperatorFixity.Left)},
        {'-',new OperatorInfo('-',"Minus",2,OperatorFixity.Left)},
        {'/',new OperatorInfo('/',"Divide",3,OperatorFixity.Left)},
        {'*',new OperatorInfo('*',"Multiply",3,OperatorFixity.Left)},
        {'^',new OperatorInfo('^',"Caret",4,OperatorFixity.Right)}
    };

    for (int i = 0; i < expression.Length; i++)
    {
        if (expression[i].Equals('('))
            continue;//ignore it 
        else if (IsNumber(expression[i].ToString()))//if its a number
        {
            //extract number
            string[] getNumberNCount =
                getNumberAndCount(expression.Substring(i)).Split(',');
            double val = double.Parse(getNumberNCount[0]);
            int count = int.Parse(getNumberNCount[1]);
            values.Push(val);
            i += count;
        }
        else if (IsOperator(expression[i]))
        {
            //Maintain precedence on stack
            if (operators.Count > 0)
            {
               CheckPrecedence(expression[i], ref values, ref operators, operatorList);
            }
            else
                operators.Push(expression[i]);//runs first time only
        }
    }

    //now most precedence is solved
    while (operators.Count != 0)
    {
        var LastOperand = values.Pop();
        var PrevOperand = values.Pop();
        var lastOperator = operators.Pop();
        values.Push(calculateExpression(lastOperator, LastOperand, PrevOperand));
    }
    Console.WriteLine("Input Expression is: " + expression);
    Console.WriteLine("Result is: " + values.Pop());
    Console.ReadLine();
}

//it checks for precedence of operators before push
//that's the basic logic for calculation
  private static void CheckPrecedence(char currentOp, ref Stack<double> values, ref Stack<char> operators, Dictionary<char, OperatorInfo> operatorList)
        {
            char lastStackOp = operators.Peek();
            //if same precedence of both Op are same
            //OR lastOp > than CurrentOp
            if ((operatorList[lastStackOp].Precedence == operatorList[currentOp].Precedence) ||
                    (operatorList[lastStackOp].Precedence > operatorList[currentOp].Precedence))
            {
                var TopMostOperand = values.Pop();
                var PrevOperand = values.Pop();
                var TopMostOperator = operators.Pop();
                values.Push(calculateExpression(TopMostOperator, TopMostOperand, PrevOperand));
                operators.Push(currentOp);
            }
            else
            {
                operators.Push(currentOp);
            }
        }

//extracts out number from string
        public static string getNumberAndCount(string numberStr)
        {
            var number = "";
            int count = 0;
            if (numberStr.Length >= 1)
            {
                while (IsNumber(numberStr[count].ToString()))
                {
                    number += numberStr[count];
                    if (numberStr.Length == 1)
                        break;
                    count++;
                }
            }
            return number + "," + (count == 0 ? count : count - 1);
        }

Problem:
1) Why its still not working when I have applied the rules correctly (I know I have made a blunder somewhere)
2) What to do for adding parenthesis support?

P.S: I had to make this for an application..

Answer 1

Try changing this method:

private static void CheckPrecedence(char currentOp, ref Stack<double> values, ref Stack<char> operators,
                                        Dictionary<char, int> operatorList)
    {
        char lastStackOp = operators.Peek();
        //if same precedence of both Op are same
        //OR lastOp > than CurrentOp
        while (((operatorList[lastStackOp] == operatorList[currentOp]) ||
            (operatorList[lastStackOp] > operatorList[currentOp])))
        {
            var TopMostOperand = values.Pop();
            var PrevOperand = values.Pop();
            var TopMostOperator = operators.Pop();
            values.Push(calculateExpression(TopMostOperator, TopMostOperand, PrevOperand));

            if (operators.Count == 0)
                break;

            lastStackOp = operators.Peek();
        }
        operators.Push(currentOp);

    }

The issue is that if you end up evaluating an operator in the stack due to it having a higher precedence than the current operation, you have to check if the new head of the stack has a higher or equal precedence to the current operation as well. I've replaced the if statement with the while loop to carry on checking until the condition is no longer met.

I'll try get the brackets working and will check back in a few minutes :)

EDIT (For brackets): Brackets are treated as special characters which are only evaluated once closed. To get them working add the following 2 values to the operatorlist:

    {'*',new OperatorInfo('(',"OpenBracket",5,OperatorFixity.Left)},
    {'^',new OperatorInfo(')',"CloseBracket",5,OperatorFixity.Left)}

And change this:

else if (IsOperator(expression[i]))
{
    //Maintain precedence on stack
    if (operators.Count > 0)
    {
       CheckPrecedence(expression[i], ref values, ref operators, operatorList);
    }
    else
        operators.Push(expression[i]);//runs first time only
}

to this:

else if (IsOperator(expression[i]))
{
    //Maintain precedence on stack
    if (operators.Count > 0 && expression[i] != '(' && expression[i] != ')')
    {
        CheckPrecedence(expression[i], ref values, ref operators, operatorList);
    }
    else if (expression[i] == ')')
    {
        while (operators.Peek() != '(')
        {
            var lastOperator = operators.Pop();
            var LastOperand = values.Pop();
            var PrevOperand = values.Pop();
            values.Push(calculateExpression(lastOperator, LastOperand, PrevOperand));
        }
        operators.Pop();
    }
    else
        operators.Push(expression[i]);
    }