我的算法中評估基本括號表達的缺陷在哪裏？

Question

我試圖執行一個程序，就像

輸入：

~1^(2~&3)|1 69 11111 -12 

輸出：

[whatever NOT 69 XOR (11111 NAND -12) OR 69 equals] 

與具有相同的優先級所有的位運算符，評估左向右。我構建算法基本上

Get number n1 (or evaluation of expression in parenthesis) 
Set result = n1 
Get operator o1 
Get number n2 (or evaluation of expression in parenthesis) 
Set result = result op n2 
Get operator o2 
Get number n3 (or evaluation of expression in paranthesis) 
Set result = result o2 n3 
Etcetera 

我不完全完成，但我有什麼應該至少能夠評估

((1)) 69 

這將導致

69 

我已測試過

(1) 69 

結果

69 

這意味着我只需要搞清楚什麼是與嵌套的括號走錯了。

我的代碼的相關部分，很好的評價，是...忍耐一下這裏...

private static long? EvalInner (string eqtn, Tuple<int,int> eqtnBnds, Dictionary<int,long> eqtnArgs) 
    { 
     //  eqtn: Equation to be parsed 
     // eqtnBnds: Bounds that define sub-equation being evaluated. 
     // eqtnargs: Equation arguments 

     // Parses and returns the evaluation of the equation eqtn in the bounds [eqtnBands.Item1, eqtnBnds.Item2) 

     // Handle case of empty sub-equation: 
     if (eqtnBnds.Item1 == eqtnBnds.Item2) throw new Exception(String.Format("Encountered empty equation at index {0}", eqtnBnds.Item1)); 


     long? result = null; 
     char? lastop = null; // last operator found 
     bool negateNextNum = false; 
     PARSEMODE CURMODE = PARSEMODE.NUM; // beginning of equation should be a number since the form of the equation is 
              // <NUM><OPER><NUM><OPER>...<OPER><NUM> 
     int curidx = eqtnBnds.Item1, offend = eqtnBnds.Item2; 
     while (curidx < offend) 
     { 
      switch (CURMODE) 
      { 
       case PARSEMODE.NUM: // Expecting character at current index to be the beginning of a 
       { 
        if (eqtn[curidx] >= '0' && eqtn[curidx] <= '9') // beginning of the int corresponding to the argument index 
        { 
         int begidx = curidx; 
         // Increment curidx to one after the last digit or the end of the subequation 
         while (++curidx < offend && eqtn[curidx] >= '0' && eqtn[curidx] <= '9'); 
         // Try to get an integer representation of the argument. If an error is encountered in that parsing, 
         // throw an error. If the argument is one within the range of arguments given in the command line, 
         // get its value and update result accordingly. If not, throw an error. 
         int argnum; 
         if (Int32.TryParse(eqtn.Substring(begidx, curidx - begidx), out argnum)) 
         { 
          if (eqtnArgs.ContainsKey(argnum)) 
          { 
           result = (result != null ? BinOpEval(result, lastop, eqtnArgs[argnum]) : eqtnArgs[argnum]); 
           if (negateNextNum) 
           { 
            result = ~result; 
            negateNextNum = false; 
           } 
          } 
          else 
           throw new Exception(String.Format("Argument {0} found in the equation beginning at index {1} is out-of-bounds", 
                    argnum, 
                    begidx) 
                ); 
         } 
         else 
         { 
          throw new Exception(String.Format("Trouble parsing argument number that begins at index {0}", 
                   begidx) 
               ); 
         } 
         CURMODE = PARSEMODE.OPER; 
        } 
        else if (eqtn[curidx] == Calculator.OPENPAREN) // beginning of subequation in paranthesis 
        { 
         int begidx = curidx, netparens = 1; 
         while (++curidx < offend && netparens != 0) 
         { 
          if  (eqtn[curidx] == Calculator.OPENPAREN ) ++netparens; 
          else if (eqtn[curidx] == Calculator.CLOSEPAREN) --netparens; 
         } 
         if (netparens != 0) // didn't find closing parenthesis 
          throw new Exception(String.Format("Couldn't find closing paranthesis for opening paranthesis at index {0}", 
                   begidx) 
               ); 
         long? presult = null; // to be the result of the evaluated subequation between the set of parenthesis 
         try { presult = EvalInner(eqtn,new Tuple<int, int>(++begidx, curidx - begidx),eqtnArgs); } 
         catch (Exception e) { throw e; } 
         result = (result != null ? BinOpEval(result,lastop,presult) : presult); 
         if (negateNextNum) 
         { 
          result = ~result; 
          negateNextNum = false; 
         } 
         // Upon leaving this else-if block, curidx should be 1 after the closing paranthesis 
         // Expect operate to following closing paranthesis 
         CURMODE = PARSEMODE.OPER; // expecting operator after parens 
        } 
        else if (eqtn[curidx] == Calculator.NOT) // NOT symbol preceding number 
        { 
         negateNextNum = !negateNextNum; 
         ++curidx; 
         // CURMODE stays as num 
        } 
        else // unexpected character where beginning of number expected 
        { 
         throw new Exception(String.Format("Expected beginning of number at index {0}, instead got {1}", 
                  curidx, 
                  eqtn[curidx]) 
              ); 
        } 
        break; 
       } 

       case PARSEMODE.OPER: 
       { 
        // ... 

，我試圖找出邏輯之所以

((1)) 69 

是印刷錯誤

Error: Encountered empty equation at index 2 

讓我通過我的邏輯：

起初curidx = 0,eqtn[curidx] = '('和CURMODE = PARSEMODE.NUM。這使我們進入塊

    else if (eqtn[curidx] == Calculator.OPENPAREN) // beginning of subequation in paranthesis 
        { 
          // ... 
        } 

在方框

     int begidx = curidx, netparens = 1; 
         while (++curidx < offend && netparens != 0) 
         { 
          if  (eqtn[curidx] == Calculator.OPENPAREN ) ++netparens; 
          else if (eqtn[curidx] == Calculator.CLOSEPAREN) --netparens; 
         } 

之後begidx是0和curidx的部分的端部是5（索引一個右括號之後）。因此，++begidx是1和curidx - begidx（在++begidx之後評估）是4。因此，調用

EvalInner(eqtn,new Tuple<int, int>(++begidx, curidx - begidx),eqtnArgs); } 

後我們最終回到塊

    else if (eqtn[curidx] == Calculator.OPENPAREN) // beginning of subequation in paranthesis 
        { 
         int begidx = curidx, netparens = 1; 
         while (++curidx < offend && netparens != 0) 
         { 
          if  (eqtn[curidx] == Calculator.OPENPAREN ) ++netparens; 
          else if (eqtn[curidx] == Calculator.CLOSEPAREN) --netparens; 
         } 

和上述begidx = 1和curidx = 4（索引一個右括號後）。然後++begidx = 2和今後curidx - begidx = 2，當我們再次進入EvalInner我們EQT n[curidx] = '1'，使我們進入塊

    if (eqtn[curidx] >= '0' && eqtn[curidx] <= '9') // beginning of the int corresponding to the argument index 
        { 
         // ... 
        } 

之後，很顯然，我們已經oarsed的1，用參數69相關的它，並通過通過調用堆棧返回到輸出。

我在哪裏出錯了？

Answer 1

元組的第二個元素是否意味着子方程的長度或其上界？

presult = EvalInner(eqtn,new Tuple<int, int>(++begidx, curidx - begidx),eqtnArgs); 

這本來可能是更多的幫助，以簡單有清晰兩個命名的參數，但基於早於遞歸調用您的使用情況，它看起來好像是指是上限，但你正在傳遞一個長度。

也許這是唯一的問題？不確定。

Answer 2

只要你的代碼確實顯示了相關的工作並修復它可能並不簡單，我寧願寫一個遞歸算法來提供你想要的功能。

下面的代碼的基本思路：

• removeAllParen開始解析過程。它執行基本的 有效性檢查（即相同數量的開始和結束括號） 以決定是否需要執行實際分析的函數的新調用。所有這些調用都是遞歸地構建最終輸出。
• removeOneParen僅處理一組括號，最外部的括號（例如，來自「（（（1））」）輸出是「（（（1））」）。它 尋找第一個左括號和最後一個右括號。

請記住，這只是一個示例代碼，可幫助您瞭解如何遞歸解決這種情況。這不是一個全面的括號分析方法，而是一個適合您的特定條件的方法。例如，第二個函數在像「（1）（1）」這樣的情況下會失敗（儘管調整它並不太困難;您將不得不依賴類似於您正在進行的開/關 - 括號計數方法你的代碼）。

private string removeAllParen(string input) 
{ 
    string output = input; 

    int openingCount = 0; 
    int closingCount = 0; 
    do 
    { 
     openingCount = output.Split('(').Length - 1; 
     closingCount = output.Split(')').Length - 1; 
     if (openingCount != closingCount || openingCount < 1 || closingCount < 1) 
     { 
      if (openingCount != closingCount) output = "ERROR"; 
      break; 
     } 
     output = removeOneParen(output); 
    } while (true); 


    return output; 
} 

private string removeOneParen(string input) 
{ 
    string output = input; 
    int count = 0; 

    bool error = false; 
    int iIni = 0; 
    int iEnd = output.Length - 1; 
    while (count < 2) 
    { 
     count = count + 1; 
     bool ended = false; 
     if (count == 2) 
     { 
      iIni = output.Length - 1; 
      iEnd = 0; 
     } 
     int i = iIni; 
     while (!ended) 
     { 
      string curBit = output.Substring(i, 1); 
      if (curBit == "(" || curBit == ")") 
      { 
       if (count == 1 && curBit == "(" && i < output.Length - 2) output = output.Substring(i + 1); 
       else if (count == 2 && curBit == ")") output = output.Substring(0, i); 
       else error = true; 
       break; 
      } 
     } 
     if (error) break; 
    } 

    if (error) output = "ERROR"; 

    return output; 
} 

UPDATE

只是爲了完整起見，在這裏你有removeOneParen另一個版本提供基於上述打開/關閉括號數更全面的答案。

private string removeOneParen(string input) 
{ 
    string output = "ERROR"; 

    int openingCount = 0; 
    int closingCount = 0; 
    bool firstOpening = true; 
    int startI = -1; 
    for (int i = 0; i < input.Length; i++) 
    { 
     string curBit = input.Substring(i, 1); 
     if (curBit == "(") 
     { 
      openingCount = openingCount + 1; 
      if (firstOpening) 
      { 
       startI = i + 1; 
       firstOpening = false; 
      } 
     } 
     else if (curBit == ")") 
     { 
      closingCount = closingCount + 1; 
      if (openingCount == closingCount) 
      { 
       if(startI > 0) output = input.Substring(0, startI - 1); 
       output = output + input.Substring(startI, i - startI); 
       if(i < input.Length - 1) output = output + input.Substring(i + 1); 
       break; 
      } 
     } 
    } 

    return output; 
}