Socorro! Minha calculadora quebrou! (Transforme expressão inteira em pressionamentos de tecla da calculadora)

30

Introdução

Socorro! Eu deixei cair acidentalmente minha calculadora TI-84 pela janela (não pergunte como) e ela quebrou. Eu tenho um teste de matemática amanhã e a única calculadora que posso encontrar é uma com estes botões:

7 8 9 +
4 5 6 -
1 2 3 *
0   = /

Meu teste de matemática é um teste de revisão para avaliar expressões. Eu preciso de um programa para pegar uma expressão como 1+(5*4)/7e convertê-la nas teclas necessárias para resolvê-la na minha calculadora sobressalente. (E no caso de você estar se perguntando, isso realmente aconteceu comigo).

Desafio

Dada uma cadeia de entrada não-vazia contendo unicamente a caracteres 0-9, (, ), +, -, *, e /, os toques de tecla de saída em uma cadeia separada por espaços (por ex. 1 + 3 / 3 =). Sempre deve haver um sinal de igual no final da saída. As brechas padrão não são permitidas.

Exemplos:

  • Entrada 1+(5*4)/7:, Saída:5 * 4 / 7 + 1 =
  • Entrada 6*(2/3):, Saída:2 / 3 * 6 =
  • Entrada (7-3)/2:, Saída:7 - 3 / 2 =

Para facilitar esse desafio:

  • Você pode presumir que a entrada possui uma série de pressionamentos de teclas vinculados a ela que não requerem a limpeza da calculadora ( 1-(7*3)não é válida, pois exigiria que você a localizasse 7 * 3e limpe a calculadora 1 - 21. Todos os exemplos acima são válidos, pois existe uma , saída contínua que não requer que o usuário limpe a calculadora e lembre-se de um número).
  • Você pode assumir que haverá apenas um único número inteiro depois de a /, pois possui uma entrada que 21/(7*3)também não passaria na primeira suposição.
  • Você pode supor que sempre haverá um *entre parênteses inteiro e esquerdo (válido:, 6*(7)inválido:) 6(7).
  • Você pode assumir que a entrada sempre produz saída inteira.
  • Você pode assumir que a entrada possui apenas três níveis de parênteses.

Não exemplos

  • 2-(14/2)como você teria que fazer 14 / 2, então limpe , então 2 - 7.
  • 36/(2*3)como você teria que fazer 2 * 3, então limpe , então 36 / 6.
  • 1024*4/(1*2+2)como você teria que fazer 1*2+2, então limpe , então 1024 * 4 / 4.

Bónus

  • -5% se o seu programa reconhecer multiplicação de parênteses (sabe disso 6(7)=6*(7)).
  • -5% se o seu programa pode manipular a entrada com números decimais ( 3.4, 2.75, 7.8) e a saída inclui .(como deve haver uma .chave na minha calculadora de reposição, neste caso).
  • -5% se o seu programa puder lidar com níveis ilimitados de parênteses.

Este é o , o código mais curto em bytes (incluindo os bônus) vence!

Classificação

Aqui está um snippet de pilha para gerar uma classificação regular e uma visão geral dos vencedores por idioma.

Para garantir que sua resposta seja exibida, inicie-a com um título, usando o seguinte modelo de remarcação:

## Language Name, N bytes

onde Nestá o tamanho do seu envio. Se você melhorar sua pontuação, poderá manter as pontuações antigas no título, identificando-as. Por exemplo:

## Ruby, <s>104</s> <s>101</s> 96 bytes

Se você quiser incluir vários números no cabeçalho (por exemplo, porque sua pontuação é a soma de dois arquivos ou você deseja listar as penalidades do sinalizador de intérpretes separadamente), verifique se a pontuação real é o último número no cabeçalho:

## Perl, 43 + 2 (-p flag) = 45 bytes

Você também pode transformar o nome do idioma em um link que será exibido no snippet do placar de líderes:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

var QUESTION_ID=61751,OVERRIDE_USER=141697;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

