前言
今天刚好遇到一个需求，用户输入任意公式，返回计算结果。
例子:文章源自灵鲨社区-https://www.0s52.com/bcjc/javajc/15863.html
properties
工资 = "出勤天数 * 基本工资/当月工作日 + 绩效奖金 - 迟到早退扣钱"
这里分享一个解析数学表达式的方法，我这里使用的是递归下降解析器（recursive descent parser）的解析方法，这是一种自顶向下的解析方法。文章源自灵鲨社区-https://www.0s52.com/bcjc/javajc/15863.html
EBNF
首先介绍一下EBNF(扩展巴科斯范式 , Extended Backus–Naur Form) , 它是一种表达形式语言文法的代码。有点类似于正则表达式文章源自灵鲨社区-https://www.0s52.com/bcjc/javajc/15863.html
简单举几个例子文章源自灵鲨社区-https://www.0s52.com/bcjc/javajc/15863.html
properties
# 表示字母
letter = 'a'|'b'|'c'|'d'|'e'|'f'|'g'|'h'|'i'|'j'|'k'|'l'|'m'|'n'|'o'|'p'|'q'|'r'|'s'|'t'|'u'|'v'|'w'|'x'|'y'|'z'|'A'|'B'|'C'|'D'|'E'|'F'|'G'|'H'|'I'|'J'|'K'|'L'|'M'|'N'|'O'|'P'|'Q'|'R'|'S'|'T'|'U'|'V'|'W'|'X'|'Y'|'Z';
# 等同于letter = 'a' ... 'z' | 'A' ... 'Z' ;
# 表示数字 1-9
nonzero_digit = '1'...'9' ;
# 表示数字 0-9
digit = '0' | nonzero_digit ;
# 表示单词
word = (letter | '_') { '_' | letter | digit } ;
# 表示整数
int = '0' | ['+'|'-'] nonzero_digit { digit } ;
- | 表示或
- ... 表示范围，可用于表示连续的字符
- {} 花括号表示出现0次或多次， 类似正则的*
- '' 表示字符串
- [] 表示可选，类似正则的?
基本运算公式的EBNF
通过上面的例子，大家应该大概明白ebnf的机制，这里我们写一下包含+-*/运算表达式的ebnf文章源自灵鲨社区-https://www.0s52.com/bcjc/javajc/15863.html
properties
digit = '0'...'9' ;
nonzero_digit = '1'...'9';
factor = nonzero_digit ['.' {digit} ] ; #这里表示小数
term = factor { ('*'|'/') factor } ;
expression = term { ('+'|'-') term } ;
这里大家应该可以发现，优先级越高的运算符需要优先计算；+-优先级最低，因此放在最外层的expression中。在日常生活的口算中，我们应该也会把term中的*/优先计算，再做+-运算文章源自灵鲨社区-https://www.0s52.com/bcjc/javajc/15863.html
如：文章源自灵鲨社区-https://www.0s52.com/bcjc/javajc/15863.html
properties
res = 1 + 2 * 3 + 4 * 5
= 1 + 6 + 20
# 这里的 1，6，20 相当于term
# 2，3，4 ，5 相当于factor
代码实现
版本一
到这里我们得出了运算表达式的ebnf，接下来我们来实现一个简单的解析器文章源自灵鲨社区-https://www.0s52.com/bcjc/javajc/15863.html
java
public class SimpleExpressionParser {
SimpleExpressionParser() {
}
int ch, pos = -1;
String str;
void nextChar() {
ch = (++pos < str.length()) ? str.charAt(pos) : -1;
}
boolean expect(char expectChar) {
while (ch == ' ') nextChar();
if (ch == expectChar) {
nextChar();
return true;
}
return false;
}
public static BigDecimal parse(String str) {
SimpleExpressionParser parser = new SimpleExpressionParser();
parser.str = str;
parser.nextChar();
return parser.parseExpression();
}
/**
* expression = term { ('+'|'-') term } ;
*/
BigDecimal parseExpression() {
BigDecimal x = parseTerm();
for (; ; ) {
if (expect('+')) x = x.add(parseTerm());
else if (expect('-')) x = x.subtract(parseTerm());
else return x;
}
}
/**
* term = factor { ('*'|'/') factor } ;
*/
BigDecimal parseTerm() {
BigDecimal x = parseFactor();
for (; ; ) {
if (expect('*')) x = x.multiply(parseFactor());
else if (expect('/')) x = x.divide(parseFactor(), 4, BigDecimal.ROUND_HALF_UP); //保留4位小数
else return x;
}
}
/**
* factor = nonzero_digit ['.' {digit} ] ;
*/
BigDecimal parseFactor() {
BigDecimal x;
// 跳过空格
while (ch == ' ') nextChar();
int startPos = this.pos;
if ('0' <= ch && ch <= '9' || ch == '.') {
while ('0' <= ch && ch <= '9' || ch == '.') nextChar();
x = new BigDecimal(str.substring(startPos, this.pos));
} else {
throw new RuntimeException("Unexpected: " + (char) ch);
}
return x;
}
public static void main(String[] args) {
System.out.println(SimpleExpressionParser.parse(" 1 + 2*3-4.5/5"));
}
}
结合ebnf范式去实现代码，我们应该可以很清晰的看到每一步要做什么。文章源自灵鲨社区-https://www.0s52.com/bcjc/javajc/15863.html
版本二
上面的代码有些问题，比如没有处理括号，没有处理负数，这些问题，这里我们来改进一下文章源自灵鲨社区-https://www.0s52.com/bcjc/javajc/15863.html
ebnf范式
先按自己的理解写下ebnf范式
properties
digit = '0'...'9' ;
letter = 'a'...'z' | 'A'...'Z';
nonzero_digit = '1'...'9';
variable = (letter | '_') { '_' | letter | digit } ; #这里表示变量
num = nonzero_digit ['.' {digit} ]
factor = ['+'|'-'] ( variable | num | '(' expression ')' ) ;
term = factor { ('*'|'/') factor } ;
expression = term { ('+'|'-') term } ;
代码实现
鉴于我们只改了factor的范式，因此我们只需要改一下parseFactor()方法即可
代码如下
java
public class SimpleExpressionParser1 extends SimpleExpressionParser {
Map<String, BigDecimal> map;
public static BigDecimal parse(String str, Map<String, BigDecimal> map) {
SimpleExpressionParser1 parser = new SimpleExpressionParser1();
parser.str = str;
parser.map = map;
parser.nextChar();
return parser.parseExpression();
}
private static boolean isLetter(int ch) {
return 'a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z';
}
private static boolean isNum(int ch) {
return '0' <= ch && ch <= '9';
}
/**
* factor = ['+'|'-'] ( variable | num | '(' expression ')' ) ;
*/
BigDecimal parseFactor() {
if (expect('+')) return parseFactor();
if (expect('-')) return parseFactor().negate();
BigDecimal x;
int startPos = this.pos;
if (expect('(')) {
x = parseExpression();
if (!expect(')')) throw new RuntimeException("Expected ')'");
} else if (isNum(ch) || ch == '.') { //解析数字
while (isNum(ch) || ch == '.') nextChar();
x = new BigDecimal(str.substring(startPos, this.pos));
} else if (isLetter(ch) || ch == '_') { // 解析变量
while (isLetter(ch) || isNum(ch) || ch == '_') nextChar();
String var = str.substring(startPos, this.pos);
x = map.get(var);
if (x == null) {
throw new RuntimeException("Unknown variable: " + var);
}
} else {
throw new RuntimeException("Unexpected: " + (char) ch);
}
return x;
}
public static void main(String[] args) {
// 预期值， 5
System.out.println(SimpleExpressionParser1.parse("-a * ( a * -(-5+10*a))", new HashMap<>() {{
put("a", new BigDecimal(1));
}}));
// 预期值，11
System.out.println(SimpleExpressionParser1.parse("a * -b + c - (-d) * 3", new HashMap<>() {{
put("a", new BigDecimal(1));
put("b", new BigDecimal(2));
put("c", new BigDecimal(3));
put("d", new BigDecimal(-4));
}}));
}
}
到目前为止我们实现了一个简单的表达式解析器。有兴趣可以再自行实现一下 位运算(>>,<<)，逻辑运算（&&,||,!），三目运算符(?:)，函数调用（如求和，求最大/小值，开方），关系运算符（>,<,=）等。
可以尝试实现解析： a > b ? max(1,2,3,4*(5+3)%2,min(7,sqrt(5))) : 20
评论