Metoda java do parsowania wyrażeń zagnieżdżonych

Question

Powiedzmy, że napisałem funkcję do oceny prostej operacji matematycznej i mam pewne dane wejściowe użytkownika w ciągu znaków, takie jak: "1 + [2 + [3 + 4]]" Jak mogę przeanalizować te nawiasy kwadratowe i wyodrębnić najpierw tekst najbardziej wewnętrzny (3 + 4), ocenić go, a następnie przeanalizować zewnętrzne nawiasy klamrowe (2 + 7)? Mam podstawową wiedzę na temat wyszukiwania Regex i zastępowania, ale wiem, że nie będą wykonywać rekursji w ten sposób. Chciałbym wykonać podstawowy kod java, a nie kolejny jar/API, jeśli mogę tego uniknąć.

Answer 1

Najczystszym sposobem na osiągnięcie celu jest napisanie do tego celu narzędzia Lexer i analizatora składni. Napisanie recursive descent parser nie jest trudne do zrobienia od zera dla wyrażeń arytmetycznych.

Istnieje wiele przykładów kodu w Internecie. This is an example, którego możesz użyć do inspiracji.

Lexer ma na celu znormalizowanie danych wejściowych i przekształcenie go w strumień tokenów. W ten sposób twój Parser musi pracować tylko na tokenach, zamiast dodatkowo zajmować się problemami białych znaków i innymi irytującymi rzeczami.

Twoexamples dla algorytmów wysokiego poziomu, które są oparte na stosach, another example, które pokazują podejście do nurkowania rekursywnego.

Answer 2

myślę regex nie jest to dobry wybór, aby osiągnąć tę funkcjonalność

należy przekonwertować wypowiedzi użytkownika do postfix lub notacji prefiksu, a następnie zbudować drzewa wyrażenie z nich. Jest to standardowe podejście w CS (język nie ma znaczenia tutaj), aby rozwiązać ten problem w czystym sposób

Answer 3

Recursion działa dobrze dla nich:

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

Answer 4

Użyj stos. Gdy natrafisz na otwarty nawias, wciśnij cokolwiek pracujesz na stos i zacznij nowe wyrażenie. Kiedy uderzysz w nawias zamykający, popnij stos i użyj wyrażenia właśnie obliczonego jako następny element. Lub, jak powiedzieli poprzednie plakaty, użyj rekurencji lub drzewa.

Answer 5

Dla języka Java można użyć JavaCC dla parser/lekser. Użyłem tego w wielu projektach. Jest dość łatwy w użyciu. Jeden z przykładów, jak sądzę, obejmuje analizę arytmetyczną. JavaCC zbuduje drzewo składniowe, w którym można przejść.

Próba arytmetyczna za pomocą JavaCC dałaby dobre wprowadzenie do gramatyki bezkontekstowej i koncepcji drzewa składni abstrakcyjnej. Jeśli się uczysz, jest to dobry krok do zrobienia po wypróbowaniu tego, co @emboss zasugerował