如何有效地(优化运行时,同时保持最小空间)解析和计算 Java 中的单个数字算术表达式。
以下算术表达式都是有效的:
eval("-5")=-5
eval("+4")=4
eval("4")=4
eval("-7+2-3")=-8
eval("5+7")=12
我的方法是迭代所有元素,使用标志跟踪当前算术运算,并逐位评估。
public int eval(String s){
int result = 0;
boolean add = true;
for(int i = 0; i < s.length(); i++){
char current = s.charAt(i);
if(current == '+'){
add = true;
} else if(current == '-'){
add = false;
} else {
if(add){
result += Character.getNumericValue(current);
} else {
result -= Character.getNumericValue(current);
}
}
}
return result;
}
这是唯一的最优解吗?我尝试使用堆栈来跟踪算术运算符,但我不确定这是否更有效。我也没有尝试过正则表达式。我之所以这么问,是因为我在采访中给出了上述解决方案,但被告知它不是最优的。
这看起来更紧凑一些。它当然需要更少的行和条件。关键是加法是“默认”行为,您遇到的每个减号都会更改您要添加的内容的符号;前提是您记得在每次添加后重置标志。
public static int eval(String s){
int result = 0;
int sign = 1;
for(int i = 0; i < s.length(); i++){
char current = s.charAt(i);
switch (current)
{
case '+': break;
case '-': sign *= -1; break;
default:
result += sign * Character.getNumericValue(current);
sign = 1;
break;
}
}
return result;
}
请注意,我认为您的添加负数(例如“4- -3”)不会产生正确的结果。您的代码生成 1,而不是正确的值 7。另一方面,我的代码允许使用诸如“5+-+-3”之类的表达式,这将生成结果 8(我认为这是正确的?:)。但是,您没有将验证列为一项要求,而且我们都没有检查连续数字、字母字符、空格等。如果我们假设数据格式正确,则上述实现应该可以工作。我不明白添加数据结构(例如队列)在这里可能有什么帮助。我还假设只是加法和减法。
这些测试用例产生以下结果:
System.out.println(eval("1+2+3+4"));
System.out.println(eval("1--3"));
System.out.println(eval("1+-3-2+4+-3"));
10
4
-3
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)