Ayuda

[Serapis]

No entiendo por qué (los profesores) se empeñan en intentar profundidar en teoría de compiladores en el primer año, cuando el alumno, todavía está demasiado verde... Una introducción estaría bien, pero sin profundizar.

La notación polaca inversa, tiene bastante trabajo incluso en su forma más simple...
Al lío...

La notación que usamos 'humanamente' se llama infija, esto es el operador aparece en medio de los operandos...
Siguiendo la idea, es fácil entender que el operador puede aparecer también al inicio o al final de ambos operandos, lo que da nombre a la notación prefija (o polaca) y la postfija (o polaca inversa).

Se usa bastante en los compiladores, porque simplifica las expresiones de cara a poder usarlos de forma cómoda y rápida desde la pila, aunque no siempre resulta eficiente.
...Tu caso (crear una calculadora que opere así), entra en el caso de los intérpretes, no será compilado, pero todavía puede resultar útil...

La forma de hacerlo eficiente, es diseñado a bajo nivel, no delegando a funciones, la ventaja es que puedes acomodar el algoritmo al completo según tus necesidade,s lo cual es siempre más eficiente que tener que diseñar y luego adaptar tu algoritmo, a lo que te dejen hacer las funciones que disponga tu lenguaje...

en esta implementación como tiene más propósito ilustrativo de cara a aprender, vamos a considerar que cada token se compone de solo 1 carácter (para no perdernos en detalles más alejados), una vez se comprenda y domine el tema, puede ampliarse, para reconocer números incluso en  diferentes bases numéricas...

Así de entrada hay que definir alguna enumeración y algún array, para mantener dicha eficiencia arriba...

Código [Seleccionar] Expandir


Enumeracion AtributosChar
   ATRIBCHAR_ERROR = -1                        // cualquier otro carácter (no considerado a continuación)...
   ATRIBCHAR_IGNORA = 0                        // espacios
   
   ATRIBCHAR_OPERADOR_PRECEDENCIA_1 = 1        //  */
   ATRIBCHAR_OPERADOR_PRECEDENCIA_2 = 2        //  +-
   ATRIBCHAR_OPERADOR_MAX = 2                  // Valor mayor de la precedencia (no precedencia mayor, pués están en orden inverso).
   // Este valor se consigna desde NextToken, pero no se asigna en la tabla.
   ATRIBCHAR_OPERADOR_UNARIO = 3               // +- (pero cuando va delante de otro operador o de un paréntesis de apertura,o al comienzo.
   
   ATRIBCHAR_DELIMITADOR_ABRE = 5              // (
   ATRIBCHAR_DELIMITADOR_CIERRA = 6            // )
   ATRIBCHAR_OPERANDO = 7                      // [±] (A-Z|a-z|0-9) ...aunque solo operamos con dígitos, porque luego quieres calcular resultados...
fin Enumeracion

Estructura RegistroTblSimb
   string Valor                      
   AtributosChar Token
   //real Calculo                    
End Type

La enumeración la usaremos para identificar cada tipo de carácter derivándolo a nuestras necesidades...
La estructura, dispuesta en un array hará las veces de la tabla de símbolos que será usada  para almacenar los tokens cuando sean analizados.

Ahora procede crear los arrays estáticos con sus valores...
Esto típicamente se hace en el Main...

Primero declaramos los arrays que vamos a usar como apoyo...

Código [Seleccionar] Expandir


Array de Atributoschar s_Tabla(0 a 255)
array de RegistroTblSimb s_TblSimb(0 a 79)      
//80 parece un número suficiente para probar la calculadora, será raro que en una calculadora sencilla haya expresiones con más de 80 tokens...
//pero vamos si se espera que suceda, basta ampliar el número a lo que se considere adecuado.

// y rellenamos ya el array de atributos de los caracteres...
funcion Main
   llamada a CrearTabla
fin funcion

