使用 Java 的递归表达式求值器
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4073069/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Recursive expression evaluator using Java
提问by 629
I am going to write an expression evaluator which only does addition and subtraction. I have a simple algorithm to do that; but, I have some implementation problems.
我将编写一个仅执行加法和减法的表达式求值器。我有一个简单的算法来做到这一点；但是，我有一些实施问题。
I considered an expression as (it is a String)
我认为一个表达式为（它是一个字符串）
"(" <expression1> <operator> <expression2> ")"
Here is my algorithm
这是我的算法
String evaluate( String expression )
if expression is digit
return expression
else if expression is "(" <expression1> <operator> <expression2> ")"
cut the brackets out of it
expression1 = evaluate( <expression1> )
operator = <operator>
expression2 = evaluate( <expression2> )
if operator is +
expression1 + expression2
else if operator is -
expression1 - expression2
My problem is parsing <expression1>, <operator>and <expression2>from the expression. How can I do that?
我的问题是解析<expression1>,<operator>和<expression2>表达式。我怎样才能做到这一点？
Note: I'm not asking for a code. All I need is an idea to do that.
注意：我不是要代码。我所需要的只是一个想法来做到这一点。
Thank you,
谢谢，
-Ali
-阿里
采纳答案by The Archetypal Paul
My problem is parsing <expression1>, <operator> and <expression2> from the expression
我的问题是从表达式中解析 <expression1>、<operator> 和 <expression2>
Don't do that, then :) When you see an opening bracket, do your recursive call to expression. At the end of the expresssion, either you find another operator (and so you're not at the end of the expression after all), or a right-bracket, in which case you return from the evaluate.
不要那样做，然后 :) 当您看到一个左括号时，请执行对表达式的递归调用。在表达式的末尾，您可以找到另一个运算符（因此您毕竟不是在表达式的末尾），或者是右括号，在这种情况下，您从评估返回。
回答by aioobe
Either you use a parser generator such as JavaCUPor ANTLR. Write up a BNF of your expression and generate a parser. Here is a sample grammar that would get you started:
您可以使用解析器生成器，例如JavaCUP或ANTLR。编写表达式的 BNF 并生成解析器。这是一个可以帮助您入门的示例语法：
Expression ::= Digit
| LeftBracket Expression Plus Expression RightBracket
| LeftBracket Expression Minus Expression RightBracket
| LeftBracket Expression RightBracket
A "hacky" way of doing it yourself would be to look for the first )backtrack to the closest (look at the parenthesis free expression in between, simply split on the operator symbols and evaluate.
一种自己做的“hacky”方法是寻找)最接近(括号自由表达式的第一个回溯，简单地拆分运算符符号并评估。
回答by Luke Hutteman
Use a StringTokenizer to split your input string into parenthesis, operators and numbers, then iterate over your tokens, making a recursive call for every open-parens, and exiting your method for every close parenthesis.
使用 StringTokenizer 将您的输入字符串拆分为括号、运算符和数字，然后迭代您的标记，对每个开括号进行递归调用，并为每个右括号退出您的方法。
I know you didn't ask for code, but this works for valid input:
我知道您没有要求提供代码，但这适用于有效输入：
public static int eval(String expr) {
StringTokenizer st = new StringTokenizer(expr, "()+- ", true);
return eval(st);
}
private static int eval(StringTokenizer st) {
int result = 0;
String tok;
boolean addition = true;
while ((tok = getNextToken(st)) != null) {
if (")".equals(tok))
return result;
else if ("(".equals(tok))
result = eval(st);
else if ("+".equals(tok))
addition = true;
else if ("-".equals(tok))
addition = false;
else if (addition)
result += Integer.parseInt(tok);
else
result -= Integer.parseInt(tok);
}
return result;
}
private static String getNextToken(StringTokenizer st) {
while (st.hasMoreTokens()) {
String tok = st.nextToken().trim();
if (tok.length() > 0)
return tok;
}
return null;
}
It would need better handling of invalid input, but you get the idea...
它需要更好地处理无效输入，但你明白了......
回答by Callum Rogers
I would recommend changing the infix input into postfix and then evaluating it, rather than reducing the expression infix-wise. There are already well defined algorithms for this and it doesn't come with the inherent multiple-nested-parentheses parsing problems.
我建议将中缀输入更改为后缀，然后对其进行评估，而不是减少中缀表达式。已经有明确定义的算法，它没有固有的多嵌套括号解析问题。
Take a look at the Shunting Yard Algorithmto convert to postfix/RPN then evaluate it using a stack using Postfix Operations. This is fast (O(n)) and reliable.
查看Shunting Yard Algorithm以转换为 postfix/RPN，然后使用Postfix Operations使用堆栈对其进行评估。这是快速 (O(n)) 和可靠的。
HTH
HTH
回答by Martin T?rnwall
I would suggest taking an approach that more closely resembles the one described in thisold but (in my opinion) relevant series of articles on compiler design. I found that the approach of using small functions/methods that parse parts of the expression to be highly effective.
我建议采取的做法更类似于中描述的这对编译器设计老，但（在我看来）相关系列文章。我发现使用解析表达式部分的小函数/方法的方法非常有效。
This approach allows you to decompose your parsing method into many sub-methods whose names and order of execution closely follows the EBNFyou might use to describe the expressions to be parsed.
这种方法允许您将解析方法分解为许多子方法，这些子方法的名称和执行顺序与您可能用来描述要解析的表达式的EBNF密切相关。
回答by jarmod
Perhaps create regular expressionsfor expressionand operatorand then use matching to identify and break out your content.
也许为表达式和运算符创建正则表达式，然后使用匹配来识别和分解您的内容。