GamrCorps
fonte
Você tem permissão para executar programas, mas não pode usá-los para executar a equação real? 0.o
Downgoat
6
@ Vɪʜᴀɴ Você vai ter que perguntar ao meu professor de matemática sobre isso, eu também não entendi.
GamrCorps
Precisamos lidar com a ordem das operações?
lirtosiast
1
Podemos ter alguns casos de teste mais longos e complicados, com dez ou mais operações?
Lirtosiast 30/10/2015
1
Há um erro de digitação. No texto dizendo que 6(7)não vai acontecer, ele também diz que o sinal ?em 6?(7)será sempre um *.
Wizzwizz4

Respostas:

11

Python 3. 337 327 - 10% = 295 bytes

Suporta ponto flutuante e níveis ilimitados de parênteses, portanto, qualifica-se para bônus -10%.

import re
def v(s):
 if s[:1]=='(':l,s=e(s[1:]);return l,s[1:]
 m=re.match(r"\d+\.?\d*|\.\d+",s)
 if m:return[m.group()],s[m.end():]
def b(s,f,*O):
 l,s=f(s)
 while s[:1]in O:
  o=s[0]
  r,s=f(s[1:])
  if len(r)>1:l,r=r,l
  l+=[o]+r
 return l,s
m=lambda s:b(s,v,'*','/')
e=lambda s:b(s,m,'+','-')
print(' '.join(e(input())[0]))
mjmt
fonte
2
???
gato
5
@ sysreq Isso funciona, você só precisa usar argumentos de linha de comando. Substituindo sys.argv[1]por input()obras em ideone (e é mais fácil - dica)
GamrCorps
Existem diretrizes em algum lugar que deixem as coisas claras, como a entrada deve ser lida, não passada como argumento? (Btw @GamrCorps, você quer dizer raw_input (), o que me salvaria apenas quatro caracteres: "sys".) Quanto a não raspar os últimos caracteres, eu realmente queria fazer a bola rolar e ver as soluções de outras pessoas, especialmente se eles fizerem algo mais interessante do que descendência recursiva.
Mjmt
@mjmt de entrada pode ser feita em qualquer método: args de linha de comando, a entrada (), etc.
GamrCorps
1
@mjmt GamrCorps significa input()porque este é Python 3! Python 2's raw_input() ===Python 3's input()!
Wizzwizz4
8

TI-BASIC, 605,2 bytes

Qualificado para a recompensa TI-BASIC do lirtosiast em Idiomas apropriados, mas inadequados .

Qualifica para todos os 3 bônus 712 - 15% = 605.2,. Existem algumas oportunidades de golfe aqui e ali, mas eu queria tirar isso primeiro, pois alguns dos possíveis campos de golfe não são triviais. Observe que o TI-BASIC é uma linguagem tokenizada e a seguir é uma representação textual desse programa. Portanto, o programa não possui 1182 bytes, pois esse programa não é codificado em UTF-8. Note que ~é equivalente à negação unária e ->àSTO> operador. Saída é uma cadeia de caracteres, recuperável de Ansou Str1.

O programa abaixo é o resultado de algumas horas do programador pensando e programando, espalhadas por algumas semanas.

