Foro de elhacker.net

3 4 + 7 * 9 10 5 6 + * - - 

3 4 + 7 * 9 10 5 6 + * - - 

3

4 + 7 * 9 10 5 6 + * - - 

3 4

+ 7 * 9 10 5 6 + * - - 

7

7 * 9 10 5 6 + * - - 

7 7

* 9 10 5 6 + * - - 

49

9 10 5 6 + * - - 

49 9

10 5 6 + * - - 

49 9 10

5 6 + * - - 

49 9 10 5

6 + * - - 

49 9 10 5 6

+ * - - 

49 9 10 11

* - - 

49 9 110

- - 

49 101

- 

52

INICIO
    posicionActual := 0
    PEDIR expresion
    PARA i := 0 HASTA expresion.longitud - 1 HACER
        SEGUN expresion[i] HACER
            numero:
                numeros[posicionActual++] = expresion[i]
            +:
                numeros[posicionActual - 2] := numeros[posicionActual - 2] + numeros[posicionActual - 1]
                posicionActual := posicionActual - 2
            *:
                numeros[posicionActual - 2] := numeros[posicionActual - 2] + numeros[posicionActual - 1]
                posicionActual := posicionActual - 2

            //...igual para el resto de operadores

        FIN SEGUN
    FIN PARA

    MOSTRAR numeros[0]
FIN 

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

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

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

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

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

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

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