// se deja en una función aparte para mantener despejado 'main', y para centrar la función a lo que dice su nombre y hace.
funcion CrearTabla
   int k
   
   // Todos se marcan como error, luego los válidos con su valor adecuado...
   Bucle para k desde 0 hasta 255
       s_Tabla(k) = ATRIBCHAR_ERROR                // todos excepto los que siguen.              
   Siguiente

   // Digitos:
   Bucle para k desde 48 hasta 57
       s_Tabla(k) = ATRIBCHAR_OPERANDO             // 0-9
   siguiente
   
   // Caracteres:
   Bucle para k desde 65 hasta 90
       s_Tabla(k) = ATRIBCHAR_OPERANDO             // A-Z
       s_Tabla(k + 32) = ATRIBCHAR_OPERANDO        // a-z
   siguiente
   
   // Separador:
   s_Tabla(32) = ATRIBCHAR_IGNORA                  // el espacio (también se podría poner l espacio duro)

   // Delimitadores:
   s_Tabla(40) = ATRIBCHAR_DELIMITADOR_ABRE        //  (
   s_Tabla(41) = ATRIBCHAR_DELIMITADOR_CIERRA      //  )
   
   // Operadores:
   s_Tabla(42) = ATRIBCHAR_OPERADOR_PRECEDENCIA_1  //  *
   s_Tabla(43) = ATRIBCHAR_OPERADOR_PRECEDENCIA_2  //  +
   s_Tabla(45) = ATRIBCHAR_OPERADOR_PRECEDENCIA_2  //  -  
   s_Tabla(47) = ATRIBCHAR_OPERADOR_PRECEDENCIA_1  //  /
fin funcion


Nos bastan esos 4 operadores y los paréntesis, para ejemplificar...
Ahora lo siguiente será una simple función que será el analizador léxico...
Su función es pedir tokens que se extraen d ela entrada y los guarda en la tabla de símbolos. es una función muy simplificada dado que para el caso, los tokens se limitan a:
Operando, Operador, ParentesisAbre, ParentesisCierra

Código [Seleccionar] Expandir


// El scan léxico: Debe reconocer cada tipo de token válido.
//  que almacena en el array s_TblSimb
// Devuelve la cantidad de tokens hallados, si devuelve 0, es que hubo algún problema:
//   1 - El string de entrada estaba vacío: ""
//   2 - Hay caracteres 'raros' no considerados en nuestra tabla: 5+3-6+?*@   (? y @ no sons ímbolos admitidos en 'nuestra gramática').
//   3 - La expresion está mal formada (error sintáctico):  5****3;   4+345;  5+(((3-2)
int = Funcion ScanLex(string Expr )
   int k, n
   string st
   AtributosChar tk  
   
   // n = 1 ciertos lenguajes considera el primer carácter de un string, como el 1, no el 0, descomentar en tal caso...
   Hacer mientras (n <= Expr.Size)
       st = NextToken(Expr, n, tk)

       Si (tk = ATRIBCHAR_ERROR)
           devolver 0
       Osi (tk = ATRIBCHAR_OPERADOR_UNARIO)
           // Un operador unario solo afecta a un operando, simulamos que el otro es 0
           // y lo encerramos entre paréntesis, para forzar la precedencia dentro.
           // ejemplo: 5*-1 = -5  ó -1*5 = -5   También si se usa el signo +   5*+7
           // queda como si fuera: 5*(0-1)   (0-1)*5    5*(0+7)
           // la misma técnica vale para otros operadores unarios como not(x), cos(x), Abs(x), etc...  
           s_TblSimb(k).Valor = "("
           s_TblSimb(k).Token = ATRIBCHAR_DELIMITADOR_ABRE
           k = (k + 1)
           s_TblSimb(k).Valor = "0"
           s_TblSimb(k).Token = ATRIBCHAR_OPERANDO
           k = (k + 1)
           s_TblSimb(k).Valor = st
           s_TblSimb(k).Token = ATRIBCHAR_OPERADOR_PRECEDENCIA_2
           k = (k + 1)
           // y ahora pedimos el operando suelto, para luego cerrar el paréntesis, antes de seguir...
           st = NextToken(Expr, n, tk)
           
           s_TblSimb(k).Valor = st
           s_TblSimb(k).Token = tk
           k = (k + 1)
           s_TblSimb(k).Valor = ")"
           s_TblSimb(k).Token = ATRIBCHAR_DELIMITADOR_CIERRA
       YSiNo
           // introduccir los datos del token en la tabla de símbolos.
           s_TblSimb(k).Valor = st
           s_TblSimb(k).Token = tk
       Fin si

       k = (k + 1)
   Siguiente
   
   devolver k
