java method for parsing nested expressions

Question

lets say I've written 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 first the inner-most text (3+4), evaluate it, then parse the outer braces (2 + 7)? I have a rudimentary understanding of Regex search and replace, but I know they won't do recursion like this. I'd like some basic java code to do this, not yet another jar/API if I can avoid it.

Answer 1

The cleanest way to accomplish your goal is to write a Lexer and a Parser for this purpose. Writing a recursive descent parser is not that hard to do from scratch for arithmetic expressions.

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

The Lexer is there to normalize your input and to abstract it to a stream of tokens. This way, your Parser only needs to work on tokens instead of additionally having to deal with whitespace issues and other annoying things.

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

Answer 2

Use a stack. When you encounter an open bracket, push whatever you're working on onto the stack and start the new expression. When you hit a closing bracket, pop the stack and use the expression you just calculated as the next item. Or, as previous posters have said, use recursion or a tree.