28
\$\begingroup\$

You must write a program that evaluates a string that would be entered into an advanced calculator.

The program must accept input using stdin and output the correct answer. For languages that do no have functions to accept stdin, you may assume the functions readLine and print to handle these tasks.

Requirements:

  • Does not use any kind of "eval" functions
  • Can handle floating point and negative numbers
  • Supports at least the +, -, *, /, and ^ operators
  • Supports brackets and parenthesis for overriding the normal order
  • Can handle input containing one or more spaces between the operators and numbers
  • Evaluates the input using the standard order of operations

Test Cases

Input

10 - 3 + 2

Output

9


Input

8 + 6 / 3 - 7 + -5 / 2.5

Output

1


Input

4 + [ ( -3 + 5 ) * 3.5 ] ^ 2 - 12

Output

41
\$\endgroup\$
  • 1
    \$\begingroup\$ Is it ok if the outputted numbers have a trailing .0 at the end if they're integers? Also: how accurate does the calculator have to be (regarding floating point precision and such)? \$\endgroup\$ – sepp2k Feb 6 '11 at 18:45
  • 1
    \$\begingroup\$ The output can have a trailing .0 on the end. I'm not too sure about the precision, but more is better. \$\endgroup\$ – Kevin Brown Feb 6 '11 at 20:33
  • 1
    \$\begingroup\$ The Stack Overflow version was Mathematical expression evaluator (full PEMDAS). Though many of the answer to that one are counting lines (?!?). Still there are several compact answers in c. \$\endgroup\$ – dmckee Feb 6 '11 at 21:30
  • \$\begingroup\$ Bonus for PN/RPN calculators? \$\endgroup\$ – Mateen Ulhaq Mar 20 '11 at 4:49
10
\$\begingroup\$

Perl, 140

Using ugly regexes (take note that the /e option, despite the name, is not an eval. For the comparison, /ee would be):

$"=qr/ *(-?\d+\.?\d*) */;1while s/[([]$"[])]/$1/
||s/$"\^$"/$1**$2/e||s,$"([*/])$",'*'eq$2?$1*$3:
$1/$3,e||s/$"([+-])$"/'+'eq$2?$1+$3:$1-$3/e

Run with perl -pE 'code here' (p flag counted in code length)

\$\endgroup\$
  • \$\begingroup\$ This is wrong: (1+2)^2*2 should give 18, but your solution gives 34 because it computes the 2*2 before the exponentiation. \$\endgroup\$ – Timwi Mar 22 '11 at 22:09
  • 15
    \$\begingroup\$ It's been five years. Can someone ungolf this for me so I can finally understand how it actually works? \$\endgroup\$ – J B Feb 17 '16 at 22:56
8
\$\begingroup\$

C++, 640 583

string k="[]()+-*/^";stack<double> m;stack<char> n;
#define C(o,x,y) ('^'==o?x<y:x<=y)
#define Q(a) double a=m.top();m.pop();
#define R(o) {Q(b)Q(a)m.push(o=='+'?a+b:o=='-'?a-b:o=='*'?a*b:o=='/'?a/b:o=='^'?pow(a,b):0);n.pop();}
while(!cin.eof()){string s;getline(cin,s,' ');if(s.empty())continue;if('\n'==*--s.end())s.erase(--s.end());(s.size()==1&&s.npos!=k.find(s[0]))?({char c=s[0]=='['?'(':s[0]==']'?')':s[0];while(!n.empty()&&'('!= c&&C(c,k.find(c),k.find(n.top())))R(n.top());')'==c?n.pop():n.push(c);}):m.push(strtod(s.c_str(),0));}while(!n.empty())R(n.top());cout<<m.top()<<endl;

Indented

