高效解析单个数字算术表达式

Question

高效解析单个数字算术表达式

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

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

- stevebot

1

你有类似这样的情况吗：eval("4+-5")？ - Krishna Sarma

@KrishnaSarma 是的，鉴于这些属性（例如，eval("+5")=5或eval("-4")=-4），这是可能的。 - stevebot

4

仅仅因为我非常懒，所以执行 new ScriptEngineManager().getEngineByExtension("js").eval("-7+4")。 - sgbj

不要使用字符串，可以使用向量、数组列表或堆栈类来进一步优化代码。通常我们不会过多地使用字符串，因为它们往往会占用更多的资源。 - Nitesh Verma

@NiteshVerma 这就是我不理解的地方。我所做的唯一字符串操作似乎完全是必要的，因为你必须从字符串中解析每个操作和数字。 - stevebot

2个回答

0

你需要查找“递归下降表达式解析器”或Dijkstra的Shunting-yard算法。你现在的方法注定会失败，一旦你必须处理运算符优先级或括号。你还需要忘记正则表达式，并准备好编写一个合适的扫描器。

- user207421

你读了这个问题吗？它是在面试中提出的，他们可能想要代码，并且限制为单个数字值。我不认为他们正在寻找一个功能齐全的解析器。 - Jeremy West

你好，以下是程序相关的内容翻译：并不清楚您是否理解这个问题。'单个数字值'与此无关。他需要一个表达式解析器，除非有其他未提及的约束条件。这是我会给出的答案，如果他们告诉我这是“次优”的，我会离开，并在编译器中多次实现它。相反，如果我是面试官，（a）我不会问这样的问题，因为我会准备好培训适合资质的候选人，但是（b）任何没有使用堆栈的回答都将被拒绝。 - user207421

不，我绝对理解这个问题。 - Jeremy West

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jeremy West · Accepted Answer

这个代码看起来更加简洁。它需要更少的行数和条件语句。关键在于加法是“默认”行为，每遇到一个减号就会改变你想要添加的数的符号；只要每次加法后记得重置符号即可。

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