5

您将如何有效地（针对运行时进行优化，同时将空间保持在最低限度）解析和评估 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;
}

这是唯一的最佳解决方案吗？我曾尝试使用堆栈来跟踪算术运算符，但我不确定这是否更有效。我也没有尝试过正则表达式。我之所以问，是因为我在一次采访中给出了上述解决方案，并被告知这是次优的。

4

2 回答 2

3

这似乎更紧凑一些。它当然需要更少的行和条件。关键是添加是“默认”行为，您遇到的每个减号都会更改您要添加的符号；前提是您记得在每次添加后重置符号。

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
于 2013-09-13T05:03:55.217 回答
0

您需要查找“递归下降表达式解析器”或 Dijkstra 分流场算法。当您必须处理运算符优先级或括号时，您目前的方法注定要失败。您还需要忘记正则表达式并放弃自己编写适当的扫描仪。

于 2013-09-13T05:32:29.393 回答