Ir para o conteúdo
thoga31

Reverse Polish Notation

Mensagens Recomendadas

thoga31    611
thoga31

Isto é só mesmo para meter o pessoal a tirar a areia dos pirolitos e movimentar um pouco mais o quadro :D

Anyway, é sempre um desafio com um carácter útil.

Título: Reverse Polish Notation (RPN)

Descrição: Como muitos de vós deveis saber, esta é uma das formas de representar expressões matemáticas para depois serem calculadas. Tem uma estrutura postfix em vez da natural (commumente designada por estrutura infix) e que não tem parêntesis, isto porque, regra geral, estas expressões RPN são geradas a partir das expressões "naturais" com recurso a parsers (coisas bonitas que não nos interessam para aqui), de forma a que a expressão seja facilmente avaliada e calculada directamente da esquerda para a direita. A Wikipédia explica o resto para quem não está familiarizado.

Objectivo: Criar uma função que receba uma expressão RPN e devolva o respectivo resultado. A expressão só pode conter as principais 5 operações (+-*/^) e não mais nenhuma função (logaritmo, por exemplo).

Restrições: Deve haver uma gestão de erros, a qual fica a vosso critério.

Exemplos I/O:

>> 3 4 +
7
>> 5 1 2 + 4 * + 3 -
14
>> 2 5 ^ 1 +
33

Editado por thoga31

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
thoga31    611
thoga31

Isto é um Haskell arranhado, sei que há códigos bem mais elegantes. Mas sendo um principiante, estou satisfeito com o resultado :D

No I/O é que a porca torce o rabo e ao utilizar potências ocorre um erro qualquer que ainda não consegui decifrar. Anyway, a função em si funciona bem (incluindo com potências), pelo que é seguro utilizá-la directamente através do GHCI.

import qualified Data.Char as C

-- Reverse Polish Notation
rpn :: String -> String
rpn expr = let res = calc [] $ words expr 
          in show $ last res
   where
       isOper = (`elem` ["+","-","*","/","^"])
       isNum = all (== True) . map (C.isNumber)

       calc l [] | length l == 1 = l
                 | otherwise     = ["There aren't sufficient operators."]
       calc l (x:xs) | isOper x  = if length l >= 2
                                      then if (x == "/") && (ultimate == 0)
                                               then ["Division by zero"]
                                               else calc (operate x) xs
                                      else ["There aren't sufficient operands."]
                     | isNum x   = calc (push x l) xs
                     | otherwise = ["There are tokens which aren't numbers or operators."]
           where
               operate "+" = push (show $ penultimate + ultimate) begin
               operate "-" = push (show $ penultimate - ultimate) begin
               operate "*" = push (show $ penultimate * ultimate) begin
               operate "/" = push (show $ penultimate / ultimate) begin
               operate "^" = push (show $ penultimate ^ (read $ show penultimate :: Int)) begin

               begin = init $ init l
               ultimate = read $ last l :: Float
               penultimate = read (last $ init l) :: Float

               push n = (++ [n])

main :: IO()
main = do
   putStr ">> "
   n <- (readLn :: IO String)
   if (/= "EXIT") (map (C.toUpper) n)
       then do
           putStrLn $ "Result: " ++ (rpn n)
           main
       else putStrLn "End."

Editado por thoga31
Breve melhoramento do código

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
HappyHippyHippo    1132
HappyHippyHippo

o tradicional C :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define BUFFER_SIZE 256
#define OPS "+-*/^"

