2

嗨，大家好，

我已经开始使用 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）如何添加括号支持？

PS：我必须为应用程序制作这个..

4

1 回答 1

3

尝试更改此方法：

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

    }

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

我会尝试让括号工作，并在几分钟后检查:)

编辑（对于括号）：括号被视为特殊字符，仅在关闭后才评估。为了让它们工作，将以下 2 个值添加到 operatorlist：

    {'*',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]);
    }
于 2013-03-12T07:22:36.803 回答