Codigo de la notacion polaca inversa

Discussion around the algorithms: the most powerful tool of the contest programmer. This is the place to ask about the algorithms you have heard mention, or to share with the community your knowledge about them.
Forum rules
Remember that you may not post the AC solution to any of the problems on the COJ. Only code pertaining to a general algorithm will be allowed.
Posting AC solutions will be penalized.
Post Reply
User avatar
isaac
Posts: 83
Joined: 3 years ago
Gender: None specified

Codigo de la notacion polaca inversa

Post by isaac » 3 years ago

Este es el codigo en C++ del algoritmo conocido como RPN (Reversed Polish Notation) o Notacion Polaca Inversa. Es un poco extenso pero muy facil de entender y con la idea basica descrita en el tema anterior, es rapido de implementar. Espero que les sirva para parsear operaciones. OBSERVACION: Este codigo se puede refinar para que detecte otros errores o para que parsee funciones previamente definidas.

Code: Select all

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<string>
#include<stack>

using namespace std;

stack<char> op;
stack<int> res;

char line[1001];

/// Convertir un rango de char* a entero
int convert(int a, int b) {

    int n = 0;

    for(int i=a; i<b; i++) {
        n *= 10;
        n += line[i] - '0';
    }

    return n;

}

bool isop(char c) {
    return c=='+' || c=='-' || c=='*' || c=='/' || c=='^' || c=='%';
}

/// Precedencia de los operadores
int prec(char s) {
    if(s=='^')
        return 3;
    if(s=='*' || s=='/' || s=='%')
        return 2;
    if(s=='+' || s=='-')
        return 1;
    return 0;
}

int sq(int x) {
    return x*x;
}

int pot(int b, int e) {
    if(e==0)
        return 1;
    if(e==1)
        return b;
    if(e%2==0)
        return sq(pot(b, e/2));
    return b * pot(b, e-1);
}

void solve(char o) {

    /// Extraemos los dos valores y
    /// guardamos el resultado en dependencia
    /// del operador.
    int b, a;

    b = res.top();
    res.pop();

    a = res.top();
    res.pop();

    if(o == '+')
        res.push(a + b);
    else if(o == '-')
        res.push(a - b);
    else if(o == '*')
        res.push(a * b);
    else if(o == '/') {
        if(b == 0) {
            printf("ERROR. DIVISION POR CERO\n");
            exit(0);
        }
        res.push(a / b);
    } else if(o == '^')
        res.push(pot(a, b));
    else if(o == '%') {
        if(b == 0) {
            printf("ERROR. MODULO INDEFINIDO\n");
            exit(0);
        }
        res.push(a % b);
    }

    /// Eliminamos el operador de la cola.
    op.pop();

}

void decode() {

    int len = strlen(line);

    /// Agregamos el parentesis al final
    line[len++] = ')';
    line[len] = '\0';

    /// Guardamos el ( en op
    op.push('(');

    /// Recorremos la expresion analizando cada caso
    /// por separado
    for(int i=0; i<len; i++)
        if(line[i] == ' ')
            continue;
        else if(line[i]=='(')
            op.push('(');
        else if(line[i]==')') {

            while(1) {
                if(op.top()=='(') {
                    op.pop();
                    break;
                }
                solve(op.top());
            }

        } else if(isdigit(line[i])) {

            /// Insertamos un numero

            int j=i+1;

            for(; j<len; j++)
                if(!isdigit(line[j]))
                    break;

            res.push(convert(i, j));

            i = j-1;

        } else if(isop(line[i])) {

            /// Insertamos un operador

            while(prec(op.top()) >= prec(line[i]))
                solve(op.top());

            op.push(line[i]);

        }

    /// Mostramos el resultado
    printf("%d\n", res.top());

    res.pop();

}

int main() {

    /// Leer la expresion
    gets(line);

    /// Interpretarla y dar el resultado
    decode();

    return 0;

}




Post Reply

Return to “Algorithms”