有效地解析单个数字运算EX pression [英] Efficiently parse single digit arithmetic expression

问题描述

你会如何高效地（优化的运行时，也保持空间最小）分析和评价一个数字的算术EX pression Java编写的。

How would you efficiently (optimizing for runtime but also keeping space at a minimum) parse and evaluate a single digit arithmetic expression in Java.

下面的算术EX pressions都是有效的：

The following arithmetic expressions are all valid:

eval("-5")=-5
eval("+4")=4
eval("4")=4
eval("-7+2-3")=-8
eval("5+7")=12

我的做法是遍历所有元素，使用标志保持当前运算的轨道，并通过数字计算数字。

My approach is to iterate over all elements, keeping track of the current arithmetic operation using a flag, and evaluate digit by digit.

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

这是唯一的最佳解决方案？我曾尝试使用堆栈跟踪的算术运算符的，但我不知道这是任何更有效。我还没有尝试过正规EX pressions。我只问，因为我给在接受采访时上述溶液，被告知这是次优的。

Is this the only optimal solution? I have tried to use stacks to keep track of the arithmetic operator, but I am not sure this is any more efficient. I also have not tried regular expressions. I only ask because I gave the above solution in an interview and was told it is sub-optimal.

推荐答案

这似乎更紧凑一点。这当然需要较少的线路和条件。最关键的是增加的是默认的行为，你遇到什么样的变化，你要添加的符号每个减号;只要你还记得每次加入后重置标志。

This seems a bit more compact. It certainly requires fewer lines and conditionals. The key is addition is the "default" behavior and each minus sign you encounter changes the sign of what you want to add; provided you remember to reset the sign after each addition.

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。您的code产生1，而不是7。另一方面正确的值，我的允许EX pressions如5 + - + - 3，这将产生结果8（我想这是正确的？:)。但是，你没有列出审定时的要求和我们俩都检查连续数字，字母字符，空格等。如果我们假设数据是正确的格式，上面的实现应该工作。我不知道怎样将数据结构（如队列）也可能会有所帮助这里。我也假设只是加减。

As a note, I don't think yours produces correct results for adding a negative, e.g., "4- -3". Your code produces 1, rather than the correct value of 7. On the other hand, mine allows expressions such as "5+-+-3", which would produce the result 8 (I suppose that's correct? :). However, you didn't list validation as a requirement and neither of us are checking for sequential digits, alpha characters, white space, etc. If we assume the data is properly formatted, the above implementation should work. I don't see how adding data structures (such as queues) could possibly be helpful here. I'm also assuming just addition and subtraction.

这些测试案例产生以下结果：

These test cases produce the following results:

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

这篇关于有效地解析单个数字运算EX pression的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！