c# - 数学表达式求值器出错

Question

大家好，

我已经开始使用 Dijkstra 两个堆栈算法制作这个数学表达式求值器，我想我已经仔细应用了所有规则，但问题是它可以正确地评估一些表达式，也可以评估一些错误的表达式:/

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

问题:
1)为什么当我正确应用规则时它仍然不起作用(我知道我在某个地方犯了错误)
2)如何添加括号支持？

P.S:我必须为应用程序制作这个..

Answer 1

尝试更改此方法:

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

    }

问题是，如果您最终评估堆栈中的某个运算符，因为它的优先级高于当前操作，则必须检查堆栈的新头是否具有高于或等于当前操作的优先级以及。我已将 if 语句替换为 while 循环，以继续检查，直到不再满足条件。

我会尝试让括号正常工作，并在几分钟后回来查看:)

编辑(对于括号): 括号被视为特殊字符，仅在关闭后才进行评估。为了让它们工作，请将以下 2 个值添加到操作符列表中:

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

并更改此:

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
}

对此:

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