int main(){
 char buffer[bUFFER_SIZE];                                // buffer de leitura do teclado
 size_t readed;                                           // contador de bytes lidos do teclado
 double stack[bUFFER_SIZE];                               // stack das entradas a serem usadas nas operações
 int ok = 1;                                              // marcador de erro
 int pos = -1;                                            // posição actual da stack
 int size;                                                // variável usada para guardar o número de caracteres da entrada
 char * tok = NULL;                                       // ponteiro usado para leitura das entradas da expressão

 do {                                                     // ciclo de vida da aplicação
   printf("expressao : ");                                // pedido pela expressão matemática
   fflush(stdout);                                        // forçar a impressão do pedido pois este não tem o '\n'
   fgets(buffer, BUFFER_SIZE, stdin);                     // leitura da expressão do teclado
   if ((readed = strlen(buffer)) != 1) {                  // verificação se foi carregado simplesmente no ENTER (sair)
     buffer[readed - 1] = 0;                              // remover o '\n' do final do buffer de leitura
     pos = -1;                                            // iniciar a stack
     ok = 1;                                              // assumir que a expressão está correctamente escrita 

     tok = strtok(buffer, " \t");                         // ler a primeira entrada
     while (ok && tok != NULL) {                          // ciclo de leitura de entradas
       size = strlen(tok);                                // verificar o tamanho da entrada
       if (size > 0) {                                    // validação para entradas sem valor (espaços consecutivos)
         if (size == 1 && strchr(OPS, tok[0]) != NULL) {  // se for um operador válido
           if (pos < 1) {                                 // verificar se existe valores suficientes para a oepração
             printf("Invalid/unexpected op token found on expression at position %ld : %s\n", (size_t)tok - (size_t)buffer, tok);
             ok = 0;                                      // terminar o ciclo de leitura
           } else {
             switch (tok[0]) {                            // efectuar a operação sobre os dois últimos elementos da stack
               case '+': stack[pos - 1] = stack[pos - 1] + stack[pos]; break;
               case '-': stack[pos - 1] = stack[pos - 1] - stack[pos]; break;
               case '*': stack[pos - 1] = stack[pos - 1] * stack[pos]; break;
               case '/': stack[pos - 1] = stack[pos - 1] / stack[pos]; break;
               case '^': pow(stack[pos - 1], stack[pos]); break;
               default: break;
             }
             pos--;                                       // definir a posição da stack como a calculada
           }
         } else
           stack[++pos] = strtod(tok, NULL);              // adicinoar a entrada à stack
       }
       tok = strtok(NULL, " \t");                         // ler a próxima entrada
     }

     if (ok) {
       if (pos != 0)                                      // verificar a leitura completa da expressão
         printf("Unexpected end of expression\n");
       else
         printf("Result : %f\n", stack[0]);               // apresentar resultado
     }
   }
 } while (readed != 1);                                   // continuar enquanto não foi inserido somente o EOL no teclado

 return 0;
}

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
HappyHippyHippo    1132
HappyHippyHippo

no muito engraçado Prolog

/* predicado de chamada de resolução de uma expressão em "Reverse Polish Notation"
*
* exemplo :
* ?- rpn('5 1 2 + 4 * + 3 -', R).
* R = 14.
*/
rpn(E, R) :- atomic_list_concat(L, ' ', E),              /* separar a expressão nos elemento que a compoem */
            rpn(L, [], R).                              /* chamada do predicado com stack inicializada */

rpn([], [R], R).                                         /* predicado de fim de leitura dos elementos da expressão */

rpn(['+' | L], [X, Y | S], R) :- P is Y + X,             /* predicado de calculo da adição */
                                rpn(L, [P | S], R), !.  /* chamada do predicado com o resultado parcial na stack */
rpn(['-' | L], [X, Y | S], R) :- P is Y - X,             /* predicado de calculo da subtração */
                                rpn(L, [P | S], R), !.  /* chamada do predicado com o resultado parcial na stack */
rpn(['*' | L], [X, Y | S], R) :- P is Y * X,             /* predicado de calculo da multiplicação */
                                rpn(L, [P | S], R), !.  /* chamada do predicado com o resultado parcial na stack */
rpn(['/' | L], [X, Y | S], R) :- P is Y / X,             /* predicado de calculo da divisão */
                                rpn(L, [P | S], R), !.  /* chamada do predicado com o resultado parcial na stack */
rpn(['^' | L], [X, Y | S], R) :- P is Y ^ X,             /* predicado de calculo da potência */
                                rpn(L, [P | S], R), !.  /* chamada do predicado com o resultado parcial na stack */
rpn([A | L], S, R) :- atom_number(A, F),                 /* predicado de leitura de um valor numérico */
                     rpn(L, [F | S], R).                /* chamada do predicado com o valor numérico na stack */

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
HappyHippyHippo    1132
HappyHippyHippo

em PHP:

<?php
$ops = array("+", "-", "*", "/", "^");
$stack = array();
$ok = 1;

//$exp = "3 4 +";
$exp = "5 1 2 + 4 * + 3 -";
//$exp = "2 5 ^ 1 +";
foreach(explode(" ", $exp) as $param) {
   if (($key = array_search($param, $ops)) !== false) {
       if (count($stack) < 2) {
           echo "Unexpected operator found : {$param}<br />";
           $ok = 0;
           break;
       } else {
           $size = count($stack);
           eval("\$stack[\$size - 2] = \$stack[\$size - 2] {$param} \$stack[\$size - 1];");
           unset($stack[$size - 1]);
       }
   } else {
       if (!is_numeric($param)) {
           echo "Unvalid param found : {$param}<br />";
           $ok = 0;
           break;
       } else
           $stack[count($stack)] = (double)$param;
   }
}