string k="[]()+-*/^";
stack<double> m;
stack<char> n;
#define C(o,x,y) ('^'==o?x<y:x<=y)
#define Q(a) double a=m.top();m.pop();
#define R(o) {Q(b)Q(a)m.push(o=='+'?a+b:o=='-'?a-b:o=='*'?a*b:o=='/'?a/b:o=='^'?pow(a,b):0);n.pop();}
while(!cin.eof())
{
    string s;
    getline(cin,s,' ');
    if(s.empty())continue;
    if('\n'==*--s.end())s.erase(--s.end());
    (s.size()==1&&s.npos!=k.find(s[0]))?({
        char c=s[0]=='['?'(':s[0]==']'?')':s[0];
        while(!n.empty()&&'('!= c&&C(c,k.find(c),k.find(n.top())))
            R(n.top());
        ')'==c?n.pop():n.push(c);
    }):m.push(strtod(s.c_str(),0));
}
while(!n.empty())
    R(n.top());
cout<<m.top()<<endl;

My first code golf, so looking forward to comments & criticism!

\$\endgroup\$
  • \$\begingroup\$ Handles the right-associativity of the exponentiation operator, which J B's Perl solution doesn't seem to. \$\endgroup\$ – drspod Feb 6 '11 at 22:10
  • \$\begingroup\$ Neither the problem statement nor the linked wikipedia page mention exponentiation has to be right-associative. Furthermore, the wikipedia page explicitely says both ways are found on commercial calculators. \$\endgroup\$ – J B Feb 7 '11 at 10:23
  • 1
    \$\begingroup\$ +1 nicely golfed, but... just dropping includes, using namespace std and a main function isn't really ok, is it? \$\endgroup\$ – ceased to turn counterclockwis Oct 17 '12 at 22:26
2
\$\begingroup\$

PHP - 394 354 312 characters

<?=e(!$s=preg_split('#\s+#',`cat`,-1,1),$s);function e($P,&$s){$S='array_shift';if(($a=$S($s))=='('|$a=='['){$a=e(0,$s);$S($s);}while($s&&($p=strpos(' +-*/^',$o=$s[0]))&&$p>=$P){$b=e($p+($S($s)!='^'),$s);if($o=='+')$a+=$b;if($o=='-')$a-=$b;if($o=='*')$a*=$b;if($o=='/')$a/=$b;if($o=='^')$a=pow($a,$b);}return$a;}

Indented:

<?
preg_match_all('#\d+(\.\d+)?|\S#',`cat`,$m);
$s=$m[0];
function e($P) {
        global $s;
        if (strpos(" ([",$s[0])){
                array_shift($s);
                $a=e(0);
                array_shift($s);
        } else {
                $a=array_shift($s);
                if ($a=='-')$a.=array_shift($s);
        }
        while ($s && ($p=strpos(' +-*/^',$o=$s[0])) && $p >= $P) {
                array_shift($s);
                $b = e($p+($o!='^'));
                switch($o){
                case'+':$a+=$b;break;
                case'-':$a-=$b;break;
                case'*':$a*=$b;break;
                case'/':$a/=$b;break;
                case'^':$a=pow($a,$b);
                }
        }
        return $a;
}
echo e(0);
\$\endgroup\$
2
\$\begingroup\$

Postscript, 446

This uses the shunting yard algorithm.

