Jump to content
thoga31

Calculadora por Explosão

Recommended Posts

thoga31

O desafio intitula-se A Calculadora por Explosão, e baseia-se em criar um pequeno programa que não é mais do que uma calculadora. Contudo, não é uma qualquer.

O objectivo é que esta calculadora seja como uma Texas Instruments ou uma Casio, onde o utilizador escreve, por exemplo, 3+4x(3+(4/2)-(9/3))^2, e é debitado o resultado 19. Ou seja, nada como a calculadora do Windows, ou uma calculadora passo-a-passo tipo "introduza 1º valor, introduza 2º valor, introduza operador", ou uma calculadora que só faz uma operação de cada vez, introduzindo-se por exemplo, 3+16.

Input:

Por exemplo: 3+4x(3+(4/2)-(9/3))^2

Output:

No caso exemplificado: 19

Operações possíveis e sua representação:

  • +, soma
  • -, subtracção
  • * ou x (ambos têm de ser admitidos), multiplicação
  • / ou : (ambos têm de ser admitidos), divisão
  • ^, potenciação

Originalmente propuseram-me uma resolução em VB ou VB.NET, mas acho interessante ver diferentes soluções em diferentes linguagens.

Tentem, sempre que possível, um código sem recorrer a possíveis funções e procedimentos pré-existentes que facilitem "de mais", se me estou a fazer entender. ;)  Algo como SolveCalculation(input) (código inventado)

Espero que achem um desafio interessante para os vossos pequenos tempos livres.

Sendo um desafio "interessante", não espero nenhuma enchente de soluções. :P

Cumprimentos,

thoga31

P.S. - poderão ver um bom exemplo disto com a linha de comandos do Windows. Introduzam o seguinte:

set 3+4*(3+(4/2)-(9/3))

Vai ser devolvido o resultado 11.


Knowledge is free!

Share this post


Link to post
Share on other sites
KTachyon

Há alguns anos desenvolvi um cross-compiler de um sub-set de Lisp para C que permitia fazer isto com as 4 operações básicas. Mas escrito na notação de Lisp, ou seja,

(+ 3 (* 4 (+ 3 (- (/ 4 2) (/ 9 3)))))

É relativamente fácil de desenvolver utilizando Lex, Yacc e C.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
thoga31

Então, era giro dares a solução numa dessas três linguagens segundo o método que disseste.

Dizer que é fácil... é fácil. ;)

EDIT, motivo:

Lex e yacc não linguagens de programação. E ele disse que era fácil utilizando os 3 e não um dos três.


Knowledge is free!

Share this post


Link to post
Share on other sites
Localhost

Lex e yacc não linguagens de programação. E ele disse que era fácil utilizando os 3 e não um dos três.


here since 2009

Share this post


Link to post
Share on other sites
KTachyon

calc.l (Lex file):

%{
#include "y.tab.h"
%}

%%

[0-9]+					{yylval.value = atoi(yytext); return NUMBER;}
[ \t]					;
[-+*/^()\n]				{return yytext[0];}
.						{ECHO; yyerror ("unexpected character");}

%%

int yywrap() { return 1; }

calc.y (Yacc file):

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

%union {int value;}
%start line
%token <value> NUMBER

%type <value> expression precedence value

%%

line		: expression '\n'			{printf ("%d\n", $1);}
		;
expression	: precedence				{$$ = $1;}
		| expression '+' precedence	{$$ = $1 + $3;}
		| expression '-' precedence	{$$ = $1 - $3;}
		| expression '^' precedence	{$$ = pow($1, $3);}
		;
precedence	: value						{$$ = $1;}
		| precedence '*' value		{$$ = $1 * $3;}
		| precedence '/' value		{$$ = $1 / $3;}
		;
value		: NUMBER					{$$ = $1;}
		| '(' expression ')'		{$$ = $2;}
		;

%%

int main() { return yyparse(); }

void yyerror(char *s) { fprintf(stderr, "%s\n", s); }

Para compilar:

lex -i calc.l
yacc -d calc.y
cc -o calc y.tab.c lex.yy.c -ll -ly


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
thoga31

Era fixe que Pascal/Delphi tivesse assim uns "atalhos" :cheesygrin:


Knowledge is free!

Share this post


Link to post
Share on other sites
KTachyon

Não são exactamente atalhos. Os ficheiros Lex e Yacc contêm a gramática e a árvore de sintaxe. Quando esses ficheiros são transformados em C, ficam com 3400 linhas de código ;)


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
thoga31

print eval(raw_input())

;)

Tentem, sempre que possível, um código sem recorrer a possíveis funções e procedimentos pré-existentes que facilitem "de mais", se me estou a fazer entender. :P   Algo como SolveCalculation(input) (código inventado)

Gostava de ver um método, por exemplo em Python, que faça as coisas com cabeça, tronco e membros, não apenas um procedimento pré-existente. :dontgetit:

É esse o objectivo do desafio: criar um algoritmo completo de análise de um cálculo matemático.


Knowledge is free!

Share this post


Link to post
Share on other sites
KTachyon

Só uma dúvida: Como escreves potências no raw_input()?


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
thoga31

