Java RPN (notación polaca inversa) infija a Postfix

Question

Estoy bastante seguro de que las pilas se utilizan para la construcción de PRN y '(' se ignoran, pero no parece ser el caso, por ejemplo:.

• de entrada 1: 52+ (1 + 2) * 4-3
• de entrada 2: 52 + ((1 + 2) * 4) -3
• de entrada 3: (52 + 1 +2) * 4-3

La entrada 1 y la salida 2 deben ser iguales, y la entrada 1 y la entrada 3 deben ser diferentes. salida

• 1: 52 1 2 + 4 3 - * +
• salida 2: 52 1 2 + 4 * 3 - +
• salida 3: 52 1 2 + 4 3 - * +

    public static String Infix2(String input) { 
     char[] in = input.toCharArray(); 
     Stack<Character> stack = new Stack<Character>(); 
     StringBuilder out = new StringBuilder(); 

     for (int i = 0; i < in.length; i++) 
      switch (in[i]) { 
      case '+': 
      case '*': 
      case '-': 
       out.append(' '); 
       stack.push(in[i]); 
       break; 
      case ' ': 
      case '(': 
       break; 
      case ')': 
       out.append(' '); 
       out.append(stack.pop()); 
       break; 
      default: 
       out.append(in[i]); 
       break; 
      } 

     while (!stack.isEmpty()) { 
      out.append(' '); 
      out.append(stack.pop()); 
     } 

     return out.toString(); 
    } 

Suponiendo que quiero entrada 1 y 3 también para trabajar, qué enfoque se debe usar?

edit: Después de los cambios '+', '-', '*' y '/' funcionaron para las entradas dadas.

public static String Infix2(String input) { 
    if (input == null) 
     return ""; 
    char[] in = input.toCharArray(); 
    Stack<Character> stack = new Stack<Character>(); 
    StringBuilder out = new StringBuilder(); 

    for (int i = 0; i < in.length; i++) 
     switch (in[i]) { 
     case '+': 
     case '-': 
      while (!stack.empty() 
        && (stack.peek() == '*' || stack.peek() == '/')) 
       out.append(' ').append(stack.pop()); 
     case '*': 
     case '/': 
      out.append(' '); 
     case '(': 
      stack.push(in[i]); 
     case ' ': 
      break; 
     case ')': 
      while (!stack.empty() && stack.peek() != '(') 
       out.append(' ').append(stack.pop()); 
      if (!stack.empty()) 
       stack.pop(); 
      break; 
     default: 
      out.append(in[i]); 
      break; 
     } 

    while (!stack.isEmpty()) 
     out.append(' ').append(stack.pop()); 

    return out.toString(); 
} 

Answer 1

El algoritmo es bastante simple (y here is a good explanation). Cada operación tiene un peso vinculante, siendo + y - el más bajo. Hay dos reglas:

• imprimir números que inmediatamente
• nunca se pusieron un elemento más ligero en un elemento más pesado
• paréntesis izquierdos van a la pila
• paréntesis derecho sobresalen de la pila hasta que llegue a la izquierda paréntesis y, a continuación, eliminar los paréntesis izquierdo

le haga el primer ejemplo, 52+ (1 + 2) * 4-3, aquí está la pila:

52+   => + 
52+(  => + (
52+(1+  => + (+ 
52+(1+2)  => +  //right parentheses popped + 
52+(1+2)*4 => + * 
52+(1+2)*4-3 => + -  //can't put - on top of *, so pop off * 
... and then pop the stack until it's empty. 

Reemplazando su bucle de interruptor con lo siguiente (el análogo más cercano al que tenía) dará las respuestas correctas para sus tres ejemplos. En un analizador real le daría un peso a cada operador y generalizaría el mecanismo pop.

for (int i = 0; i < in.length; i++) 
     switch (in[i]) { 
     case '+': 
     case '-': 
      while (!stack.empty() && (stack.peek() == '*' || stack.peek() == '/')) { 
       out.append(' '); 
       out.append(stack.pop()); 
      } 
      out.append(' '); 
      stack.push(in[i]); 
      break; 
     case '*': 
     case '/': 
      out.append(' '); 
      stack.push(in[i]); 
      break; 
     case '(': 
      stack.push(in[i]); 
      break; 
     case ')': 
      while (!stack.empty() && stack.peek() != '(') { 
       out.append(' '); 
       out.append(stack.pop()); 
      } 
      stack.pop(); 
      break; 
     default: 
      out.append(in[i]); 
      break; 
     } 

Answer 2

No

una respuesta exacta a la pregunta específica, sino algo que recomiendo para el desarrollo de este tipo de algoritmos: echar un vistazo a prueba impulsado devlopment (TDD). En resumen: escriba un par de pruebas unitarias, por ejemplo, con JUnit, para el método infix2, donde alimenta el método con patrones de prueba (expresiones) y prueba, si infix2 produce el resultado correcto.

Start con los fáciles, como

assertequals("1", "1"); // positive number 
assertequals("-1", "-1"); // negative number 
assertequals("1+1", "1 1 +"); // simple addition 
assertequals(" 1 + 1 ", "1 1 +"); // simple addition with whitechars 
assertequals(" 1 + +1 ", "1 -1 +"); // simple addition with pos. number & whitechars 
assertequals(" 1 + -1 ", "1 -1 +"); // simple addition with neg. number & whitechars 
assertequals("(1+1)", "1 1 +"); // simple addition with brackets 

y no se olvide expresiones ilegales como

String[] illegalExpressions = {null, "", " ", "1 +", "1 + 1)"}; 

Los casos de prueba para que los ejemplos deben ser

assertequals("52+(1+2)*4-3", "52 1 2 + 4 * 3 -"); 
assertequals("52+((1+2)*4)-3", "52 1 2 + 4 * 3 -"); 
assertequals("(52+1+2)*4-3", "52 1 + 2 + 4 * 3 -");