[/*[/p
2/e{mul}>>/d[/p
2/e{div}>>/+[/p
1/e{add}>>/-[/p
1/e{sub}>>/o[/p
9/e{}>>/c[/p
-1/e{}>>/^[/p
3/e{exp}>>/p
0>>begin/s(%stdin)(r)file 999 string readline pop def
0 1 s length 1 sub{s exch[0 1 255{}for]dup[(\(o)([o)(\)c)(]c)(/d)]{{}forall
put dup}forall
pop
3 copy pop
get
get
put}for{s token not{exit}if
exch/s exch store{cvr}stopped{load
dup/p get
p
le{currentdict end
exch begin/e get exec}{begin}ifelse}if}loop{{e end}stopped{exit}if}loop
=

Un-golfed and commented:

% We associate the operators with their precedence /p and the executed commend /e
[
  (*)[/p  2 /e{mul}>>
  (d)[/p  2 /e{div}>> % This is division
  (+)[/p  1 /e{add}>>
  (-)[/p  1 /e{sub}>>
  (o)[/p  9 /e{   }>> % This is open bracket
  (c)[/p -1 /e{   }>> % This is close bracket
  (^)[/p  3 /e{exp}>>
  /p 0
>>begin

% Let's read the input string
/s(%stdin)(r)file 999 string readline pop def

% If we want to use the token operator, we have to replace (, [, ), ] and / to get meaningful results
% We use kind of an encoding array (familiar to PostScripters) to map those codes to o, c, and d.
0 1 s length 1 sub{        % index
  s exch                   % string index
  [0 1 255{}for] dup       % string index translationArray translationArray
  [(\(o)  ([o)  (\)c)  (]c)  (/d)] % string index translationArray translationArray reencodeArray
  {                        % string index translationArray translationArray translationString
    {}forall               % string index translationArray translationArray charCode newCharCode
    put dup                % string index translationArray translationArray
  }forall                  % string index translationArray translationArray
  pop                      % string index translationArray
  3 copy pop               % string index translationArray string index
  get                      % string index translationArray charCode
  get                      % string index translatedCharCode
  put                      % -/-
}for

% Now we can actually start interpreting the string
% We use the stack for storing numbers we read and the dictionary stack for operators that are "waiting"
{                          % number*
  s token not{exit}if      % number* string token
  exch /s exch store       % number* token
  % We try to interpret the token as a number
  {cvr}stopped{            % number* token
    % If interpretation as number fails, we have an operator
    load                   % number* opDict
    % Compare operator precedence with last operator on dictstack
    dup /p get             % number* opDict opPrec
    p                      % number* opDict opPrec prevOpPrec
    le {                   % number* opDict
      % If the last operator on the stack has at least the same precedence, execute it
      currentdict end      % number* opDict prevOpDict
      exch begin           % number* prevOpDict
      /e get exec          % number*
    }{                     % number* opDict
      % If last operator doesn't have higher precedence, put the new operator on the dictstack as well
      begin
    }ifelse
  }if
}loop
% If we're finished with interpreting the string, execute all operators that are left on the dictstack
{{e end}stopped{exit}if}loop
=

TODO: Right-associativity of exponentation

\$\endgroup\$
  • \$\begingroup\$ Ah... The dictstack: brilliant! \$\endgroup\$ – luser droog Oct 17 '12 at 22:12
  • \$\begingroup\$ I'm allowed to comment on stackoverflow, so I was a little confused. Is it normal that the reputation is managed separately, or did I screw up my logins? \$\endgroup\$ – Thomas W. Oct 18 '12 at 6:16
  • \$\begingroup\$ I wanted to tell you that there must be something wrong with your solution because all three test cases given above fail. However, I didn't try to understand what you're doing yet (some comments would be cool ;-)). \$\endgroup\$ – Thomas W. Oct 18 '12 at 6:19
  • \$\begingroup\$ 1) Once you hit 200 on any site, you'll start at 101 on every site. Or hit 50 here. 2) AUGHH! I thought it was a quick extension of the Basic Calculator. I didn't even see that brackets are required! And I didn't test it very well. Oh, well; pants down, at least my undies are clean! \$\endgroup\$ – luser droog Oct 18 '12 at 6:37
  • \$\begingroup\$ @luserdroog: "@ThomasW" does not invite me to comment. \$\endgroup\$ – Thomas W. Oct 19 '12 at 16:04
1
\$\begingroup\$

Python 2,339 335 bytes

import re
x,s=input(),re.sub
def f(y):
 y,r=s('- ','+ -',y).split(),['^','*','/','+','-']
 for c in r:
  while c in y:d=y.index(c)-1;a,b=map(float,[y[d],y[d+2]]);y=y[:d]+[((a,-a)[a<0]**b,a*b,a/b,a+b,a-b)[r.index(c)]]+y[d+3:]
 return`y[0]`
w=lambda b:s("[([]+[\d+\-*/^ .]*[)\]]",lambda m:f(m.group()[1:]),s(' +',' ',b))
print f(w(w(x)))