Esqueci-me de ser mais específico. Já corrigi o que faltava:

Operações possíveis e sua representação:

  • +, soma
  • -, subtracção
  • * ou x (ambos têm de ser admitidos), multiplicação
  • / ou : (ambos têm de ser admitidos), divisão
  • ^, potenciação

Cumpz. ;)


Knowledge is free!

Share this post


Link to post
Share on other sites
KTachyon

Reparei que o cálculo de potências não está correcto (não lhe estou a dar a precedência correcta). E também reparei que o input utiliza 'x' em vez de '*'. Aqui estão algumas pequenas correcções (e as restantes indicadas no post anterior :P )

%{
#include "y.tab.h"
%}

%%

[0-9]+					{yylval.value = atoi(yytext); return NUMBER;}
[ \t]					;
[-+x*:/^()\n]			{return yytext[0];}
.						{ECHO;}

%%

int yywrap() { return 1; }

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

%union {int value;}
%start line
%token <value> NUMBER

%type <value> expression precedence power value

%%

line		: expression '\n'			{printf ("%d\n", $1);}
		;
expression	: precedence				{$$ = $1;}
		| expression '+' precedence	{$$ = $1 + $3;}
		| expression '-' precedence	{$$ = $1 - $3;}
		;
precedence	: value						{$$ = $1;}
		| precedence 'x' power		{$$ = $1 * $3;}
		| precedence '*' power		{$$ = $1 * $3;}
		| precedence '/' power		{$$ = $1 / $3;}
		| precedence ':' power		{$$ = $1 / $3;}
		;
power		: value						{$$ = $1;}
		| power '^' value			{$$ = pow($1, $3);}
value		: NUMBER					{$$ = $1;}
		| '(' expression ')'		{$$ = $2;}
		;

%%

int main() { while(1) yyparse(); }

EDIT: Pronto... não custa muito mudar agora ;)


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
thoga31

E também reparei que o input utiliza 'x' em vez de '*'.

Atenção, ambas têm de ser admitidas, assim como na divisão " / " e " : " também têm de o ser. ;)


Knowledge is free!

Share this post


Link to post
Share on other sites
KTachyon

Sim, eu entretanto corrigi ;)

Agora suporta tudo.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
thoga31

Pronto, primeira proposta de resolução dada. Utiliza um "atalho" como eu lhe chamo, mas pronto...

Espero entretanto um algoritmo completo. :P

Eu ando a tentar em Pascal, e só a análise completa do texto introduzido vai com umas 150 linhas de código. ;)


Knowledge is free!

Share this post


Link to post
Share on other sites
KTachyon

A técnica é simples. O facto de eu ter escolhido o Lex e o Yacc para resolver o problema foi mesmo por criar uma árvore que permite definir as precedências das operações. Ou seja, a base para se desenvolver isto é criar uma árvore que coloca as operações por precedência, obrigando-te a resolver a árvore de baixo para cima.

Isto podia ser desenvolvido puramente, em qualquer linguagem de programação, com o custo de desenvolver a estrutura da árvore por completo. Eu desenvolvi simplesmente os nós da árvore:

union {int value;}

e defini a estrutura da árvore no Yacc. Não sei se pode ser considerado um atalho ou não, visto que permite fazer tudo o que utilize um input com regras gramaticais e de sintaxe aceitáveis para uma linguagem de programação (Lex e Yacc são ferramentas para criar compiladores ;))


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
mjamado

EDIT: podes ir direitinho à Wikipedia para veres tudo o que escrevi abaixo - notação polaca inversa e o tal algoritmo do Dijkstra (que faz ainda mais coisas, e que já descobri o nome ;)).


thoga31, como em quase tudo neste ramo, não reiventes a roda quando grandes mentes já a inventaram. Mas vamos por fases:

Em primeiro lugar, os computadores têm uma certa dificuldade em resolver coisas da maneira que o ser humano as formula. Neste caso em concreto, algumas linguagens apenas aceitam um certo formato já por causa disso (é o caso do Lisp, que o KTachyon mostrou). Os formatos mais comuns são a notação polaca (o tal do Lisp) e a notação polaca inversa, que é a mesma coisa, mas com os operadores depois dos números, e não antes. Com uma destas notações, é tão simples como leres a expressão da esquerda para a direita e usares uma pilha com os valores (os operadores podem ser descartados à medida que são calculados).

Exemplo de pseudo-código:

Seja input = expressão em notação polaca inversa;
Seja ponteiro = início do input;
Seja pilhaValores = vector vazio;

Enquanto(ponteiro <= tamanho do input)
    Seja elemento = elemento do input em ponteiro;
    Se(elemento for um número)
        Acrescenta elemento a pilhaValores;
    Senão
        Seja operando1 = Retira último valor de pilhaValores;
        Seja operando2 = Retira último valor de pilhaValores;
        Seja valorOperacao = Aplicar a operação em elemento aos elementos operando1 e operando2;
        Acrescenta valorOperacao a pilhaValores;

    Incrementar ponteiro;

Seja resultado = Retirar único valor restante de pilhaValores;
Devolver resultado;

