Вычислить арифметическое выражение рекурсивно

Question

Мне нужна помощь при оценке арифметического выражения (INFIX) через рекурсию. Я сделал дерево, просматривая справа налево (+, - сначала, *,/second). Ошибка:

Для ввода строки: "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 оператор. Если ваш 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.

Если вы хотите, чтобы оператор приоритет в сведенью, вы должны игнорировать * или /, если есть + или - в строке. Это потребует изменения вашего цикла:

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

Answer 2

Не понятно, почему вы возвращаете Integer.parseInt(s), когда, по всей вероятности s будет иметь оператор (+, -, * или /). Таким образом, по существу, вы пытаетесь преобразовать "2+3" в int, что является причиной ошибки.