數學表達式求值出了錯

Question

傢伙嗨，

我已經開始使用的Dijkstra 2堆棧算法使這個數學表達式求值，我想我已經仔細地應用了所有規則，但問題是，它可以評估一些表達正確，一些錯誤的：/

//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：我不得不做出這樣一個應用程序..

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

    } 

的問題是，如果你最終在堆棧中，由於評估操作要比當前操作具有更高的優先級，則必須檢查堆棧的新頭是否與當前操作相比具有更高或相同的優先級。我用while循環替換了if語句以繼續檢查，直到不再滿足條件。

我會盡力讓括號工作和:)

Edit（對於括號內）將檢查回來幾分鐘： 支架作爲其只計算一次關閉特殊字符處理。爲了讓他們的工作添加下列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]); 
    }