Ok, agora que deixámos isso fora do caminho, temos outro problema: como transformar uma expressão em notação normal em notação polaca inversa, pronta a ser alimentada a este algoritmo? Podes perder uma noite a enjorcar um sistema mas, para quê, se outros já tiveram esse trabalho? Notavelmente, existe um algoritmo do nosso grande amigo Dijkstra para isso!

Infelizmente, não me consigo lembrar do nome do algoritmo (que seria mais Google-friendly para ti), mas é qualquer coisa deste estilo (é possível que tenha erros, mas confio que, ao implementares, darás com eles):

Seja input = expressao a converter;
Seja ponteiro = inicio do input;
Seja output = vector vazio;
Seja pilha = pilhaElementos;
Seja precedências = {+ => 1,
                     - => 1,
                     * => 2,
                     / => 2,
                     ^ => 3};
Seja associações = {+ => esquerda,
                    - => esquerda,
                    * => esquerda,
                    / => esquerda,
                    ^ => direita};

Enquanto(ponteiro <= tamanho do input)
    Seja elemento = elemento do input em ponteiro;
    Escolher por elemento:
        Caso seja um número
            Acrescentar elemento a output;

        Caso seja um operador
            Enquanto último elemento de pilha for um operador
                Seja operador = último elemento da pilha;
                Se ((elemento em associações = direita) e (elemento em precedências <= operador em precedências))
                   ou ((elemento em associações = esquerda) e (elemento em precedências < operador em precedências))
                    Acrescentar operador a output;
                    Retirar operador da pilha;
            Acrescentar elemento à pilha;

        Caso seja "("
            Acrescentar elemento à pilha;

        Caso seja ")"
            Enquanto último elemento da pilha <> "("
                Seja operador = Retirar último elemento da pilha;
                Acrescentar operador a output;
            Retirar último elemento da pilha

    Incrementar ponteiro;

Enquanto pilha <> vector vazio
    Seja operador = Retirar último elemento da pilha;
    Acrescentar operador a output;

Devolver output;

Só uma coisa que é necessário explicar, que são as associações (as precedências são claras, certo?). Um operador pode ser associativo à esquerda ou à direita. Repara: 1 - 2 + 3 poderia ser (1 - 2) + 3 = 2 ou 1 - (2 + 3) = -4. O primeiro exemplo mostra como seria com os operadores com associação à esquerda, e o segundo com associação à direita - o que está errado.

Isto é importante por causa das potências. A expressão 2^3^4, se as potências fossem associativas à direita, seria interpretada como 2^(3^4), o que está errado! Com associação à esquerda, será correctamente interpretada como (2^3)^4.

Assim por alto, acho que é tudo. Go play!


"Para desenhar um website, não tenho que saber distinguir server-side de client-side" - um membro do fórum que se auto-intitula webdesigner. Temo pelo futuro da web.

Share this post


Link to post
Share on other sites
djthyrax

Epá... http://www.portugal-a-programar.pt/forums/topic/0-find-topic/?do=findComment&comment=180269 pois.

A única diferença para as cientificas Texas (a TI-84 p.e) é a sintaxe da potencia que é feita usando ** em vez de ^, coisa que pode ser suportada trocando o ^ por ** antes do eval.


Não peças ajuda por PM! A tua dúvida vai ter menos atenção do que se for postada na secção correcta do fórum!

Share this post


Link to post
Share on other sites
mjamado
Gostava de ver um método, por exemplo em Python, que faça as coisas com cabeça, tronco e membros, não apenas um procedimento pré-existente. :dontgetit:

É esse o objectivo do desafio: criar um algoritmo completo de análise de um cálculo matemático.

Basicamente, fazes um eval da expressão; dificilmente se poderá considerar o que foi pedido... 👎


"Para desenhar um website, não tenho que saber distinguir server-side de client-side" - um membro do fórum que se auto-intitula webdesigner. Temo pelo futuro da web.

Share this post


Link to post
Share on other sites
Warrior

Acho que fiz algo deste género em assembly no primeiro ano, tirando a exponenciação.

Pena já não ter o código..

Share this post


Link to post
Share on other sites
thoga31

@mjamado,

Não estou a reinventar a roda. :thumbsup:   Apenas me colocaram este desafio, e decidi partilhar convosco.


Knowledge is free!

Share this post


Link to post
Share on other sites
djthyrax

Basicamente, fazes um eval da expressão; dificilmente se poderá considerar o que foi pedido... 👎

Eu sei, mas também este é um bom exemplo de uma tarefa que não faz qualquer sentido realizar a não ser que as ferramentas já existentes não façam o que é pretendido, o que não é o caso. É o mesmo que arrancares o teu carro de empurrão quando ele o consegue fazer sozinho. :)

Não peças ajuda por PM! A tua dúvida vai ter menos atenção do que se for postada na secção correcta do fórum!

Share this post


Link to post
Share on other sites
mogers

Já há tão poucos desafios propostos, não vale a pena andar a bater nos poucos que surgem.

Este desafio é bom para quem é relativamente iniciado na programação e pretende desenvolver as suas skills.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.