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

• 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)? Feb 6 '11 at 18:45
• The output can have a trailing .0 on the end. I'm not too sure about the precision, but more is better. Feb 6 '11 at 20:33
• 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. Feb 6 '11 at 21:30
• Bonus for PN/RPN calculators? Mar 20 '11 at 4:49

## 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))?({char c=s=='['?'(':s==']'?')':s;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))?({
char c=s=='['?'(':s==']'?')':s;
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!

• Handles the right-associativity of the exponentiation operator, which J B's Perl solution doesn't seem to. Feb 6 '11 at 22:10
• 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.
– J B
Feb 7 '11 at 10:23
• +1 nicely golfed, but... just dropping includes, using namespace std and a main function isn't really ok, is it? Oct 17 '12 at 22:26

# PHP - 394354 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))&&$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;
function e($P) { global$s;
if (strpos(" ([",$s)){ 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)) &&$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);


# Postscript, 446

This uses the shunting yard algorithm.

[/*[/p
2/e{mul}>>/d[/p
2/e{div}>>/+[/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
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{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
% 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

• Ah... The dictstack: brilliant! Oct 17 '12 at 22:12
• 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? Oct 18 '12 at 6:16
• 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 ;-)). Oct 18 '12 at 6:19
• 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! Oct 18 '12 at 6:37
• @luserdroog: "@ThomasW" does not invite me to comment. Oct 19 '12 at 16:04

# 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:]
returny
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 !

# Postscript, 1000695665 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
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{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 %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