Reverse Polish notation

Question

You must evaluate a string written in Reverse Polish notation and output the result.

The program must accept an input and return the output. For programming languages that do not have functions to receive input/output, you can assume functions like readLine/print.

You are not allowed to use any kind of "eval" in the program.

Numbers and operators are separated by one or more spaces.

You must support at least the +, -, * and / operators.

You need to add support to negative numbers (for example, -4 is not the same thing as 0 4 -) and floating point numbers.

You can assume the input is valid and follows the rules above

Test Cases

Input:

-4 5 +

Output:

Input:

5 2 /

Output:

2.5

Input:

5 2.5 /

Output:

Input:

5 1 2 + 4 * 3 - +

Output:

Input:

4 2 5 * + 1 3 2 * + /

Output:

It's a shame no eval is allowed, otherwise the GolfScript solution is 1 character: ~. :-P — Chris Jester-Young, Jan 30 '11 at 1:49
That's why it's not allowed :-P, this question on StackOverflow received a 4 chars answer with dc. — user11, Jan 30 '11 at 1:51
@SHiNKiROU: Which language requires you to use eval to parse numbers? It sounds quite broken. (GolfScript is one such language, as far as I'm aware. I think it's broken too.) — Chris Jester-Young, Jan 30 '11 at 5:08
I think eval should be ok if it were just to convert strings to numbers. eg. in python eval(s) is better than float(s) — gnibbler, Jan 30 '11 at 10:56

Nemo157 · Accepted Answer · 2011-01-31 07:49:31Z

Ruby - 95 77 characters

a=[]
gets.split.each{|b|a<<(b=~/\d/?b.to_f: (j,k=a.pop 2;j.send b,k))}
p a[0]

Takes input on stdin.

Testing code

[
  "-4 5 +",
  "5 2 /",
  "5 2.5 /",
  "5 1 2 + 4 * 3 - +",
  "4 2 5 * + 1 3 2 * + /",
  "12 8 3 * 6 / - 2 + -20.5 "
].each do |test|
  puts "[#{test}] gives #{`echo '#{test}' | ruby golf-polish.rb`}"
end

gives

[-4 5 +] gives 1.0
[5 2 /] gives 2.5
[5 2.5 /] gives 2.0
[5 1 2 + 4 * 3 - +] gives 14.0
[4 2 5 * + 1 3 2 * + /] gives 2.0
[12 8 3 * 6 / - 2 + -20.5 ] gives 10.0

Unlike the C version this returns the last valid result if there are extra numbers appended to the input it seems.

You could shave off a character by using map instead of each — addison, Jun 21 '15 at 2:31

gnibbler · Accepted Answer · 2011-01-30 12:37:02Z

10

Python - 124 chars

s=[1,1]
for i in raw_input().split():b,a=map(float,s[:2]);s[:2]=[[a+b],[a-b],[a*b],[a/b],[i,b,a]]["+-*/".find(i)]
print s[0]

Python - 133 chars

s=[1,1]
for i in raw_input().split():b,a=map(float,s[:2]);s={'+':[a+b],'-':[a-b],'*':[a*b],'/':[a/b]}.get(i,[i,b,a])+s[2:]
print s[0]

edited Jan 30 '11 at 12:37

answered Jan 30 '11 at 11:43

gnibbler

14.2k3 gold badges43 silver badges73 bronze badges

1

\$\begingroup\$ I like the stack manipulation. \$\endgroup\$ – Alexandru Jan 30 '11 at 12:55
2

\$\begingroup\$ You can't have 0 as second operand... \$\endgroup\$ – JBernardo Dec 22 '11 at 8:36
2

\$\begingroup\$ [a/b] should be replaced with b and[a/b] so that you can have 0 as second operand. \$\endgroup\$ – flornquake Apr 14 '13 at 21:44

add a comment |

Chris Jester-Young · Accepted Answer · 2011-01-31 01:45:51Z

Scheme, 162 chars

(Line breaks added for clarity—all are optional.)

(let l((s'()))(let((t(read)))(cond((number? t)(l`(,t,@s)))((assq t
`((+,+)(-,-)(*,*)(/,/)))=>(lambda(a)(l`(,((cadr a)(cadr s)(car s))
,@(cddr s)))))(else(car s)))))

Fully-formatted (ungolfed) version:

