表達式評估 - 避免StackOverflow異常

我一直在擺弄我自己的表達式求值器，並在這個我很好奇的問題上登陸。表達式評估 - 避免StackOverflow異常

我已經使用了2種評估字符串表達式的方法。一種方法使用二叉樹。

當我輸入長度大於（大約）42000的表達式字符串時，我得到一個stackoverflow異常。

但是同樣的，如果我使用此功能（我的第二個實現）

現在我寧願堅持二叉樹方法評估相同的表達式字符串（甚至多更長的長度）不會發生 - 有沒有辦法我可以修復堆棧溢出異常，即我可以避免我的堆棧溢出遞歸還是有辦法找到何時堆棧實際上溢出？如果不是，即使表達式開始評估堆棧溢出可能發生之前，我怎麼才能實際上至少警告用戶？

來源

2013-10-14 Sadique

你有沒有考慮重新分析你的字符串以反轉波蘭表示法（http://en.wikipedia.org/wiki/Reverse_Polish_notation），這將允許你用少得多的複雜度來做到這一點 – MikeT

什麼參數'字符串strPostFix'對你來說意味着什麼？ – Sadique

我確實想知道，在這種情況下，你的二叉樹不幸是完全錯誤的方法來處理這個，它的Bodmas風格的數學需要樹分析。所以你的第二個解決方案是正確的一個 – MikeT

老實說，你最好的選擇是使用第二種方法。雖然遞歸在這裏可用，但從算法的角度來看，您提供的堆棧方法更加正確 - 主要是因爲您的二叉樹方法沒有辦法處理一元運算符（至少據我所知）（例如，++ i）。

至於你的第一個問題，沒有一個真正的方法來判斷是否有東西會從剛纔的輸入中拋出堆棧溢出異常。你最好的選擇是將try/catch中的遞歸方法的第一個調用包裝起來，並明確地捕獲StackOverflowException，並向用戶返回一個有效的錯誤消息。另外，請記住，如果需要，理論上可以將二叉樹實現移至使用類似於數字2的堆棧對象。儘管您仍然需要重新設計使用堆棧而不是應用程序堆棧的方法。

來源

2013-10-14 13:40:03

表達式評估 - 避免StackOverflow異常

回答

相關問題