fin Funcion


Ahor aprocede poner como sería la función para obtener el siguiente token... es también muy simple, ya que de entrada cada token ocupa un único carácter... y tenemos pocos tokens distintos.

Código [Seleccionar] Expandir


// NOTA: Se considera token de 1 solo carácter
//    operando:     [±] A-Z|a-z|0-9
//    operador:     *|/|+|-
//    parentesis:    (|)
//  Para algo más exahustivo, habría que reconocer:
//    - identificador y número
//    - operadores de 1 o más símbolos (como en '>=')
// OJO: No se verifica si se alcanza el límite de la expresión,
//   lo cual puede suceder con expresiones mal formadas
//   (con caracteres no esperados a la derecha del último caracter válido).
// Los 3 parámetros son pasados por referencia...
string = funcion NextToken(string Expr, int Index, AtributosChar tkUltimo)
   string s
   AtributosChar ac
   
   Hacer
       s = Expr.Substring(Index, 1)   // tomamos el carácter en la posición index
       ac = s_Tabla(s.toByte)    // Evaluamos de qué tipo es el caracter.
       // en ciertos lenguajes caracter y byte se usan indistintamente, en otros marca error,
       // luego exige una conversión a bytes implícita, explícita, por casting o por coerción...
       Index += 1
   repetir mientras (ac = ATRIBCHAR_IGNORA) // saltar espacios
    // cualquier otro carácter no aceptado será detectado como error, tras la devolución.
   
   // Detectar si es un operador unario... Esto se sabe si hay otro operador delante.
   //  casos: *+2,  /-2,  +-4,  -+4,  (-1, +1    (total: 6 casos distintos)
   // es decir aparece un ± detrás de otro operador, de un paréntesis de apertura, o al comienzo de expresión.
   Si (ac = ATRIBCHAR_OPERADOR_PRECEDENCIA_2)  // solo signos +- que son los posibles unarios en esta implementación.
       Si ((tkUltimo <= ATRIBCHAR_DELIMITADOR_ABRE)  // es posible hacerlo así de simple,
            // porque se ha estudiado el orden de los tipos en la enumeración. Así acepta los 6 casos.
           ac = ATRIBCHAR_OPERADOR_UNARIO  
           //marcamos temporalmente como un token de operador unario,
       Fin si
   fin Si
   
   tkUltimo = ac
   Devolver s
Fin Funcion


Ahora toca hacer la función que implementa el algoritmo de la notación polaca inversa.
Para qien tenga bien a fondo conocimeinto en teoría de compiladores, básicamente puede lograr lo mismo mediante la técnica de 'compilación recursiva descendente'... que eso sería una analizado sintáctico...
Pero dado la sencillez d ela gramática usada, aquí se deja constancia de una sencilla implementación del algoritmo de Dijkstra (de Edsger Dijkstra, no nuestro forista: Dijsktra)

Como bien te han dicho una pila puede implementarse con un array, lo mismo que una cola, aquí incluso en un string... fíjate al caso que la diferencia entre pila y cola así usados será que la pila añade en orden inverso:
// cola: "A      ";  "An     "; "Ant    "; "Anti   "; "Antig  "; "Antigu "; "Antiguo"
// pila: "      A"; "     nA"; "    tnA"; "   itnA"; "  gitnA"; " ugitnA";  "ougitnA"

Código [Seleccionar] Expandir


// Ini y fin, son el punto de la tabla de símbolos entre los que queramos analizar.
// Si siempre va a ser desde el comienzo, ini puede dejar de ser un parámetro para ser una variable interna de la función con valor 0.
// Fin en cualquier caso, indica el final, o para la situación anterior la cantidad-1 de tokens almacenados durante el análisis léxico.
string = Funcion DijkstraRPN(int Ini, int Fin)
   AtributosChar AtChar As , PrevTkChar         // tipo de token.
   string cola, int ixCola                                // cola de operandos (y operadores) y su puntero.
   string pila, int ixPila                                  // pila de operadores y su puntero
   int IxMax =   (Fin - Ini + 1)
   
   ixPila = (IxMax + 1)
   ixCola = 0  // 1, si el lenguaje considera el primer carácter de un string, como 1.
   // creamos el espacio máximo de cada string, en realidad cola, nunca crece mucho...
   // Si se opera con arrays de chars, incluso mejor, cuando el lenguaje no supone pérdida de eficiencia en conversiones 'tontas' entre char y byte.
   // la reserva de espacio en el string, al giaul que en un array, previene que la modificación de su tamaño exija contruir y copiar el contenido en otro, como sucede con append, etc...
   pila = Espacios(IxMax)
   cola = espacios(IxMax)
   
   Hacer mientras (Ini <= Fin)
       AtChar = s_TblSimb(Ini).Token
       Seleccionar  Caso para AtChar
           Caso ATRIBCHAR_OPERANDO   // accion: añadir a la cola
               cola.Replace(ixCola, 1) = s_TblSimb(Ini).Valor   // remplaza el carácter en la posición indicada.
               ixCola += 1                
           Caso ATRIBCHAR_DELIMITADOR_ABRE  // accion: Añadir a la pila.
               ixPila -= 1
               pila.Replace(ixPila, 1) = s_TblSimb(Ini).Valor
           Caso ATRIBCHAR_DELIMITADOR_CIERRA
               // Accion: mover operadores de la pila a la cola, hasta que
               //   se encuentre el paréntesis de apertura de su mismo anidamiento.
               Hacer mientras (s_Tabla(pila.Substring(ixPila, 1).ToByte) <> ATRIBCHAR_DELIMITADOR_ABRE)
                   cola.Replace(ixCola, 1) = pila.Substring(ixPila, 1)  // mover elemento a la cola
                   ixCola += 1
                   pila.Replace(ixPila, 1) = " "   // eliminar de la pila (basta poner un espacio)
                   ixPila += 1
                   si (ixPila = IxMax) Salir del bucle
               Repetir
               
               pila.replace(ixPila, 1) = " "          // eliminar paréntesis de apertura encontrado.
               ixPila += 1
           Resto de casos // operadores: considerar precedencia.
               // Accion: Mover a la cola, mientras el operador en la pila siendo examinado
               // sea de menor o igual precedencia que el operador actual.
               Si (ixPila <= IxMax)  // es habitual que la pila quede vacía...
                   PrevTkChar = s_Tabla(pila.Substring(ixPila, 1).ToByte)

                   Hacer mientras (PrevTkChar <= AtChar)  // y (PrevTkChar <> ATRIBCHAR_DELIMITADOR_ABRE)), pero el diseño en la enumeración ya considera esto, con la previa condición.
                       cola.Replace(ixCola, 1) = pila.Substring(ixPila, 1)  // mover elemento a la cola
                       ixCola += 1
                       pila.Replace(ixPila, 1) = " " // eliminar de la pila (basta poner un espacio)
                       ixPila += 1
                       si (ixPila > IxMax) Salir del bucle
                       PrevTkChar = s_Tabla(pila.Substring(ixPila, 1).ToByte)
                   Repetir  // el bucle se parece bastante al anterior, pero no llegan a ser iguales...
               Fin si
               
               ixPila -= 1   // la pila crece hacia abajo...
               pila.Replace( ixPila, 1) = s_TblSimb(Ini).Valor
       Fin seleccion de casos
       imprimir cola tabulador pila  // solo para ver como evoluciona...
       Ini += 1
   Repetir
   
   // Pasar contenido restante de la pila a la cola (pero si quedan paréntesis = error).
   //   En realidad, no se espera este error, toda vez que pasó un scan léxico.
   //   Sin embargo se deja por si se decide modificar el algoritmo para aceptar directamente
   // el texto de la expresión como parámetro, e ignorar el scan léxico previo....
   pila = pila.Right(IxMax - ixPila + 1)  // la pila descarta los espacios a la izquierda...
   Si (pila.Contiene( "(")) = FALSE)
       cola.Replace(ixCola) = pila    // copia el contenido de la pila en la cola, a partir de la posición indicada.
       ixCola += pila.Size
       imprimir cola tabulador pila  // solo para ver el resultado final ...
       devolver cola.Left(ixCola - 1)   // devuelve el contenido de la cola, descartando los espacios a su derecha.
   fin si