Try it online!

  • -4 bytes by changing str(x) with backticks ``!
\$\endgroup\$
0
\$\begingroup\$

Postscript, 1000 695 665 494

Stole ideas from ThomasW. Added feature: accepts strings with or without spaces around operators.[feature removed]


Using ARGUMENTS is shorter than %stdin, and easier to test, to boot!


Simplified the substitution to just replace brackets with parens.

575(1)10:36 PM:ps 0> gsnd -q -- calc2bg.ps '10 - 3 + 2'
9
576(1)10:37 PM:ps 0> gsnd -q -- calc2bg.ps '8 + 6 / 3 - 7 + -5 / 2.5'
1.0
577(1)10:37 PM:ps 0> gsnd -q -- calc2bg.ps '4 + [ ( -3 + 5 ) * 3.5 ] ^ 2 - 12'
41.0

Code:

/T[/^[/C{exp}/P 4/X{le}>>/*[/C{mul}/P 3/X{lt}>>/[/C{div}/P
3/X{lt}>>/+[/C{add}/P 2/X{lt}>>/-[/C{sub}/P
2/X{lt}>>>>def[/integertype{}/realtype{}/stringtype{V}/nametype{cvlit/N
exch store{P T N get dup/P get exch/X get exec{exit}if C end}loop T N get
begin}91 40 93 41>>begin/V{0 1 2 index length 1 sub{2 copy get
dup where{exch get}if 3 copy put pop pop}for[/N 0/R 0/P 0/C{}>>begin{token
not{exit}if exch/R exch store dup type exec R}loop{P 0 eq{end exit}if C
end}loop}def ARGUMENTS{V ==}forall

Ungolfed and commented:

%!
%Shunting-Yard Algorithm using dictstack for operators
%invoke with %gsnd -q -- calc2bg.ps [ 'expr1' ]*

%The operator table. C:code P:precedence X:test(implements associativity)
/T[
    /^[/C{exp}/P 4/X{le}>>
    /*[/C{mul}/P 3/X{lt}>>
    /[/C{div}/P 3/X{lt}>>
    /+[/C{add}/P 2/X{lt}>>
    /-[/C{sub}/P 2/X{lt}>>
>>def

%The type-dispatch dictionary
%numbers: do nothing
%string: recurse
%name: process op
[%/integertype{}/realtype{} %now uses `where` below
/stringtype{V}/nametype{
pstack()=
    cvlit/N exch store %stash cur-op
    {
        P %prec(tos)
        T N get %prec(tos) cur-op-dict
        dup/P get %prec(tos) cur-op-dict prec(cur-op)
        exch/X get %prec(tos) prec(cur-op) test(cur-op)
        exec{exit}if %exit if prec(tos) < || <= prec(cur-op)
/C load ==
        C %pop-and-apply
        end
pstack()=
    } loop
    T N get begin %push cur-op
}>>begin

%substitutions
[91 40 93 41>>begin %replace brackets with parens
/V {
    %pre-process
    0 1 2 index length 1 sub {
        2 copy get
        dup where { exch get } if
        3 copy put pop pop
    } for
dup ==

    [/N 0/R 0/P 0/C{}>>begin %dummy base operator and storage
    { token not{exit}if exch /R exch store %extract token, stash Remainder
pstack(>)=
        %dispatch type procedure
        dup type dup where { pop exec }{ pop } ifelse
    R }loop
pstack()=
    {
        P 0 eq{end exit}if %hit dummy op: exit
/C load ==
        C end %pop and apply
    } loop
} def

ARGUMENTS{V ==}forall %iterate through the command-line arguments
\$\endgroup\$
  • \$\begingroup\$ @ThomasW I wonder if this works to invite you to comment. (?) \$\endgroup\$ – luser droog Oct 19 '12 at 6:06
  • \$\begingroup\$ I've posted a fuller implementation of the same idea in comp.lang.postscript. \$\endgroup\$ – luser droog Oct 19 '12 at 6:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.