Question

link

给定一个表达式字符串，其中只包含非负整数，加法，减法以及乘法符号，例如7+345+2+4-3-1。请写程序计算该表达式的值。

提示：可以尝试使用递归算法，程序将非常简洁易写，很适用于面试场合。

Solution

Trying to solve this problem iteratively is like suicide. The code would be lengthy and buggy, and very hard to make it right.

The most important point about this question, is how to handle minus(-) sign. We know that when we see * and /, we evaluate immediately, and when sees + and -, we postpone it. However this case:

1 - 2 - 3

If we postpone the first minus sign, we would end up getting:

1 - (-1)

So it’s wrong (outputing 2 in this case).

The solution to this issue is, consider (a - b) as (a + (-b)). That’s why later in the code, you’ll see a variable preNum being modified.

ref

Code

written by me

int p;

public int evaluate(String expr) {
    p = 0;
    int firstNum = getNumber(expr);
    return helper(firstNum, expr);
}

private int helper(int preNum, String expr) {
    // now p points to a operator (or end of string)
    if (p == expr.length()) {
        return preNum;
    }
    char operator = expr.charAt(p);
    p++;
    int nextNum = getNumber(expr);
    switch (operator) {
    case '+':
        return preNum + helper(nextNum, expr);
    case '-':
        return preNum + helper(-1 * nextNum, expr);
    case '*':
        return helper(preNum * nextNum, expr);
    default:
        return helper(preNum / nextNum, expr);
    }
}

private int getNumber(String expr) {
    // now p points to a number
    int num = 0;
    while (p < expr.length() && expr.charAt(p) >= '0'
            && expr.charAt(p) <= '9') {
        num = num * 10 + expr.charAt(p) - '0';
        p++;
    }
    return num;
}