fin funcion


Y finalmente como lo que se te pide es una calculadora, y no solo la conversión de la notación, pués hale esto completa el intérprete...

Código [Seleccionar] Expandir


// Calcula el valor de una expresión postfija.
//   A - Se supone que es una expresión aritmética, donde todos los operandos son números.
//   B - Si se admite que fueran identificadores, se supone que estos o bien refieren direcciones de memoria o bien su valor se haya en una tabla hash (por ejemplo),
//     luego antes de guardar a la 'pila' se debe dereferenciar el identificador. Por ejemplo:   s_Temp(i) = tHash(identificador)
//     Por eso si el propósito es meramente un ejercicio, es preferible ceñirse al caso 'A', exclusivamente y usar solo dígitos.
// devuelve el valor calclado, como puede tener decimales... el array temporal conviene que así sea...
real = Funcion CalcularRPN(string RPN)
   int k, i, X, Y
   AtributosChar  tk
   string s
   real Temp(0 a 79) // mismo tamaño que dejamos para la tabla de símbolos, adaptar según necesidades..
   // incluso conviene mover este array al nivel del módulo...
   
   bucle para k desde 0 hasta RPN.Size-1   // nuevamente si el lenguaje trata el primer char de la cadena , como 1, ira de 1 a rpn.size
       s = RPN.Substring( k, 1)   // toma el enésimo carácter de la cadena (o array)
       tk = s_Tabla(s.ToByte)
       // Mientras se obtengan operandos se guardan en temp
       // cuando aparece un operador se toma los dos últimos operandos guardados y se opera con ellos
       Si (tk <= ATRIBCHAR_OPERADOR_MAX)
           // sacar dos últimos operandos de la pila
           i -= 2
           X = Temp(i)
           Y = Temp(i + 1)
           
           // calcular y almacenar en la pila.
           Seleccionar Caso para s
               Caso "*"
                   Temp(i) = (X * Y)
               Caso "/"
                   Temp(i) = (X / Y)
               Caso "+"
                   Temp(i) = (X + Y)
               Caso "-"
                   Temp(i) = (X - Y)
           fin seleccion casos
       Ysino // Osi (tk = ATRIBCHAR_OPERANDO)
           //  una expresión RPN (bien formada) solo tiene operandos y operadores.
           // leer y almacenar operandos hasta encontrar un operador...
           Temp(i) = s
       // YSiNo
        //  solo si se espera errores en caso de expresion malformada... activar el 'Osi' del caso anterior y activar este 'YSino'
       Fin Si
       i += 1
   Siguiente
   
   devolver Temp(0)  // i acabará valiendo 1
