2011-08-31 28 views
6

可以說我寫了一個函數來評估一個簡單的數學運算,並且我在字符串中有一些用戶輸入,例如: 「1 + [2 + [3 + 4]]」 我該如何解析這些方括號並首先提取最內層文本(3 + 4),評估它,然後解析外括號(2 + 7)? 我對正則表達式的搜索和替換有一個基本的理解,但我知道他們不會像這樣做遞歸。 我想要一些基本的java代碼來做到這一點,如果我能避免它,還不是另一個jar/API。解析嵌套表達式的java方法

+0

相關:https://stackoverflow.com/questions/3422673/evaluating-a-math-expression-given-in-string -形成 – Boann

回答

9

完成您的目標的最簡潔的方法是爲此寫一個詞法分析器和一個解析器。編寫一個recursive descent parser對於算術表達式來說不難做到。

網上有很多代碼示例。 This is an example,你可以使用靈感。

詞法分析器在那裏規範化您的輸入並將其抽象爲令牌流。這樣,你的解析器只需要處理令牌,而不必另外處理空白問題和其他煩人的事情。

Twoexamples適用於基於堆棧的高級算法,another example顯示遞歸下降方法。

2

我覺得正則表達式是不是一個很好的選擇來實現這一功能

你應該使用者表情轉換爲後綴或前綴符號,然後從他們建立一個表達式樹。 這是CS的標準方法(語言並不真正的問題在這裏)來解決這個問題,在一個乾淨的方式

0

遞歸非常適用於這些:

int parse(String expression){ 
    //use a regex to find an instance of [ followed by numbers/operators, followed by ] 
    //replace it with parse(whatever's inside the brackets) 
    //continue until there are none left 
    //evaluate the string (which should be a sequence of numbers and operators without brackets) 
} 
3

使用堆棧。當你遇到一個開放的括號時,將你正在工作的任何東西推入堆棧並開始新的表達式。當您敲一個右括號時,彈出堆棧,並使用剛計算的表達式作爲下一項。或者,正如前面的海報所說,使用遞歸或樹。

0

對於Java,您可以使用JavaCC作爲解析器/詞法分析器。我在很多項目中使用過這個。這很容易使用。我認爲其中的一個例子包括算術解析。 JavaCC將構建語法樹,您可以在其中瀏覽。

嘗試使用JavaCC的算術可以很好地介紹Context Free Grammar和抽象語法樹的概念。如果您正在學習,那麼在嘗試了@emboss建議的內容後,這是一個很好的步驟