java method for parsing nested expressions

问题:

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.

回答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.

回答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.

回答3:

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

You should convert user expression to postfix or prefix notation and then build an expression tree from them. This is a standard approach in CS (language does not really matter here) to solve this issue in a clean way

回答4:

Recursion works well for these:

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

回答5:

For Java, you could use JavaCC for parser/lexer. I have used this one in numerous projects. It's pretty easy to use. One of the examples, I think, includes an arithmetic parsing. JavaCC will build the syntax tree where you could walk through.

Trying out arithmetic using JavaCC would give good intro to Context Free Grammar and the concept of Abstract Syntax Tree. If you are learning, then it is a good step to take after trying out what @emboss suggested