Fin funcion


Se invocaría como:

Código [Seleccionar] Expandir


funcion Main (string command)
   string rpn
   real valor
   llamada a CrearTabla

   rpn = ExpToRPN(command)
   Si (rpn.size > 0)
       valor = CalcularRPN(rpn)
       imprimir rpn tabulador valor
   Ysino
       Mensaje "el texto de la expresion no es correcto..."
   fin si
fin funcion

string = Function ExpToRPN(string Expr )
   int k As Integer
   
   
   k = ScanLex(Expr)
   si (k = 0) devolver ""
   devolver DijkstraRPN(0, k - 1)
fin Funcion


Y solo resta algún ejemplo:
Expr Infija: 3+6*2
Expr Postfija: 362*+   Valor: 15

Expr Infija: 3+(6*2)
Expr Postfija: 362*+   Valor: 15

Expr Infija: (3+6)*2
Expr Postfija: 36+2*   18

Expr Infija: 9*3+2-5-4*3
Expr Postfija: 93*2+5-43*-  Valor: 12

Expr Infija: 3+4-5*7-(4/2)*3
Expr Postfija: 34+57*-42/3*-   valor: -34

Expr Infija: 5-3*8/2+(5-4/2)+(8+(5*3)-1+(6/3))+5*3
Expr Postfija: 538*2/-542/-+853*+1-63/++53*+   Valor: 35