(let loop ((stack '()))
  (let ((token (read)))
    (cond ((number? token) (loop `(,token ,@stack)))
          ((assq token `((+ ,+) (- ,-) (* ,*) (/ ,/)))
           => (lambda (ass) (loop `(,((cadr ass) (cadr stack) (car stack))
                                    ,@(cddr stack)))))
          (else (car stack)))))

Selected commentary

`(,foo ,@bar) is the same as (cons foo bar) (i.e., it (effectively^†) returns a new list with foo prepended to bar), except it's one character shorter if you compress all the spaces out.

Thus, you can read the iteration clauses as (loop (cons token stack)) and (loop (cons ((cadr ass) (cadr stack) (car stack)) (cddr stack))) if that's easier on your eyes.

`((+ ,+) (- ,-) (* ,*) (/ ,/)) creates an association list with the symbol + paired with the procedure +, and likewise with the other operators. Thus it's a simple symbol lookup table (bare words are (read) in as symbols, which is why no further processing on token is necessary). Association lists have O(n) lookup, and thus are only suitable for short lists, as is the case here. :-P

† This is not technically accurate, but, for non-Lisp programmers, it gets a right-enough idea across.

@M28: The ungolfed version, yes. I program in Scheme on a semi-regular basis (for real, serious programs). — Chris Jester-Young, Jan 30 '11 at 3:16
Unfortunately, Scheme is a verbose language and notoriously difficult to golf well. So I wouldn't be surprised to see some Perl submission beat this one. — Chris Jester-Young, Jan 30 '11 at 3:18

dmckee --- ex-moderator kitten · Accepted Answer · 2011-01-30 06:58:54Z

c -- 424 necessary character

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define O(X) g=o();g=o() X g;u(g);break;
char*p=NULL,*b;size_t a,n=0;float g,s[99];float o(){return s[--n];};
void u(float v){s[n++]=v;};int main(){getdelim(&p,&a,EOF,stdin);for(;;){
b=strsep(&p," \n\t");if(3>p-b){if(*b>='0'&&*b<='9')goto n;switch(*b){case 0:
case EOF:printf("%f\n",o());return 0;case'+':O(+)case'-':O(-)case'*':O(*)
case'/':O(/)}}else n:u(atof(b));}}

Assumes that you have a new enough libc to include getdelim in stdio.h. The approach is straight ahead, the whole input is read into a buffer, then we tokenize with strsep and use length and initial character to determine the class of each. There is no protection against bad input. Feed it "+ - * / + - ...", and it will happily pop stuff off the memory "below" the stack until it seg faults. All non-operators are interpreted as floats by atof which means zero value if they don't look like numbers.

Readable and commented:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *p=NULL,*b;
size_t a,n=0;
float g,s[99];
float o(){        /* pOp */
  //printf("\tpoping '%f'\n",s[n-1]);
  return s[--n];
};
void u(float v){  /* pUsh */
  //printf("\tpushing '%f'\n",v);
  s[n++]=v;
};
int main(){
  getdelim(&p,&a,EOF,stdin); /* get all the input */
  for(;;){
    b=strsep(&p," \n\t"); /* now *b though *(p-1) is a token and p
                 points at the rest of the input */
    if(3>p-b){
      if (*b>='0'&&*b<='9') goto n;
      //printf("Got 1 char token '%c'\n",*b);
      switch (*b) {
      case 0:
      case EOF: printf("%f\n",o()); return 0;
      case '+': g=o(); g=o()+g; u(g); break;
      case '-': g=o(); g=o()-g; u(g); break;
      case '*': g=o(); g=o()*g; u(g); break;
      case '/': g=o(); g=o()/g; u(g); break;
    /* all other cases viciously ignored */
      } 
    } else { n:
      //printf("Got token '%s' (%f)\n",b,atof(b));
      u(atof(b));
    }
  }
}

Validation:

 $ gcc -c99 rpn_golf.c 
 $ wc rpn_golf.c
  9  34 433 rpn_golf.c
 $ echo -4 5 + | ./a.out
1.000000
 $ echo 5 2 / | ./a.out
2.500000
 $ echo 5 2.5 / | ./a.out
2.000000

Heh! Gotta quote anything with * in it...

 $ echo "5 1 2 + 4 * 3 - +" | ./a.out
14.000000
 $ echo "4 2 5 * + 1 3 2 * + /" | ./a.out
2.000000

and my own test case

 $ echo "12 8 3 * 6 / - 2 + -20.5 " | ./a.out
-20.500000

You can safe some characters by replacing case with a makro. — FUZxxl, Jan 30 '11 at 14:24

marinus · Accepted Answer · 2013-04-20 01:21:56Z

7

Haskell (155)

f#(a:b:c)=b`f`a:c
(s:_)![]=print s
s!("+":v)=(+)#s!v
s!("-":v)=(-)#s!v
s!("*":v)=(*)#s!v
s!("/":v)=(/)#s!v
s!(n:v)=(read n:s)!v
main=getLine>>=([]!).words

edited Apr 20 '13 at 1:21

answered May 5 '11 at 0:00

marinus

30.2k6 gold badges62 silver badges109 bronze badges

\$\begingroup\$ You can get remove 9 characters by changing "(s:_)![]=s" to "(s:_)![]=print s" and "main=getLine>>=putStrLn.show.([]!).words" to "main=getLine>>=([]!).words" \$\endgroup\$ – Fors Apr 19 '13 at 16:25
\$\begingroup\$ And then further remove a few other characters by using a one-line case-statement. \$\endgroup\$ – Fors Apr 19 '13 at 18:29
\$\begingroup\$ s!(n:v)=case n of{"+"->(+)#s;"-"->(-)#s;"*"->(*)#s;"/"->(/)#s;_->(read n:s)}!v would save 14 characters. \$\endgroup\$ – Fors Apr 20 '13 at 12:38

add a comment |

Amro · Accepted Answer · 2015-07-29 11:56:49Z

MATLAB – 158, 147

C=strsplit(input('','s'));D=str2double(C);q=[];for i=1:numel(D),if isnan(D(i)),f=str2func(C{i});q=[f(q(2),q(1)) q(3:end)];else q=[D(i) q];end,end,q

(input is read from user input, output printed out).

Below is the code prettified and commented, it pretty much implements the postfix algorithm described (with the assumption that expressions are valid):

C = strsplit(input('','s'));         % prompt user for input and split string by spaces
D = str2double(C);                   % convert to numbers, non-numeric are set to NaN
q = [];                              % initialize stack (array)
for i=1:numel(D)                     % for each value
    if isnan(D(i))                   % if it is an operator
        f = str2func(C{i});          % convert op to a function
        q = [f(q(2),q(1)) q(3:end)]; % pop top two values, apply op and push result
    else
        q = [D(i) q];                % else push value on stack
    end
end
q                                    % show result

Bonus:

In the code above, we assume operators are always binary (+, -, *, /). We can generalize it by using nargin(f) to determine the number of arguments the operand/function requires, and pop the right amount of values from the stack accordingly, as in:

f = str2func(C{i});
n = nargin(f);
args = num2cell(q(n:-1:1));
q = [f(args{:}) q(n+1:end)];

That way we can evaluate expressions like:

str = '6 5 1 2 mean_of_three 1 + 4 * +'

where mean_of_three is a user-defined function with three inputs:

function d = mean_of_three(a,b,c)
    d = (a+b+c)/3;
end

Ming-Tang · Accepted Answer · 2011-01-30 05:16:29Z

Perl (134)

@a=split/\s/,<>;/\d/?push@s,$_:($x=pop@s,$y=pop@s,push@s,('+'eq$_?$x+$y:'-'eq$_?$y-$x:'*'eq$_?$x*$y:'/'eq$_?$y/$x:0))for@a;print pop@s

Next time, I'm going to use the recursive regexp thing.

Ungolfed:

@a = split /\s/, <>;
for (@a) {
    /\d/
  ? (push @s, $_)
  : ( $x = pop @s,
      $y = pop @s,
      push @s , ( '+' eq $_ ? $x + $y
                : '-' eq $_ ? $y - $x
                : '*' eq $_ ? $x * $y
                : '/' eq $_ ? $y / $x
                : 0 )
      )
}
print(pop @s);

I though F# is my only dream programming language...

\$\begingroup\$ I have a shorter Perl 5 implementation. \$\endgroup\$ – dolmen Jan 3 '19 at 0:48 — dolmen, Jan 3 '19 at 0:48

Joey · Accepted Answer · 2011-01-30 10:40:19Z

Windows PowerShell, 152 181 192

In readable form, because by now it's only two lines with no chance of breaking them up:

$s=@()
switch -r(-split$input){
  '\+'        {$s[1]+=$s[0]}
  '-'         {$s[1]-=$s[0]}
  '\*'        {$s[1]*=$s[0]}
  '/'         {$s[1]/=$s[0]}
  '-?[\d.]+'  {$s=0,+$_+$s}
  '.'         {$s=$s[1..($s.count)]}}
$s

2010-01-30 11:07 (192) – First attempt.

2010-01-30 11:09 (170) – Turning the function into a scriptblock solves the scope issues. Just makes each invocation two bytes longer.

2010-01-30 11:19 (188) – Didn't solve the scope issue, the test case just masked it. Removed the index from the final output and removed a superfluous line break, though. And changed double to float.

2010-01-30 11:19 (181) – Can't even remember my own advice. Casting to a numeric type can be done in a single char.

2010-01-30 11:39 (152) – Greatly reduced by using regex matching in the switch. Completely solves the previous scope issues with accessing the stack to pop it.

Sam Tobin-Hochstadt · Accepted Answer · 2011-09-21 15:41:38Z

5

Racket 131:

(let l((s 0))(define t(read))(cond[(real? t)
(l`(,t,@s))][(memq t'(+ - * /))(l`(,((eval t)(cadr s)
(car s)),@(cddr s)))][0(car s)]))

Line breaks optional.

Based on Chris Jester-Young's solution for Scheme.

answered Sep 21 '11 at 15:41

Sam Tobin-Hochstadt

1511 silver badge3 bronze badges

add a comment |

Keith Randall · Accepted Answer · 2011-01-30 05:36:54Z

4

Python, 166 characters

import os,operator as o
S=[]
for i in os.read(0,99).split():
 try:S=[float(i)]+S
 except:S=[{'+':o.add,'-':o.sub,'/':o.div,'*':o.mul}[i](S[1],S[0])]+S[2:]
print S[0]

answered Jan 30 '11 at 5:36

Keith Randall

19.8k2 gold badges38 silver badges100 bronze badges

\$\begingroup\$ Use raw_input() code isn't split over multiple lines. \$\endgroup\$ – JPvdMerwe Jan 30 '11 at 6:23
\$\begingroup\$ Then you could try: from operator import* and replace o.div with div. \$\endgroup\$ – JPvdMerwe Jan 30 '11 at 10:37

add a comment |

flornquake · Accepted Answer · 2016-06-23 19:57:58Z

4

Python 3, 119 bytes

s=[]
for x in input().split():
 try:s+=float(x),
 except:o='-*+'.find(x);*s,a,b=s;s+=(a+b*~-o,a*b**o)[o%2],
print(s[0])

Input: 5 1 1 - -7 0 * + - 2 /

Output: 2.5

(You can find a 128-character Python 2 version in the edit history.)

edited Jun 23 '16 at 19:57

answered Apr 21 '13 at 14:11

flornquake

1,4679 silver badges24 bronze badges

\$\begingroup\$ Pretty clever :) I like how you don't need / in the string. \$\endgroup\$ – Daniel Lubarov Oct 20 '13 at 19:12
\$\begingroup\$ 114 bytes \$\endgroup\$ – Erik the Outgolfer Oct 26 '17 at 18:46
\$\begingroup\$ @EriktheOutgolfer that breaks with a ZeroDivisionError when the second operand is 0 (e.g. 5 0 +). \$\endgroup\$ – flornquake Nov 1 '17 at 16:54
\$\begingroup\$ You can save 1 character by using the ord(x) - 42 method. \$\endgroup\$ – frederick99 May 26 '19 at 4:54
\$\begingroup\$ @frederick99 I don't see how. \$\endgroup\$ – flornquake Jul 22 '19 at 21:07

| show 5 more comments

user11user11 · Accepted Answer · 2011-01-30 03:11:46Z

3

JavaScript (157)

This code assumes there are these two functions: readLine and print

a=readLine().split(/ +/g);s=[];for(i in a){v=a[i];if(isNaN(+v)){f=s.pop();p=s.pop();s.push([p+f,p-f,p*f,p/f]['+-*/'.indexOf(v)])}else{s.push(+v)}}print(s[0])

answered Jan 30 '11 at 3:11

user11

\$\begingroup\$ Shorter if you use prompt() instead of readLine() (and perhaps alert() instead of print() to match prompt()). \$\endgroup\$ – nyuszika7h Aug 21 '14 at 19:00

add a comment |

J B · Accepted Answer · 2011-02-04 00:21:27Z

Perl, 128

This isn't really competitive next to the other Perl answer, but explores a different (suboptimal) path.

perl -plE '@_=split" ";$_=$_[$i],/\d||
do{($a,$b)=splice@_,$i-=2,2;$_[$i--]=
"+"eq$_?$a+$b:"-"eq$_?$a-$b:"*"eq$_?
$a*$b:$a/$b;}while++$i<@_'

Characters counted as diff to a simple perl -e '' invocation.

Thomas O · Accepted Answer · 2011-01-30 11:55:44Z

2

Python, 161 characters:

from operator import*;s=[];i=raw_input().split(' ')
q="*+-/";o=[mul,add,0,sub,0,div]
for c in i:
 if c in q:s=[o[ord(c)-42](*s[1::-1])]+s 
 else:s=[float(c)]+s
print(s[0])

answered Jan 30 '11 at 11:55

Thomas O

3,03420 silver badges33 bronze badges

add a comment |

Kevin Brown · Accepted Answer · 2011-01-31 02:09:17Z

PHP, 439 265 263 262 244 240 characters

<? $c=fgets(STDIN);$a=array_values(array_filter(explode(" ",$c)));$s[]=0;foreach($a as$b){if(floatval($b)){$s[]=$b;continue;}$d=array_pop($s);$e=array_pop($s);$s[]=$b=="+"?$e+$d:($b=="-"?$e-$d:($b=="*"?$e*$d:($b=="/"?$e/$d:"")));}echo$s[1];

This code should work with stdin, though it is not tested with stdin.

It has been tested on all of the cases, the output (and code) for the last one is here:
http://codepad.viper-7.com/fGbnv6

Ungolfed, ~~314~~ ~~330~~ 326 characters

<?php
$c = fgets(STDIN);
$a = array_values(array_filter(explode(" ", $c)));
$s[] = 0;
foreach($a as $b){
    if(floatval($b)){
        $s[] = $b;
        continue;
    }
    $d = array_pop($s);
    $e = array_pop($s);
    $s[] = $b == "+" ? $e + $d : ($b == "-" ? $e - $d : ($b == "*" ? $e * $d : ($b == "/" ? $e / $d :"")));
}
echo $s[1];

Quote from the task description: »For programming languages that do not have functions to receive input/output, you can assume functions like readLine/print.« – demonstrably PHP has functions to do so, therefore the assumption is incorrect. — Joey, Jan 30 '11 at 10:11

Geoff Reedy · Accepted Answer · 2013-04-20 04:20:58Z

2

flex - 157

%{
float b[100],*s=b;
#define O(o) s--;*(s-1)=*(s-1)o*s;
%}
%%
-?[0-9.]+ *s++=strtof(yytext,0);
\+ O(+)
- O(-)
\* O(*)
\/ O(/)
\n printf("%g\n",*--s);
.
%%

If you aren't familiar, compile with flex rpn.l && gcc -lfl lex.yy.c

answered Apr 20 '13 at 4:20

Geoff Reedy

2,82811 silver badges16 bronze badges

add a comment |

Daniel Lubarov · Accepted Answer · 2014-09-15 19:43:00Z

2

Python, 130 characters

Would be 124 characters if we dropped b and (which some of the Python answers are missing). And it incorporates 42!

s=[]
for x in raw_input().split():
 try:s=[float(x)]+s
 except:b,a=s[:2];s[:2]=[[a*b,a+b,0,a-b,0,b and a/b][ord(x)-42]]
print s[0]

edited Sep 15 '14 at 19:43

answered Oct 20 '13 at 8:34

Daniel Lubarov

3011 silver badge9 bronze badges

\$\begingroup\$ Really nice answer. But I count 130 characters. ;) \$\endgroup\$ – flornquake Sep 15 '14 at 10:02
\$\begingroup\$ @flornquake you're right, thanks for the correction. \$\endgroup\$ – Daniel Lubarov Sep 15 '14 at 19:44

