Help! My calculator broke! (Turn integer expression into calculator keystrokes)

Question

Introduction

Help! I accidentally dropped my TI-84 calculator out my window (don't ask how) and it broke. I have a math test tomorrow and the only calculator I can find is one with these buttons:

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

My math test is a review test on evaluating expressions. I need a program to take an expression such as 1+(5*4)/7 and convert it to the keystrokes needed to solve it on my spare calculator. (And in case you were wondering, this actually happened to me).

Challenge

Given a non-empty input string containing only the characters 0-9, (, ), +, -, *, and /, output the keystrokes in a space-separated string (eg. 1 + 3 / 3 =). There must always be an equal sign at the end of the output. Standard loopholes are not allowed.

Examples:

• Input: 1+(5*4)/7, Output: 5 * 4 / 7 + 1 =
• Input: 6*(2/3), Output: 2 / 3 * 6 =
• Input: (7-3)/2, Output: 7 - 3 / 2 =

To make this challenge easier:

• You may assume that the input has a series of keystrokes linked to it that does not require clearing the calculator (1-(7*3) is not valid since it would require you to find 7 * 3, then clear the calculator to do 1 - 21. All the above examples are valid since there is one, continuous output that does not require the user to clear the calculator and remember a number).
• You may assume that there will only be a single integer after a /, as having an input such as 21/(7*3) would not pass the first assumption either.
• You may assume that there will always be a * between an integer and a left parentheses (Valid: 6*(7), Invalid: 6(7)).
• You may assume the input always produces integer output.
• You may assume the input only has three levels of parentheses.

Non-examples

• 2-(14/2) as you would have to do 14 / 2, then clear, then 2 - 7.
• 36/(2*3) as you would have to do 2 * 3, then clear, then 36 / 6.
• 1024*4/(1*2+2) as you would have to do 1*2+2, then clear, then 1024 * 4 / 4.

Bonuses

• -5% if your program can recognize parentheses multiplication (it knows that 6(7)=6*(7)).
• -5% if your program can handle input with decimal numbers (3.4, 2.75, 7.8) and the output includes . (as there must be a . key on my spare calculator in this case).
• -5% if your program can handle unlimited levels of parentheses.

This is code-golf, shortest code in bytes (including the bonuses) wins!

Leaderboards

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

## Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

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

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

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

You can also make the language name a link which will then show up in the leaderboard snippet:

## [><>](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>

Answer 1

Python 3. 337 327 - 10% = 295 bytes

Supports floating-point and unlimited levels of parentheses, so qualifies for bonus -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]))

Answer 2

TI-BASIC, 605.2 bytes

Eligible for lirtosiast's TI-BASIC bounty under Fitting but Unsuitable Languages.

Qualifies for all 3 bonuses, 712 - 15% = 605.2. There are some golfing opportunities here and there, but I wanted to get this out first, as some of the potential golfs are non-trivial. Please note that TI-BASIC is a tokenized language, and the below is a textual representation of that program. Thus, the program is not 1182 bytes, since this program is not encoded under UTF-8. Note that ~ is equivalent to unary negation and -> to the STO> operator. Output is a string, retrievable from Ans or Str1.

The below program is the result of a few programmer hours thinking and programming, spread over the course of a few weeks.

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

General explanation

Here's the key I worked with while developing the program:

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)

And here is the equivalent, hand-written JavaScript code I used to test and develop this program.

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);

I will provide a more in-depth explanation once I'm sure I'm done golfing, but in the meantime, this might help provide a cursory understanding of the code.

Answer 3

Javascript (ES6), 535 - 80 (15% bonus) = 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,'$& ')+'='}

Not a minimal solution I'm sure, but pretty complete, allowing for all three bonuses. Some instances require multiple pressings of equals key, but do not require clearing of calculator contents. (ex. 3,5,6 & 7 in fiddle)

Link to JSFiddle with some tests: https://jsfiddle.net/2v8rkysp/3/

Here's some unfolded, semi-unobfuscated code with a few comments for good measure.

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, '$& ')+'=';
}