java - 递归地计算算术表达式

Question

我需要通过递归计算算术表达式 (INFIX) 的帮助。我做了一棵树，从右到左扫描(+，- 第一，*，/第二)。错误是:

For input string: "2+3"

我不知道我做错了什么。我希望有人能看看我的方法并指出正确的方向。感谢帮助。这是我的方法。

   // recursive method to evaluate an expression given by string s 
int evaluateE(String s)
{   
    String r1;
    String r2;
    int result = 0;
    int i;

    for(i = s.length() - 1; i >= 0; i--)
    {
        if (s.charAt(i) == '+' || s.charAt(i) == '-')
            break;
        else if (s.charAt(i) == '*' || s.charAt(i) == '/')
            break;
    }

    r1 = s.substring(0, i);
    r2 = s.substring(i + 1, s.length());

    //Base case
    if(!r1.contains("+") && !r1.contains("-") && !r1.contains("*") && !r1.contains("/") &&
       !r2.contains("+") && !r2.contains("-") && !r2.contains("*") && !r2.contains("/"))
            return Integer.parseInt(s);

    switch (s.charAt(i))
    {
        case '+':
            result =  evaluateE(r1) + evaluateE(r2);
            break;
        case '-':
            result = evaluateE(r1) - evaluateE(r2);
            break;
        case '*':
            result = evaluateE(r1) * evaluateE(r2);
            break;
        case '/':
            if (Integer.parseInt(r2) == 0)  //if denominator is zero
            {
                System.out.println("Invalid divisor");
                System.exit(1);
            }
            else
                result = evaluateE(r1) / evaluateE(r2);
                break;
    }
    return result;

}

Answer 1

您正在检查运算符，如果它们包含运算符，即对于 r1+r2 您检查，如果 r1 或 r2 包含一个运算符(operator)。如果您的 String 恰好包含 1 个运算符，则 r1 和 r2 都不包含运算符，因此 Integer.parse(s) 将被执行。由于 s = r1 + operator + r2 包含运算符，Integer.parse 将引发错误。

要解决此问题，请在该方法中执行任何其他操作之前检查基本情况:

int evaluateE(String s) {
    //Base case
    if (!s.contains("+") && !s.contains("-") && !s.contains("*") && !s.contains("/")) {
        return Integer.parseInt(s);
    }

    int i;

    for (i = s.length() - 1; i >= 0; i--) {
        if (s.charAt(i) == '+' || s.charAt(i) == '-') {
            break;
        } else if (s.charAt(i) == '*' || s.charAt(i) == '/') {
            break;
        }
    }

    String r1 = s.substring(0, i);
    String r2 = s.substring(i + 1, s.length());

    int result = 0;

    switch (s.charAt(i)) {
        case '+':
            result = evaluateE(r1) + evaluateE(r2);
            break;
        case '-':
            result = evaluateE(r1) - evaluateE(r2);
            break;
        case '*':
            result = evaluateE(r1) * evaluateE(r2);
            break;
        case '/':
            int right = evaluateE(r2);
            if (right == 0) //if denominator is zero
            {
                System.out.println("Invalid divisor");
                System.exit(1);
            } else {
                result = evaluateE(r1) / right;
            }
            break;
    }
    return result;

}

然而，这忽略了运算符的优先级，即它从左到右计算表达式。例如。 10-3*6/9+4 被解释为 (((10-3)*6)/9)+4。

如果要考虑运算符优先级，则必须忽略 * 或 /，如果有 + 或 - 在字符串中。这将需要您修改 for 循环:

    // search for '+' and '-' first
    for (i = s.length() - 1; i >= 0; i--) {
        if (s.charAt(i) == '+' || s.charAt(i) == '-') {
            break;
        }
    }
    if (i < 0) {
        // if '+' and '-' were not found, search for '*' and '/'
        for (i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '*' || s.charAt(i) == '/') {
                break;
            }
        }
    }