Y un ejemplo con un operador unario (la misma expresión previa vale)
--------------------------------------------!!-3!!--------- (se ha añadido un signo - delante del 3.
Expr Infija: 5-3*8/2+(5-4/2)+(8+(5*-3)-1+(6/3))+5*3
Expr Postfija: 538*2/-542/-+8503-*+1-63/++53*+  Valor: 5

Y un ejemplo de la evolución, para que al iplementarlo, puedas ir verificando cada cosa:
Expr Infija: 5-3*8/2+(5-4/2)+(8+(5*3)-1+(6/3))+5*3

--- Cola ------------------------------------------------ Pila ---
-------------------------------------------------------------------
5                                                                        
5                                                                        -
53                                                                       -
53                                                                      *-
538                                                                     *-
538*                                                                    /-
538*2                                                                   /-
538*2/-                                                                  +
538*2/-                                                                 (+
538*2/-5                                                                (+
538*2/-5                                                               -(+
538*2/-54                                                              -(+
538*2/-54                                                             /-(+
538*2/-542                                                            /-(+
538*2/-542/-                                                             +
538*2/-542/-+                                                            +
538*2/-542/-+                                                           (+
538*2/-542/-+8                                                          (+
538*2/-542/-+8                                                         +(+
538*2/-542/-+8                                                        (+(+
538*2/-542/-+85                                                       (+(+
538*2/-542/-+85                                                      *(+(+
538*2/-542/-+853                                                     *(+(+
538*2/-542/-+853*                                                      +(+
538*2/-542/-+853*+                                                     -(+
538*2/-542/-+853*+1                                                    -(+
538*2/-542/-+853*+1-                                                   +(+
538*2/-542/-+853*+1-                                                  (+(+
538*2/-542/-+853*+1-6                                                 (+(+
538*2/-542/-+853*+1-6                                                /(+(+
538*2/-542/-+853*+1-63                                               /(+(+
538*2/-542/-+853*+1-63/                                                +(+
538*2/-542/-+853*+1-63/+                                                 +
538*2/-542/-+853*+1-63/++                                                +
538*2/-542/-+853*+1-63/++5                                               +
538*2/-542/-+853*+1-63/++5                                              *+
538*2/-542/-+853*+1-63/++53                                             *+
538*2/-542/-+853*+1-63/++53*+             *+
538*2/-542/-+853*+1-63/++53*+   35

Y bueno, como cada lenguaje tiene sus pecualiaridades, cualquiere que lo implemente en el de su interés, que considere que a veces hay siempre un ± 1 bailando por ahí...

[dijsktra]

Hola!

Basado en el trabajo de  YreX-DwX, ahora creo que si he dado con una respuesta a tu problema. Un interprete de expresiones en notación polaca inversa.

En algún lado de la Wikipedia he leído que una de sus propiedades es que el empleo de paréntesis se hace innecesario con independencia de la precedencia de los operadores. Cada secuencia (correcta) determina una y solo una expresión valida...

Para no repeterlo aquí, lo podéis ver en el correo modificado anterior:

https://foro.elhacker.net/programacion_cc/ayuda-t499837.0.html;msg2206082#msg2206082

[Serapis]

En efecto, el cambio a la notación polaca inversa, es resolver la precedencia de la evaluación de la expresión debida por un lado a los paréntesis, y por otro al resto de  operadores que con distinta precedencia aparecen incluso sin paréntesis, y paliar por tanto el tiempo que se pierde en evaluar la precedencia de la expresión cada vez que deba ser ejecutada. Además simplifica el uso de la pila... pués tiene acciones muy sencillas para efectuar el cálculo.

Tampoco hay que olvidar que el código máquina/ensamblador suele ser notación prefija:
Mov  AX, 5
Add  BH, AH
Jmp  800
...
por lo que los compiladores, usan como código intermedio lo que se llama 'código de 3 direcciones', para finalmente compilar al sistema destino de una forma sencilla y rápida, precisamente teniendo en mente estas cuestiones.