if ($ok) {
   if (count($stack) != 1)
       echo "Unexpected end of exp<b></b>ression<br />";
   else
       echo "result : {$stack[0]}<br />";
}
?>

Editado por HappyHippyHippo

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
pwseo    224
pwseo

Mais um em Haskell (também no ideone). Tomei a liberdade de criar alguns sinónimos de tipos de dados só porque sim, clarificando um pouco as assinaturas das funções:

import System.IO

type Stack = [integer]
type Operator = Integer -> Integer -> Integer

apply :: Operator -> Stack -> Stack
apply f (x:y:zs) = (f y x) : zs

opList :: [(String, Operator)]
opList = [ ("+", (+)), ("-", (-))
        , ("*", (*)), ("/", div)
        , ("^", (^)) ]

runRPN :: [string] -> Stack -> Integer
runRPN [] (t:_) = t
runRPN (curr:rest) stk =
 case lookup curr opList of
   Just op -> runRPN rest $ apply op stk
   Nothing -> runRPN rest $ (read curr) : stk

main :: IO ()
main = interact $ unlines . map f . lines
 where f x = show $ runRPN (words x) []

PS.: Muito provavelmente há coisas simplificáveis, como sempre!

EDIT: Alterei a função apply para algo mais simples.

Editado por pwseo

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
thoga31    611
thoga31

E eu dei conta que tinha algo desnecessário na função rpn (fazer "if length res == 1 then head else last" é mesmo à mestre carpinteiro :D ), e o @pwseo chamou-me a atenção para um pequeno erro na main.

E, claro, estou a devorar a solução do @pwseo, que eu estou sedento de aprender este raciocínio mais "Haskelliano" :D

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Rui Carlos    311
Rui Carlos

Tenho para aqui um código de um trabalho prático que faz algo do género.

Quando tiver tempo coloco aqui (é mais um em Haskell :D).

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
KTachyon    272
KTachyon

A solução em Objective-C com Runtime:

#import <Foundation/Foundation.h>
#import <objc/runtime.h>
#import <math.h>

#define assert(x, m) if (!x) { printf("%s\n", [m cString]); exit(-1); }

int main(int argc, const char * argv[]) {
   NSPredicate *opPredicate = [NSPredicate predicateWithFormat:@"SELF MATCHES %@", @"^(\\+|\\-|\\*|/|\\^)$"];
   NSPredicate *numPredicate = [NSPredicate predicateWithFormat:@"SELF MATCHES %@", @"^\\-?[0-9]*\\.?[0-9]+$"];

   id (^pop)(id) = ^(id _self) {
       if ([_self count] == 0) return (id)@0;
       id obj = [_self lastObject];
       [_self removeLastObject];
       return obj;
   };

   void (^push)(id, id) = ^(id _self, id obj) {
       if ([opPredicate evaluateWithObject:obj]) {
           double a = [[_self pop] doubleValue], b = [[_self pop] doubleValue];

           if ([obj isEqualToString:@"+"]) [_self push:[NSString stringWithFormat:@"%f", b + a]];
           if ([obj isEqualToString:@"*"]) [_self push:[NSString stringWithFormat:@"%f", b * a]];
           if ([obj isEqualToString:@"-"]) [_self push:[NSString stringWithFormat:@"%f", b - a]];
           if ([obj isEqualToString:@"/"]) [_self push:[NSString stringWithFormat:@"%f", b / a]];
           if ([obj isEqualToString:@"^"]) [_self push:[NSString stringWithFormat:@"%f", pow(b, a)]];
       }
       else if ([numPredicate evaluateWithObject:obj]) [_self addObject:obj];
       else assert(NO, @"Invalid input");
   };

   class_addMethod([NSMutableArray class], @selector(pop), imp_implementationWithBlock(pop), "@@:");
   class_addMethod([NSMutableArray class], @selector(push:), imp_implementationWithBlock(push), "v@:@");

   id stack = [NSMutableArray new];
   NSMutableString *token = [NSMutableString stringWithString:@""];

   for (char c = getchar(); c != '\n'; c = getchar())
       if (c == ' ' && token.length > 0) {
           [stack push:token];
           token = [NSMutableString stringWithString:@""];
       }
       else if (c != ' ') [token appendFormat:@"%c", c];

   if (token.length > 0) [stack push:token];

   printf("Result: %f\nRemaining on stack:%ld\n", [[stack pop] doubleValue], [stack count]);

   return 0;
}

