función de evaluación de escritura cadena

Question

estoy tratando de escribir una función de evaluación de cuerdas es decir

evaluate("4 + 1") ; // returns 5 
evaluate("4 + 1 + 3") ; // returns 8 
evaluate("4 + 1 * 3") ; // returns 7 (not 15) 

The operators are + -/and * 

Mi inicial, aunque era utilizar expresiones regulares para recoger los operadores y dígitos, ya que pueden ser emparejados. Y que después de encontrar esa información, de alguna manera encuentre una manera de priorizar los operadores /* ove -+.

Así es como empecé:

static String regex = "([\\+\\*-/])+"; 
static String digitRegex = "(\\d)+"; 

public static void main(String[] args) { 
    System.out.println(getOperators("4 + 1 * 3")); 
} 

public static List<String> getOperators(String input) { 
    Pattern p = Pattern.compile(regex); 
    Matcher matcher = p.matcher(input); 

    List<String> operatorList = new ArrayList<String>(); 

    int count = 0; 
    while (matcher.find()){ 
     if (matcher.group(count) != null && matcher.group(count).trim().length() > 0) { 
     operatorList.add(matcher.group(count)); 
     count++; 
     } 
    } 

    return operatorList; 
} 

Ahora puedo escribir otro método para extraer los dígitos utilizando la misma lógica.

public static List<Integer> getDigits(String input) { 
     Pattern p = Pattern.compile(digitRegex); 
     Matcher matcher = p.matcher(input); 

     List<Integer> digitList = new ArrayList<Integer>(); 

     int count = 0; 
     while (matcher.find()) { 
      if (matcher.group(count) != null && matcher.group(count).trim().length() > 0) { 
       digitList.add(Integer.valueOf(matcher.group(count))); 
       count++; 
      } 
     } 

     return digitList; 
    } 

Ahora es la parte donde estoy atascado. # 1 Este método anterior falla en el tercer ejemplo:

evaluate("4 + 1 * 3") ; // returns 7 (not 15) 

Y esto # 2 Incluso si trato ejemplos anteriores, no puedo imaginar que encontrar la manera de ponerlos en el orden correcto.

Estoy en el camino correcto, ¿Alguien tiene algún consejo útil por favor comparta?

Answer 1

Escribí aquí algo ... digamos que rápido & sucio es un eufemismo ...
Por supuesto, NO DEBE usarlo "tal cual". Se necesita "arreglando" - la lectura de los números/aritmética de operaciones debe hacerse utilizando StringTokenizer - pero voy a dejar los tecnicismos a ti;)

public class NewClass { 

    public static int evaluate(String str){ 
     if("".equals(str)){ 
      return 0; 
     } 
     else if(str.length() == 1){ 
      return Integer.valueOf(str); 
     } 
     else{ 
      String _a = String.valueOf(str.charAt(0)); 
      String _b = String.valueOf(str.charAt(1)); 
      if("+".equals(_b) || "-".equals(_b)){ 
       if("+".equals(_b)){ 
        return Integer.valueOf(_a) + evaluate(str.substring(2)); 
       } 
       else{// "-" 
        return Integer.valueOf(_a) - evaluate(str.substring(2)); 
       } 
      } 
      else{// "*" or "/" 
       boolean isMulti = ("*".equals(_b)); 
       String _c = String.valueOf(str.charAt(2));     
       Integer tmp = 0; 
       if(isMulti){ 
        tmp = Integer.valueOf(_a) * Integer.valueOf(_c); 
       } 
       else{ 
        tmp = Integer.valueOf(_a)/Integer.valueOf(_c); 
       } 
       String new_str = String.valueOf(tmp) + str.substring(3);     
       return evaluate(new_str); 
      } 
     } 
    } 

    public static void main(String[] args){   
     String e = "4+1*3"; 
     int t = evaluate(e); 
     System.out.println(e + " = "+t); 
    } 

} 

Answer 2

Quiere operator precedence parser. Este es un analizador sintáctico basado en tablas muy común, diseñado para hacer exactamente lo que usted desea. Básicamente, se compara el operador que se está escaneando con el que se encuentra en la parte superior de una pila, y se elige reducir la pila (es decir, hacer las operaciones matemáticas y volver a insertar el resultado en la pila) o presionar al operador.

Como una ventaja adicional, los OPP son fáciles y divertidos de escribir. Puede agregar soporte para paréntesis, etc. con un pequeño esfuerzo adicional.

editar - Acabo de leer el artículo de la wiki. Es terrible.

Encuentra otros ejemplos de este tipo de analizador.

Edición 2 -

This one shows a sample in c. Note the table.

This one is pretty good.

Y recuerde, usted está apoyando un pequeño número de operadores, por lo que no se dejan intimidar. además, es todo lo mismo una vez que implemente una tabla.