Input "",Str1
0->dim(L1
0->dim(L2
1->I
DelVar S
While I<length(Str1
DelVar T
".->Str3
1->C
While C and I<length(Str1
sub(Str1,I,1->Str2
inString("0123456789.",Str2->C
If C:Then
I+1->I
1->T
Str3+Str2->Str3
End
End
If T=0:Str3+Str2->Str3
sub(Str3,2,length(Str3)-1->Str3
If T=1:Then
expr(Str3->L2(1+dim(L2
End
inString("*+/-",Str3->M
If M:Then
I+1->I
2->T
1->C
While C
dim(L1->C
If C:Then
2fPart(L1(dim(L1))/2)>2fPart(M/2->C
If C:Then
~L1(dim(L1->L2(1+dim(L2
dim(L1)-1->dim(L1
End
End
End
M->L1(1+dim(L1
End
If Str3="(":Then
If S=1:Then
sub(Str1,1,I-1)+"*"+sub(Str1,I,length(Str1)-I+1)->Str1
Else
I+1->I
0->L1(dim(L1)+1
End
End
If Str3=")":Then
I+1->I
While L1(dim(L1
~L1(dim(L1->L2(1+dim(L2
dim(L1)-1->dim(L1
End
dim(L1)-1->dim(L1
End
T->S
End
augment(L2,-seq(L1(X),X,dim(L1),1,-1)->L2
0->dim(L1
1->C
{0,1->L3
For(I,1,dim(L2
L2(I->M
If M>=0:Then
M->L1(dim(L1)+1
Else
If C:Then
L1(dim(L1)-1
Goto S
Lbl A
Ans->Str1
L1(dim(L1->L1(dim(L1)-1
dim(L1)-1->dim(L1
0->C
End
Str1+" "+sub("*+/-",-M,1)+" ->Str1
L1(dim(L1
Goto S
Lbl B
Str1+Ans->Str1
dim(L1)-1->dim(L1
End
End
Goto F
Lbl S
L3Ans->L4
LinReg(ax+b) L3,L4,Y1
Equ►String(Y1,Str2
sub(Str2,1,length(Str2)-3
If C:Goto A
Goto B
Lbl F
Str1

Explicação geral

Aqui está a chave com a qual trabalhei durante o desenvolvimento do programa:

Str1        The input string.
Str2        Counter variable (e.g. current character)
Str3        The current token being built.
L1          The operator stack
L2          The output queue
L3          Temporary list
L4          Temporary list
I           Iterator index
T           Type of token (enum)
S           Type of previous token (enum)
M           Temporary variable
C           Conditional variable


Token Types (T)
0           Undefined
1           Number
2           Operator
3           Open Parenthesis

Operator Elements
0           left parenthesis ("(")
1           multiplication ("*")
2           addition ("+")
3           division ("/")
4           subtraction ("-")
5           right parenthesis (")")

Precedence Rule: Remainder(prec, levelno)
0 - add, sub
1 - mul, div
(levelno = 2)

E aqui está o código JavaScript manuscrito equivalente que usei para testar e desenvolver este programa.

let Str1, Str2, Str3, L1, L2, I, S, T, M, C;

let error = (type, ...args) => {
    let message = "ERR:" + type + " (" + args.join("; ") + ")";
    throw new Error(message);
};

let isInteger = (n) => n == Math.floor(n);

let inString = (haystack, needle, start=1) => {
    if(start < 1 || !isInteger(start)) {
        error("DOMAIN", haystacak, needle, start);
    }
    let index = haystack.indexOf(needle, start - 1);
    return index + 1;
};

let sub = (string, start, length) => {
    if(start < 1 || length < 1 || !isInteger(start) || !isInteger(length)) {
        error("DOMAIN", string, start, length);
    }
    if(start + length > string.length + 1) {
        error("INVALID DIM", string, start, length);
    }
    return string.substr(start - 1, length);
}

let fPart = (value) => value - Math.floor(value);

// Input "", Str1
Str1 = process.argv[2];
// 0->dim(L1
L1 = [];
// 0->dim(L2
L2 = [];
// 1->I
I = 1;
// DelVar S
S = 0;
// While I<=length(Str1
while(I <= Str1.length) {
    // DelVar T
    T = 0;
    // Disp "Starting",I
    console.log("Starting, I =", I);

    // " read token
    // ".->Str3
    Str3 = ".";
    // 1->C
    C = 1;
    // While C and I<=length(Str1
    while(C && I <= Str1.length) {
        // sub(Str1,I,1->Str2
        Str2 = sub(Str1, I, 1);
        // inString("0123456789",Str2->C
        C = inString("0123456789", Str2);
        // If C:Then
        if(C) {
            // I+1->I
            I++;
            // 1->T
            T = 1;
            // Str3+Str2->Str3
            Str3 += Str2;
        }
    }
    // If T=0:
    if(T == 0) {
        // console.log("Huh?T=0?", Str3, Str2);
        // Str3+Str2->Str3
        Str3 += Str2;
    }

    // " remove placeholder character
    // sub(Str3,2,length(Str3)-1->Str3
    Str3 = sub(Str3, 2, Str3.length - 1);

    // " number
    // If T=1:Then
    if(T == 1) {
        // expr(Str3->L2(1+dim(L2
        L2[L2.length] = eval(Str3);
    }

    // Disp "Str3",Str3
    console.log("post processing, Str3 = \"" + Str3 + "\"");

    // inString("*+/-",Str3->M
    M = inString("*+/-", Str3);
    // " operator
    // If M:Then
    if(M) {
        // I+1->I
        I++;
        // 2->T
        T = 2;
        // Disp "op",M,dim(L1
        console.log("op", M, L1.length);
        // " parse previous operators
        // 1->C
        C = 1;
        // While C
        while(C) {
            // dim(L1->C
            C = L1.length;
            // If C:Then
            if(C) {
                // 2fPart(L1(dim(L1))/2)>2fPart(M/2->C
                C = 2 * fPart(L1[L1.length - 1] / 2) > 2 * fPart(M / 2);
                // If C:Then
                if(C) {
                    // ~L1(dim(L1->L2(1+dim(L2
                    L2[L2.length] = -L1[L1.length - 1];
                    // dim(L1)-1->dim(L1
                    L1.length--;
                }
            }
        }
        // " push current operator
        // M->L1(1+dim(L1
        L1[L1.length] = M;
    }
    // If Str3="(":Then
    if(Str3 == "(") {
        // 3->T
        T = 3;
        // If S=1:Then
        if(S == 1) {
            // sub(Str1,1,I-1)+"*"+sub(Str1,I,length(Str1)-I+1)->Str1
            Str1 = sub(Str1, 1, I - 1) + "*" + sub(Str1, I, Str1.length - I + 1);
        }
        // Else
        else {
            // I+1->I
            I++;
            // 0->L1(dim(L1)+1
            L1[L1.length] = 0;
        }
        // End
    }
    // If Str3=")":Then
    if(Str3 == ")") {
        // I+1->I
        I++;
        // While L1(dim(L1
        while(L1[L1.length - 1]) {
            // ~L1(dim(L1->L2(1+dim(L2
            L2[L2.length] = -L1[L1.length - 1];
            // dim(L1)-1->dim(L1
            L1.length--;
        }
        // End
        // dim(L1)-1->dim(L1
        L1.length--;
    }
    // Disp "Ending",I
    console.log("Ending", I);
    // T->S
    S = T;
    // Pause
    console.log("-".repeat(40));
}

// augment(L2,-seq(L1(X),X,dim(L1),1,-1)->L2
L2 = L2.concat(L1.map(e => -e).reverse());

// Disp L1, L2
console.log("L1", L1);
console.log("..", "[ " + L1.map(e=>"*+/-"[e-1]).join`, ` + " ]");
console.log("L2", L2);
console.log("..", "[ " + L2.map(e=>e<0?"*+/-"[~e]:e).join`, ` + " ]");

// post-processing
let res = "";
// 0->dim(L1
L1.length = 0;
// 1->C
C = 1;
// For(I,1,dim(L2
for(I = 1; I <= L2.length; I++) {
    // L2(I->M
    M = L2[I - 1];
    // If M>=0:Then
    if(M >= 0) {
        // M->L1(dim(L1)+1
        L1[L1.length] = M;
    }
    // Else
    else {
        // If C:Then
        if(C) {
            // L1(dim(L1)-1
            // Goto ST
            // Lbl A0
            // Ans->Str1
            res += L1[L1.length - 2];
            // L1(dim(L1->L1(dim(L1)-1
            L1[L1.length - 2] = L1[L1.length - 1];
            // dim(L1)-1->dim(L1
            L1.length--;
            // 0->C
            C = 0;
        }
        // End
        // Str1+" "+sub("*+/-",-M,1)+" ->Str1
        res += " " + "*+/-"[-M - 1] + " ";
        // L1(dim(L1
        // Goto ST
        // Lbl A1
        // Str1+Ans->Str1
        res += L1[L1.length - 1];
        // dim(L1)-1->dim(L1
        L1.length--;
    }
}
// Goto EF
// Lbl ST
// L3Ans->L4
// LinReg(ax+b) L3,L4,Y1
// Equ►String(Y1,Str2
// sub(Str2,1,length(Str2)-3
// If C:Goto A0
// Goto A1
// Lbl EF
// Str1
console.log(res);

Fornecerei uma explicação mais aprofundada quando tiver certeza de que já terminei de jogar golfe, mas, enquanto isso, isso pode ajudar a fornecer uma compreensão superficial do código.

Conor O'Brien
fonte
Você pode assumir a nova calculadora TI-84 + CE, assim Input "",Str1 0->dim(L1 0->dim(L2 1->I DelVar Spode ser Prompt Str1:SetUpEditor :1->I, e pode usar toString (. Também possui algumas
parênteses
@lirtosiast Bom ponto sobre a calculadora nova, eu não queria incluir, toStringpois não tenho um CE. Vou examinar a emulação para garantir a validade do programa.
Conor O'Brien
7

Javascript (ES6), 535 - 80 (bônus de 15%) = 455 bytes

f=z=>{a=[],i=0;c=n=>{while(n[M='match'](/\(/)){n=n[R='replace'](/\(([^()]+)\)/g,(q,p)=>{m=++i;a[m]=c(p);return'['+m+']'})}n=n[R](/(\](?=\[|[\d])|[\d](?=\[))/g,'$1*');n=n[R](/\[?[\d\.]+\]?[*/]\[?[\d\.]+\]?/g,q=>{a[++i]=q;return'['+i+']'});n=n[R](/([\d.]+)\+(\[[\d]+\])/g,'$2+$1');while(n[M](/\[/)){n=n[R](/(\[?[\d\.]+\]?)\*(\[?[\d\.]+\]?)/g,(q,p,r)=>{t=a[r[R](/[\[\]]/g,'')];return r[M](/\[/)?(t&&t[M](/\+|\-/)?(r+'*'+p):q):q});n=n[R](/\[(\d+)\]/g,(q,p)=>{return a[p]+(a[p][M](/\+|-/)?'=':'')})}return n};return c(z)[R](/./g,'$& ')+'='}

Não é uma solução mínima, tenho certeza, mas bastante completo, permitindo todos os três bônus. Algumas instâncias exigem várias pressões da tecla igual, mas não exigem a limpeza do conteúdo da calculadora. (ex. 3,5,6 e 7 em violino)

Link para o JSFiddle com alguns testes: https://jsfiddle.net/2v8rkysp/3/

Aqui está um código desdobrado, semi-oculto, com alguns comentários para uma boa medida.

function f(z) {
var a=[],i=0;
function c(n) {
    //// Tokenize parentheses groups recursively
    while (n.match(/\(/)) {
    n = n.replace(/\(([^()]+)\)/g, function(q,p) {
      m = ++i;
      a[m]=c(p);
      return '['+m+']';
    });
    }

    //// Allow implied multiplication with parentheses
    n = n.replace(/(\](?=\[|[\d])|[\d](?=\[))/g, '$1*');

    //// Tokenize mult/division
    n = n.replace(/\[?[\d\.]+\]?[*\/]\[?[\d\.]+\]?/g, function(q) {
      a[++i]=q;
      return '['+i+']';
    });

    //// Move addition tokens to the front
    n = n.replace(/([\d.]+)\+(\[[\d]+\])/g,'$2+$1');

    //// Detokenize
    while (n.match(/\[/)) {
        //// If a token includes addition or subtraction,
        ////   move it to the front of other tokens 
        n = n.replace(/(\[?[\d\.]+\]?)\*(\[?[\d\.]+\]?)/g,function(q,p,r) {
          t=a[r.replace(/[\[\]]/g,'')];
          return r.match(/\[/)?(t&&t.match(/\+|\-/)?(r+'*'+p):q):q;
        });
        //// If a token includes addition or subtraction,
        ////   add the equals keypress
        n = n.replace(/\[(\d+)\]/g, function(q,p) {
           return a[p]+(a[p].match(/\+|-/)?'=':'');
        });
    }
    return n;
}
//// Add spaces and final equals keypress
return c(z).replace(/./g, '$& ')+'=';
}
styletron
fonte