add a comment |

mbomb007 · Accepted Answer · 2015-07-28 20:16:53Z

2

Python 3, 126 132 chars

s=[2,2]
for c in input().split():
    a,b=s[:2]
    try:s[:2]=[[a+b,b-a,a*b,a and b/a]["+-*/".index(c)]]
    except:s=[float(c)]+s
print(s[0])

There have been better solutions already, but now that I had written it (without having read the prior submissions, of course - even though I have to admit that my code looks as if I had copypasted them together), I wanted to share it, too.

edited Jul 28 '15 at 20:16

mbomb007

21.9k5 gold badges50 silver badges121 bronze badges

answered May 5 '11 at 18:39

cemper93

6705 silver badges8 bronze badges

\$\begingroup\$ b/a should be replaced with a and b/a, otherwise this solution won't work if the second operand is 0 (e.g. 4 0 -). \$\endgroup\$ – flornquake Apr 20 '13 at 10:51
\$\begingroup\$ @flornquake Fixed it for him. \$\endgroup\$ – mbomb007 Jul 28 '15 at 20:17

add a comment |

Jerry Jeremiah · Accepted Answer · 2015-07-30 03:45:04Z

c99 gcc 235

This works for me (with warnings):

#include <stdlib.h>
#define O(x):--d;s[d]=s[d]x s[d+1];break;
float s[99];main(c,v)char**v;{for(int i=1,d=0;i<c;i++)switch(!v[i][1]?*v[i]:' '){case'+'O(+)case'-'O(-)case'*'O(*)case'/'O(/)default:s[++d]=atof(v[i]);}printf("%f\n",s[1]);}

