¿Hay alguna forma de interpretar la notación polaca inversa en notación matemática "normal" cuando se utiliza C++ o C#? Trabajo para una empresa de ingeniería, por lo que usan RPN de vez en cuando y necesitamos una forma de convertirlo. ¿Alguna sugerencia?Conversión de notación polaca inversa
Sí. Piensa en cómo funciona una calculadora RPN. Ahora, en lugar de calcular el valor, en su lugar, agrega la operación al árbol. Entonces, por ejemplo, 2 3 4 + *, cuando llegas al +, entonces en lugar de poner 7 en la pila, pones (+ 3 4) en la pila. Y de manera similar cuando llegue al * (su pila se verá como 2 (+ 3 4) * en ese momento), se convierte en (* 2 (+ 3 4)).
Esta es la notación de prefijo, que luego debe convertir a infijo. Recorre el árbol de izquierda a derecha, profundidad primero. Para cada "nivel interno", si la precedencia del operador es menor, deberá colocar la operación entre paréntesis. Aquí, entonces, dirá, 2 * (3 + 4), porque el + tiene precedencia menor que *.
Espero que esto ayude!
Editar: Hay una sutileza (aparte de no considerar las operaciones unarias en lo anterior): asumí que los operadores asociativos de la izquierda. Para asociaciones de la derecha (por ejemplo, **), se obtienen resultados diferentes para 2 3 4 ** ** ⇒ (** 2 (** 3 4)) versus 2 3 ** 4 ** ⇒ (** (** 2 3) 4).
Al reconstruir Infix desde el árbol, ambos casos muestran que la precedencia no requiere el horquillado, pero en realidad este último caso debe estar entre corchetes ((2 ** 3) ** 4). Por lo tanto, para los operadores asociativos de derecha, la rama de la izquierda necesita tener una precedencia mayor (en lugar de mayor o igual) para evitar el horquillado.
Además, otras consideraciones son que necesita soportes para la rama de la derecha de los operadores - y también.
C# no tiene soporte incorporado para analizar la notación polaca inversa (RPN). Tendrá que escribir su propio analizador, o encontrar uno en línea.
Hay docenas de tutoriales para convertir la forma de postfijo (RPN) en infijo (ecuación algebraica). Eche un vistazo al this, tal vez lo encuentre útil y puede intentar 'realizar ingeniería inversa' para convertir expresiones de postfijo a infijo, teniendo en cuenta que puede haber múltiples notaciones de infijo para un postfijo dado. Hay muy pocos ejemplos útiles que realmente analicen la conversión de postfix a infijo. Aquí hay una entrada de dos partes que encontré muy útil. También tiene algunos pseudo código:
El enlace habla sobre cómo convertir infix a postfix, no al revés .... –
He actualizado mi respuesta. Si bien no pude encontrar una solución exacta, he agregado referencias que deberían ayudar a formular una. – Abbas
El algoritmo de yarda de derivación se utiliza para convertir Infix (es decir, algebraico) en RPN. Esto es lo opuesto a lo que quieres.
¿Me puede dar un ejemplo de su entrada RPN? Soy un usuario/programador veterano de HP calculadora. Supongo que tiene una pila que contiene todas las entradas & operadores. Supongo que necesita reconstruir el árbol de expresiones y luego recorrer el árbol para generar el formulario de infijo.
Sí, crear un árbol de expresiones es exactamente el camino a seguir. :-) La forma en que lo hice fue convertir al prefijo primero, pero tal vez haya métodos directos a infijos disponibles. –
Un enfoque es tomar el ejemplo del segundo capítulo de dragon book que explica cómo escribir un analizador para convertir de notación infijo a postfijo e invertirlo.
Si tiene algún texto de origen (cadena/s) que usted está buscando convertir de RPN (notación de sufijo) para "notación normal" (infija), esto es ciertamente posible (y probablemente no muy difícil).
RPN fue diseñado para máquinas basadas en apilamiento, ya que la forma en que se representó la operación ("2 + 3" -> "2 3 +") encajaba cómo se ejecutaba realmente en el hardware (presione "2" en la pila , presione "3" en la pila, saque dos argumentos de la pila y agréguelos, vuelva a colocarlos en la pila).
Básicamente, desea crear un árbol de sintaxis a partir de su RPN haciendo las 2 expresiones que desea operar en "nodos hoja" y la operación misma, que viene después, el "nodo padre". Esto probablemente se hará al buscar recursivamente su cadena de entrada (probablemente quiera asegurarse de que las subexpresiones estén entre paréntesis para mayor claridad, si es que aún no lo están).
Una vez que tenga ese árbol de sintaxis, puede generar prefijos, infijos o notación de postfijo simplemente haciendo un recorrido de pre-pedido, post-pedido o en orden de ese árbol (de nuevo, entre paréntesis su resultado para mayor claridad si deseado).
Alguna más información se puede encontrar here.
Si usted puede leer rubí, encontrará algunas buenas soluciones a este here
que acabo de escribir una versión en Java, es here y uno en Objective-C, sobre here.
Algoritmo posible: Dado que tiene una pila con la entrada en rpn como el usuario la ingresaría, p. 8, 9, *. Usted itera sobre la matriz de principio a fin y siempre elimina el elemento actual. Este elemento lo evalúas Si es un operando, lo agrega a una pila de resultados. Cuando es un operador, extrae la pila de resultados dos veces (para operaciones binarias) para los operandos y escribe la cadena de resultados en la pila de resultados.
Con el ejemplo de entrada de "8, 9, +, 2, *" recibe estos valores en la resultstack (corchetes para indicar elementos individuales):
paso 1: [8 ]
paso 2: [8], [9]
paso 3: [(8 + 9)]
paso 4: [(8 + 9)], [2]
paso 5: [(8 + 9) * 2]
Cuando la pila de entrada está vacío, que son terminado y el único elemento resultStack es tu resultado. (Sin embargo, tenga en cuenta que la entrada puede contener entradas múltiples o que no tienen sentido, como una operación principal: "+ 2 3 /".)
Las implementaciones en los enlaces deliberadamente no usan ningún tipo de auto-creación para p.ej operadores o operandos, ni se aplica, p. patrón compuesto. Simplemente es limpio y simple, por lo que puede ser fácilmente entendido y trasladado a cualquier otro idioma.
Moverlo a C# es sencillo.
¡Gracias por la ayuda! Apreciado enormemente. – Iwasakabukiman