A mesma solução com Categorias:

#import <Foundation/Foundation.h>
#import <math.h>

#define assert(x, m) if (!x) { printf("%s\n", [m cString]); exit(-1); }

@implementation NSMutableArray (RPNStack)

- (id) pop {
   if ([_self count] == 0) return (id)@0;
   id obj = [self lastObject];
   [self removeLastObject];
   return obj;
}

- (void) push:(id)obj {
   NSPredicate *opPredicate = [NSPredicate predicateWithFormat:@"SELF MATCHES %@", @"^(\\+|\\-|\\*|/|\\^)$"];
   NSPredicate *numPredicate = [NSPredicate predicateWithFormat:@"SELF MATCHES %@", @"^\\-?[0-9]*\\.?[0-9]+$"];

   if ([opPredicate evaluateWithObject:obj]) {
       double a = [[self pop] doubleValue], b = [[self pop] doubleValue];

       if ([obj isEqualToString:@"+"]) [self push:[NSString stringWithFormat:@"%f", b + a]];
       if ([obj isEqualToString:@"*"]) [self push:[NSString stringWithFormat:@"%f", b * a]];
       if ([obj isEqualToString:@"-"]) [self push:[NSString stringWithFormat:@"%f", b - a]];
       if ([obj isEqualToString:@"/"]) [self push:[NSString stringWithFormat:@"%f", b / a]];
       if ([obj isEqualToString:@"^"]) [self push:[NSString stringWithFormat:@"%f", pow(b, a)]];
   }
   else if ([numPredicate evaluateWithObject:obj]) [self addObject:obj];
   else assert(NO, @"Invalid input");
}

@end

int main(int argc, const char * argv[]) {
   id stack = [NSMutableArray new];
   NSMutableString *token = [NSMutableString stringWithString:@""];

   for (char c = getchar(); c != '\n'; c = getchar())
       if (c == ' ' && token.length > 0) {
           [stack push:token];
           token = [NSMutableString stringWithString:@""];
       }
       else if (c != ' ') [token appendFormat:@"%c", c];

   if (token.length > 0) [stack push:token];

   printf("Result: %f\nRemaining on stack:%ld\n", [[stack pop] doubleValue], [stack count]);

   return 0;
}

EDIT: A primeira só deverá funcionar em Mac OS X e iOS. Os métodos do runtime.h só foram implementados para estas plataformas e, em Linux/Windows seria necessário brincar com structs e ponteiros para se obter o mesmo resultado. A segunda deverá funcionar em todas as plataformas.

EDIT 2: Suporte para o ^.

EDIT 3: Suporte para números negativos

Editado por KTachyon

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
KTachyon    272
KTachyon

A mesma solução em Python:

from string import split
from operator import add, sub, mul, div, pow

operations = { '+':add, '-':sub, '*':mul, '/':div, '^':pow }
stack = []

def pop(stack): return stack.pop() if len(stack) > 0 else 0

try:
   for token in split(raw_input()):
       if token in operations:
           a, b = pop(stack), pop(stack)
           r = operations[token](b, a)
       else: r = float(token)

       stack.append(r)

   print(stack.pop())
except: print("Invalid input")

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
KTachyon    272
KTachyon

Em lex/yacc, sem permitir retirar zeros caso a stack esteja vazia:

RPN.l:

%{
#include <stdlib.h>
#include "y.tab.h"
%}

%%

"-"?[0-9]*"."?[0-9]+    { yylval.value = atof(yytext); return NUM; }
" "                     ;
"+"|"-"|"*"|"/"|"^"     { return yytext[0]; }
"\n"                    { return EOE; }
.                       { printf("Invalid input\n"); exit(-1); }

%%

int yywrap() { return 1; }

RPN.y:

%{
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
%}

%token <value> NUM

%token EOE

%union{
   double value;
}

%type <value> rpn

%%

exp : rpn EOE        { printf("%f\n\n", $1); exit(0); }
   ;

rpn : NUM            { $$ = $1; }
   | rpn rpn '+'    { $$ = $1 + $2; }
   | rpn rpn '-'    { $$ = $1 - $2; }
   | rpn rpn '*'    { $$ = $1 * $2; }
   | rpn rpn '/'    { $$ = $1 / $2; }
   | rpn rpn '^'    { $$ = pow($1, $2); }
   ;

%%

int main()  { yyparse(); return 0; }

Compilação:

yacc -d RPN.y; lex -i RPN.l; cc y.tab.c lex.yy.c -ll -ly;

Editado por KTachyon

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora


×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade