Java method for parsing nested expressions

Question

lets say that I wrote a function to evaluate a simple mathematical operation, and I have some user input in a string, such as: "1 + [2 + [3 + 4]]" How can I parse these square brackets and extract the first inner text (3 + 4), evaluate it, then analyze external curly braces (2 + 7)? I have a rudimentary understanding of finding and replacing Regex, but I know that they will not do recursion like this. I would like some basic Java code to do this, not just another jar / API, if I can avoid it.

Answer 1

The cleanest way to achieve your goal is to write Lexer and Parser for that purpose. Writing recursive parsing is not so difficult to do from scratch for arithmetic expressions.

There are many code examples on the Internet. This is an example that you could use for inspiration.

The lexer should normalize your input and distract it from the token stream. Thus, your Parser should only work with tokens, instead of additionally dealing with problems with spaces and other unpleasant things.

Two examples for high-level stack-based algorithms, another example that shows a recursive descent approach.

Answer 2

Use the stack. When you come across an open bracket, push everything that you are working on the stack and start a new expression. When you hit the closing bracket, place the stack and use the expression that you just counted as the next element. Or, as previous posters said, use recursion or a tree.

Answer 3

I think regex is not a good choice to achieve this functionality.

You must convert the user expression to postfix or prefix notation, and then build an expression tree from them. This is a standard approach in CS (the language doesn't matter here) to solve this problem in a clean way.

Answer 4

Recursion works well for them:

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

Answer 5

For Java, you can use JavaCC for the parser / lexer. I have used this in numerous projects. It is pretty easy to use. One example, I think, involves arithmetic parsing. JavaCC will build a syntax tree that you could go through.

An attempt at arithmetic using JavaCC will provide a good introduction to the context free grammar and the concept of an abstract syntax tree. If you're a student, then this is a good step to try, as @emboss suggested