But if you are compiling it with mingw32 you need to turn off globbing (see https://www.cygwin.com/ml/cygwin/1999-11/msg00052.html) by compiling like this:

gcc -std=c99 x.c C:\Applications\mingw32\i686-w64-mingw32\lib\CRT_noglob.o

If you don't * is automatically expanded by the mingw32 CRT.

Does anybody know how to turn break;case'*':s[--d]*=s[d+1]; into a macro that accepts the character + as a parameter because then all four cases would just be O(+)O(-)O(*)O(/)

H:\Desktop>gcc -std=c99 x.c C:\Applications\mingw32\i686-w64-mingw32\lib\CRT_noglob.o
x.c:3:13: warning: return type defaults to 'int'
 float s[99];main(c,v)char**v;{for(int i=1,d=0;i<c;i++)switch(!v[i][1]?*v[i]:' '){case'+'O(+)case'-'O(-)case'*'O(*)case'/'O(/)default:s[++d]=atof(v[i]);}printf("%f\n",s[1]);}
x.c: In function 'main':
x.c:3:13: warning: type of 'c' defaults to 'int'
x.c:3:1: warning: implicit declaration of function 'atof' [-Wimplicit-function-declaration]
 float s[99];main(c,v)char**v;{for(int i=1,d=0;i<c;i++)switch(!v[i][1]?*v[i]:' '){case'+'O(+)case'-'O(-)case'*'O(*)case'/'O(/)default:s[++d]=atof(v[i]);}printf("%f\n",s[1]);}
x.c:3:1: warning: implicit declaration of function 'printf' [-Wimplicit-function-declaration]
x.c:3:153: warning: incompatible implicit declaration of built-in function 'printf'
 float s[99];main(c,v)char**v;{for(int i=1,d=0;i<c;i++)switch(!v[i][1]?*v[i]:' '){case'+'O(+)case'-'O(-)case'*'O(*)case'/'O(/)default:s[++d]=atof(v[i]);}printf("%f\n",s[1]);}
H:\Desktop>a -4 5 +
1.000000
H:\Desktop>a 5 2 /
2.500000
H:\Desktop>a 5 2.5 /
2.000000
H:\Desktop>a 5 1 2 + 4 * 3 - +
14.000000
H:\Desktop>a 4 2 5 * + 1 3 2 * + /
2.000000

Cole Cameron · Accepted Answer · 2015-07-30 22:12:26Z

C, 232 229 bytes

Fun with recursion.

#include <stdlib.h>
#define b *p>47|*(p+1)>47
char*p;float a(float m){float n=strtof(p,&p);b?n=a(n):0;for(;*++p==32;);m=*p%43?*p%45?*p%42?m/n:m*n:m-n:m+n;return*++p&&b?a(m):m;}main(c,v)char**v;{printf("%f\n",a(strtof(v[1],&p)));}

Ungolfed:

#include <stdlib.h>

/* Detect if next char in buffer is a number */
#define b *p > 47 | *(p+1) > 47

char*p; /* the buffer */

float a(float m)
{
    float n = strtof(p, &p); /* parse the next number */

    /* if the next thing is another number, recursively evaluate */
    b ? n = a(n) : 0;

    for(;*++p==32;); /* skip spaces */

    /* Perform the arithmetic operation */
    m = *p%'+' ? *p%'-' ? *p%'*' ? m/n : m*n : m-n : m+n;

    /* If there's more stuff, recursively parse that, otherwise return the current computed value */
    return *++p && b ? a(m) : m;
}

int main(int c, char **v)
{
    printf("%f\n", a(strtof(v[1], &p)));
}

Test Cases:

$ ./a.out "-4 5 +"
1.000000
$ ./a.out "5 2 /"
2.500000
$ ./a.out "5 2.5 /"
2.000000
$ ./a.out "5 1 2 + 4 * 3 - +"
14.000000
$ ./a.out "4 2 5 * + 1 3 2 * + /"
2.000000

Downgoat · Accepted Answer · 2015-12-05 18:05:41Z

2

JavaScript ES7, 119 bytes

I'm getting a bug with array comprehensions so I've used .map

(s,t=[])=>(s.split` `.map(i=>+i?t.unshift(+i):t.unshift((r=t.pop(),o=t.pop(),[r+o,r-o,r*o,r/o]['+-*/'.indexOf(i)]))),t)

Try it online at ESFiddle

edited Dec 5 '15 at 18:05

answered Jul 28 '15 at 20:13

Downgoat

27.1k6 gold badges66 silver badges152 bronze badges

\$\begingroup\$ Is there an ES7 interpreter available? \$\endgroup\$ – Conor O'Brien Dec 3 '15 at 18:12
\$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ this should work on Firefox. You could try babeljs.io/repl \$\endgroup\$ – Downgoat Dec 3 '15 at 18:28
\$\begingroup\$ Oh, I see. ^_^ Thanks! \$\endgroup\$ – Conor O'Brien Dec 3 '15 at 18:36

add a comment |

Aurel Bílý · Accepted Answer · 2011-01-30 17:25:43Z

1

PHP - 259 characters

$n=explode(" ",$_POST["i"]);$s=array();for($i=0;$i<count($n);$s=$d-->0?array_merge($s,!$p?array($b,$a,$c):array($p)):$s){if($c=$n[$i++]){$d=1;$a=array_pop($s);$b=array_pop($s);$p=$c=="+"?$b+$a:($c=="-"?$b-$a:($c=="*"?$b*$a:($c=="/"?$b/$a:false)));}}echo$s[2];

Assuming input in POST variable i.

answered Jan 30 '11 at 17:25

Aurel Bílý

1,0839 silver badges8 bronze badges

2

\$\begingroup\$ Quoted from the original description »For programming languages that do not have functions to receive input/output, you can assume functions like readLine/print.« PHP has a way to get stdin through streams. \$\endgroup\$ – Kevin Brown Jan 30 '11 at 19:02

add a comment |

MiffTheFox · Accepted Answer · 2011-02-05 14:28:48Z

C# - 392 characters

namespace System.Collections.Generic{class P{static void Main(){var i=Console.ReadLine().Split(' ');var k=new Stack<float>();float o;foreach(var s in i)switch (s){case "+":k.Push(k.Pop()+k.Pop());break;case "-":o=k.Pop();k.Push(k.Pop()-o);break;case "*":k.Push(k.Pop()*k.Pop());break;case "/":o=k.Pop();k.Push(k.Pop()/o);break;default:k.Push(float.Parse(s));break;}Console.Write(k.Pop());}}}

However, if arguments can be used instead of standard input, we can bring it down to

C# - 366 characters

namespace System.Collections.Generic{class P{static void Main(string[] i){var k=new Stack<float>();float o;foreach(var s in i)switch (s){case "+":k.Push(k.Pop()+k.Pop());break;case "-":o=k.Pop();k.Push(k.Pop()-o);break;case "*":k.Push(k.Pop()*k.Pop());break;case "/":o=k.Pop();k.Push(k.Pop()/o);break;default:k.Push(float.Parse(s));break;}Console.Write(k.Pop());}}}

You can save 23 characters with a little optimization: 1. remove the namespace trick, explicitly qualify the two types that need it. You save the "namespace" keyword and corresponding brackets. 2. Remove spaces between string[] and i, case keywords and labels, switch and its parens. 3. Get rid of float o and simply use math to get the right results (ie. -k.Pop()+k.Pop() for minus, and 1/k.Pop()*k.Pop() for divide. — MikeP, May 5 '11 at 3:33

user unknown · Accepted Answer · 2011-12-21 19:47:42Z

Scala 412 376 349 335 312:

object P extends App{
def p(t:List[String],u:List[Double]):Double={
def a=u drop 2
t match{
case Nil=>u.head
case x::y=>x match{
case"+"=>p(y,u(1)+u(0)::a)
case"-"=>p(y,u(1)-u(0)::a)
case"*"=>p(y,u(1)*u(0)::a)
case"/"=>p(y,u(1)/u(0)::a)
case d=>p(y,d.toDouble::u)}}}
println(p((readLine()split " ").toList,Nil))}

golfer9338 · Accepted Answer · 2013-10-19 08:13:57Z

Python - 206

import sys;i=sys.argv[1].split();s=[];a=s.append;b=s.pop
for t in i:
 if t=="+":a(b()+b())
 elif t=="-":m=b();a(b()-m)
 elif t=="*":a(b()*b())
 elif t=="/":m=b();a(b()/m)
 else:a(float(t))
print(b())

Ungolfed version:

# RPN

import sys

input = sys.argv[1].split()
stack = []

# Eval postfix notation
for tkn in input:
    if tkn == "+":
        stack.append(stack.pop() + stack.pop())
    elif tkn == "-":
        tmp = stack.pop()
        stack.append(stack.pop() - tmp)
    elif tkn == "*":
        stack.append(stack.pop() * stack.pop())
    elif tkn == "/":
        tmp = stack.pop()
        stack.append(stack.pop()/tmp)
    else:
        stack.append(float(tkn))

print(stack.pop())

Input from command-line argument; output on standard output.

Ingo Bürk · Accepted Answer · 2014-09-16 19:13:29Z

ECMAScript 6 (131)

Just typed together in a few seconds, so it can probably be golfed further or maybe even approached better. I might revisit it tomorrow:

f=s=>(p=[],s.split(/\s+/).forEach(t=>+t==t?p.push(t):(b=+p.pop(),a=+p.pop(),p.push(t=='+'?a+b:t=='-'?a-b:t=='*'?a*b:a/b))),p.pop())

mbomb007 · Accepted Answer · 2015-07-28 20:18:08Z

1

C# - 323 284 241

class P{static void Main(string[] i){int x=0;var a=new float[i.Length];foreach(var s in i){var o="+-*/".IndexOf(s);if(o>-1){float y=a[--x],z=a[--x];a[x++]=o>3?z/y:o>2?z*y:o>1?z-y:y+z;}else a[x++]=float.Parse(s);}System.Console.Write(a[0]);}}

Edit: Replacing the Stack with an Array is way shorter

Edit2: Replaced the ifs with a ternary expression

edited Jul 28 '15 at 20:18

mbomb007

21.9k5 gold badges50 silver badges121 bronze badges

answered Dec 21 '11 at 15:22

kev

1913 bronze badges

\$\begingroup\$ string[] i=>string[]i. \$\endgroup\$ – Zacharý Jul 27 '17 at 18:06

add a comment |

mbomb007 · Accepted Answer · 2015-07-28 20:19:37Z

Python 2

I've tried out some different approaches to the ones published so far. None of these is quite as short as the best Python solutions, but they might still be interesting to some of you.

Using recursion, 146

def f(s):
 try:x=s.pop();r=float(x)
 except:b,s=f(s);a,s=f(s);r=[a+b,a-b,a*b,b and a/b]['+-*'.find(x)]
 return r,s
print f(raw_input().split())[0]

Using list manipulation, 149

s=raw_input().split()
i=0
while s[1:]:
 o='+-*/'.find(s[i])
 if~o:i-=2;a,b=map(float,s[i:i+2]);s[i:i+3]=[[a+b,a-b,a*b,b and a/b][o]]
 i+=1
print s[0]

Using `reduce()`, 145

print reduce(lambda s,x:x in'+-*/'and[(lambda b,a:[a+b,a-b,a*b,b and a/b])(*s[:2])['+-*'.find(x)]]+s[2:]or[float(x)]+s,raw_input().split(),[])[0]

Luis Mendo · Accepted Answer · 2015-07-29 14:30:10Z

1

Matlab, 228

F='+-/*';f={@plus,@minus,@rdivide,@times};t=strsplit(input('','s'),' ');i=str2double(t);j=~isnan(i);t(j)=num2cell(i(j));while numel(t)>1
n=find(cellfun(@(x)isstr(x),t),1);t{n}=bsxfun(f{t{n}==F},t{n-2:n-1});t(n-2:n-1)=[];end
t{1}

Ungolfed:

F = '+-/*'; %// possible operators
f = {@plus,@minus,@rdivide,@times}; %// to be used with bsxfun
t = strsplit(input('','s'),' '); %// input string and split by one or multiple spaces
i = str2double(t); %// convert each split string to number
j =~ isnan(i); %// these were operators, not numbers ...
t(j) = num2cell(i(j)); %// ... so restore them
while numel(t)>1
    n = find(cellfun(@(x)isstr(x),t),1); %// find left-most operator
    t{n} = bsxfun(f{t{n}==F}, t{n-2:n-1}); %// apply it to preceding numbers and replace
    t(n-2:n-1)=[]; %// remove used numbers
end
t{1} %// display result

edited Jul 29 '15 at 14:30

answered Jul 29 '15 at 11:36

Luis Mendo

86.7k8 gold badges101 silver badges314 bronze badges

\$\begingroup\$ You can save 2 more bytes by putting everything onto one line (or use a text editor which only uses one character for newline) \$\endgroup\$ – Hoki Jul 29 '15 at 13:28
\$\begingroup\$ @Hoki I'm only using new lines when not breaking the line would require a ;. So I think the byte count is the same \$\endgroup\$ – Luis Mendo Jul 29 '15 at 13:50
\$\begingroup\$ not exactly, most window text editors use cr+lf for a newline, which is 2 characters. My notepad++ counted 230 characters in your 3 lines version, but only 128 if I stick everything in one line (removed 2*2=4 characters from the 2 newlines, and added two ;). Try it yourself ;) \$\endgroup\$ – Hoki Jul 29 '15 at 14:06
\$\begingroup\$ @Hoki You are right. In fact, if I paste the three-line version on mothereff.in/byte-counter (which is what I used for counting text bytes), it gives 228. And of course that's also what I get from putting it all in a single line. I don't know where I got the number 230 from. Thanks! Corrected \$\endgroup\$ – Luis Mendo Jul 29 '15 at 14:29

add a comment |

kirbyfan64sos · Accepted Answer · 2015-07-30 23:11:40Z

1

K5, 70 bytes

`0:*{$[-9=@*x;((*(+;-;*;%)@"+-*/"?y).-2#x;x,.y)@47<y;(.x;.y)]}/" "\0:`

I'm not sure when K5 was released, so this might not count. Still awesome!

answered Jul 30 '15 at 23:11

kirbyfan64sos

8,7301 gold badge19 silver badges40 bronze badges

add a comment |

Reverse Polish notation

Test Cases

43 Answers 43

Ruby - 95 77 characters

Testing code

Python - 124 chars

Scheme, 162 chars

c -- 424 necessary character

Haskell (155)

MATLAB – 158, 147

Bonus:

Perl (134)

Windows PowerShell, 152 181 192

Python, 166 characters

Python 3, 119 bytes

JavaScript (157)

Perl, 128

PHP, 439 265 263 262 244 240 characters

flex - 157

Python, 130 characters

Python 3, 126 132 chars

c99 gcc 235

C, 232 229 bytes

Ungolfed:

Test Cases:

JavaScript ES7, 119 bytes

PHP - 259 characters

C# - 392 characters

C# - 366 characters

Scala 412 376 349 335 312:

Python - 206

ECMAScript 6 (131)

C# - 323 284 241

Python 2

Using recursion, 146

Using list manipulation, 149

Using reduce(), 145

Matlab, 228

K5, 70 bytes

Your Answer

Sign up or log in

Post as a guest

Linked

Related

Hot Network Questions

Using `reduce()`, 145