41
\$\begingroup\$

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:

1

Input:

5 2 /

Output:

2.5

Input:

5 2.5 /

Output:

2

Input:

5 1 2 + 4 * 3 - +

Output:

14

Input:

4 2 5 * + 1 3 2 * + /

Output:

2
\$\endgroup\$
  • 8
    \$\begingroup\$ It's a shame no eval is allowed, otherwise the GolfScript solution is 1 character: ~. :-P \$\endgroup\$ – Chris Jester-Young Jan 30 '11 at 1:49
  • 5
    \$\begingroup\$ That's why it's not allowed :-P, this question on StackOverflow received a 4 chars answer with dc. \$\endgroup\$ – user11 Jan 30 '11 at 1:51
  • 1
    \$\begingroup\$ @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.) \$\endgroup\$ – Chris Jester-Young Jan 30 '11 at 5:08
  • 3
    \$\begingroup\$ How is -4 not the same as 0 4 - ? \$\endgroup\$ – Keith Randall Jan 30 '11 at 5:18
  • 1
    \$\begingroup\$ 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) \$\endgroup\$ – gnibbler Jan 30 '11 at 10:56

43 Answers 43

1
\$\begingroup\$

C++, 265 bytes

Worse than first thought, looking for improvements.

#include<iostream>
#include<string>
#include<stack>
#define G s.top();s.pop()
using namespace std;int main(){string t; stack<float>s;while(cin>>t)if(47<t.back()&t.back()<58)s.push(stof(t));else{float a,b=G;a=G;s.push(t=="+"?a+b:t=="-"?a-b:t=="*"?a*b:a/b);}cout<<G;}

Usage

Run -> input -> enter -> Ctrl+Z -> enter  (windows)
                      -> Ctrl+D           (unix)

Ungolfed

#include <iostream>
#include <string>
#include <stack>
#define G s.top(); s.pop()
using namespace std;

int main()
{
    string t;
    stack<float> s;
    while (cin >> t)
    {
        if (47 < t.back() & t.back() < 58)
            s.push(stof(t));
        else
        {
            float a, b = G;
            a = G;
            s.push(t=="+" ? a+b : t=="-" ? a-b : t=="*" ? a*b : a/b);
        }
    }
    cout << G;
}
\$\endgroup\$
1
\$\begingroup\$

Perl, 159

sub c{pop@s}sub z{push@s,$_[0]}while(<>){($_,$a)=/(\S*) ?(.*)/;z$_ if/\d/;z(('-'eq$_?- c:c)+c)if/[+-]/;z(('/'eq$_?1/c:c)*c)if/[*\/]/;redo if$_=$a;print c."\n"}

And here's the ungolfed version:

#!/usr/bin/perl

sub c{pop @stack}
sub z{push @stack,$_[0]}
while (<>) {
    ($_, $a) = /(\S*) ?(.*)/;
    z$_ if /\d/;
    z(('-'eq$_?- c:c)+c) if /[+-]/;
    z(('/'eq$_?1/c:c)*c) if /[*\/]/;
    redo if $_=$a;
    print c . "\n"
}

Not really much to look at, but I'm pretty happy with it. I managed to at least beat the Scheme version :)

\$\endgroup\$
1
\$\begingroup\$

Mathetmatica, 143 bytes

Last@Flatten[#~ImportString~"CSV"&/@StringSplit@#]//.{{a___,b_,c_,o_String,d___}:>{a,o[b,c],d},"+"->Plus,"*"->Times,"/"->Divide,"-"->Subtract}&

Anonymous function, takes a string as input (StringSplit[#]), splits at whitespace, ImportString[#,"CSV"] acts on each element separately (it's like a soft form of eval), converting number-like strings to numbers, however operators remain as strings.

//. - repeatedly apply replacement rule: go through the input list, until you hit an operator character, e.g. {1, 4, 2, / *} becomes {1 /[4,2] *}, then {*[1, /[4,2]]}.

String-forms of operators are replaced with the names of the actual Mathematica functions which do the required thing. Output is a number.

\$\endgroup\$
  • \$\begingroup\$ I'm disappointed Mathematica doesn't have a builtin ... \$\endgroup\$ – wastl Aug 1 '18 at 12:44
  • \$\begingroup\$ Last must be applied to the whole expression, not just the input: Last[Flatten[#~ImportString~"CSV" & /@ StringSplit@#] //. {{a___, b_, c_, o_String, d___} :> {a, o[b, c], d}, "+" -> Plus, "*" -> Times, "/" -> Divide, "-" -> Subtract}] &. 142 bytes \$\endgroup\$ – Roman Aug 31 at 16:47
1
\$\begingroup\$

R, 132 105 96 bytes

for(i in scan(,""))F="if"(grepl("[0-9]",i),c(as.double(i),F),c(get(i)(F[2],F[1]),F[-1:-2]));F[1]

Try it online!

Port of Amro's Matlab answer. I never realized the two languages had so much in common. Saved 27 bytes thanks to Giuseppe ! See edit history for test cases.

\$\endgroup\$
  • \$\begingroup\$ 128 bytes \$\endgroup\$ – Giuseppe Aug 1 '18 at 16:53
  • \$\begingroup\$ using scan(,"") to split the input string (and changing to a full program) is probably a good golf; it would take input as 1 3 + instead of "1 3 +" \$\endgroup\$ – Giuseppe Aug 1 '18 at 16:55
  • \$\begingroup\$ @Giuseppe it is a good golf indeed! \$\endgroup\$ – JayCe Aug 1 '18 at 16:59
1
\$\begingroup\$

Runic Enchantments, 118 bytes

?!/rRlril1-{=
R:0q}"+0"{:}≠?\"-0"{:}≠?\"*0"{:}≠?\"/0"{≠?\R}l1=?!@
\r\ /<?6+{{~{~/?7-S{{~{~/?8 *{{~{~/?7,S{{~/\

Try it online!

Runic already operates in Reverse Polish Notation, so its just a matter of reading the input and converting from char-based symbols to actual operators.

Due to the near-perfect space usage on the lower line, ≠?\ works out to the same number of bytes as =?!\, but is easier to read.

Explanation

    /<                                                Entry
?!\rRlril1-{=                                         Read all inputs
/r/                                                   Reverse the stack (we need to parse from front to back, not back to front; mirrors flipped to preserve visual flow direction within the explanation)
R                                                     Initial parsing loop entry
 :                                                    Duplicate
  0q}                                                 Concat TOS with a 0 on the end
     "+0"                                             Construct string +0 (checking for addition)
         {:}                                          RoL, Dup, RoR (this allows the same i0 string concatenation to be reused)
            ≠?\                                       Compare, if not equal, continue
               "-0"{:}≠?\"*0"{:}≠?\"/0"{≠?\           Do the same for -, *, and /
                                           R          Bottom-of-loop entry
                                            }         Rotate numerical value to bottom of stack
                                             l1=?!@   If stack is only 1 object, print and terminate
           ~{~/                                       If equal, pop no-longer-needed i0 concatenations and the original input char
        +{{                                           Add most recent 2 values
      ?6                                              Skip to bottom-of-loop
               ?7-S{{~{~/?8 *{{~{~/?7,S{{~/           Similar chunks for -, *, and /
                                           \          Mirror up to bottom of main loop (after-math skips wind up here)
                                     ,S{{~            Note that division does not need to pop no-longer-needed concatenated string, as we used up the last one in the comparison

Invalid input characters will be treated as their decimal equivalents because chars implicitly convert to ints. Strings will crash.

Operators must be compared with their string equivalents, again, because chars implicitly convert to ints. A numerical 43 is identical to the character +. 0q is the shortest method of generating a unique string representation of the stack object that can be compared with known expected strings. Additionally a string may not be the ToS when constructing a new string or the two strings are automatically concatenated.

\$\endgroup\$
0
\$\begingroup\$

Python 2.7 (205 bytes)

Edit: Version 2. After consideration I was able to shave off a lot by using the operator module:

from operator import *
f={'*':mul,'/':div,'+':add,'-':sub}
def e(r):
    l=[]
    for i in r:
        try:i=float(i);l.append(i)
        except:l.append(f[i](*l[-2:]));del l[-3:-1]
    return l
print e(raw_input().split())[0]
\$\endgroup\$
0
\$\begingroup\$

Java 243

Input comes from the command line. Element 0 in the Float[ ] isn't actually used for storing the inputs, however it is needed for the first assignment of the temp value. The Float constructor takes care of parsing for negative values and values with a decimal place.

interface R{static void main(String[]a){Float t,f[]=new Float[a.length];int i=0;for(String s:a){t=f[i];switch(s){case"-":t=-t;case"+":f[--i]+=t;break;case"/":t=1/t;case"*":f[--i]*=t;break;default:f[++i]=new Float(s);}}System.out.print(f[i]);}}

Ungolfed:

interface ReversePolishNotation{
    static void main(String[]arg){
        Float temp, fVals[]=new Float[arg.length];
        int i=0;
        for(String str:arg){
            temp=fVals[i];
            switch(str){
                case"-":
                    temp=-temp;
                case"+":
                    fVals[--i]+=temp; break;
                case"/":
                    temp=1/temp;
                case"*":
                    fVals[--i]*=temp; break;
                default:
                    fVals[++i]=new Float(str);
            }
        }
        System.out.print(fVals[i]);
    }
}
\$\endgroup\$
  • \$\begingroup\$ @RikerW how do you mean? If it's a style issue, I don't see the harm in leaving it the way it is. \$\endgroup\$ – Jack Ammo Jan 28 '16 at 2:36
  • \$\begingroup\$ Oh NVM. :P I was thinking about the ungolfed version. Oops, sorry. \$\endgroup\$ – Rɪᴋᴇʀ Jan 28 '16 at 2:51
0
\$\begingroup\$

05AB1E, 32 30 bytes

#vyDd_iD'+Qi\+ëD'-Qi\-ë'*Qi*ë/

Try it online or verify all test cases.

Explanation:

#                  # Split the (implicit) input on spaces
 vy                # Loop `y` over each item:
   D               #  Duplicate `y` so its now twice on the stack
    d_i            #  If it's not a digit:
       D'+Qi       #   If it's a '+':
            \      #    Remove the duplicated '+' that's still on the stack
             +     #    Add the top two numbers together
       ëD'-Qi      #   Else-if it's a '-':
             \     #    Remove the duplicated '-' that's still on the stack
              -    #    Subtract the top two numbers from each other
       ë'*Qi       #   Else-if it's a '*':
            *      #    Multiply the top two numbers together
       ë           #   Else (it's a '/'):
        /          #    Divide the top two numbers
                   # (Implicitly output the result)

If eval would have been allowed, it's 14 bytes instead:

TF'-N+N'(+:}.V

Try it online or verify all test cases.

Explanation:

                # Take the string input (implicit)
TF         }    # Loop `N` in the range [0, 10):
  '-N+    :     #  Replace "-N" (where N is the current number of the loop) with:
      N'(+      #   "N(" (where N is again the current number of the loop)
.V              # Eval the string as 05AB1E code (and implicitly output the result)

Negative numbers are indicated with a trailing ( instead of leading - in 05AB1E. Apart from that the calculations are also done in Reverse Polish Notation style.

\$\endgroup\$
0
\$\begingroup\$

Kotlin, 175 bytes

{var s=List(0){0f}
for(t in it.split(" ")){try{s=s+t.toFloat()}catch(e:Exception){val(a,b)=s.takeLast(2)
s=s.dropLast(2)+listOf(a+b,a-b,a*b,a/b)["+-*/".indexOf(t)]}}
s.last()}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Dart, 196 bytes

F(l,n)=>l.removeAt(l.length-1-n);G(a,b,c)=>c=='+'?a+b:c=='-'?a-b:c=='*'?a*b:a/b;f(s){var l=[];s.split(' ').forEach((a){l.add('+-*/'.contains(a)?G(F(l,1),F(l,0),a):double.parse(a));});return l[0];}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Perl 5.10+: 95 bytes

perl '-anEmy@a;push@a,/\d/?$_:do{$j=pop@a;$i=pop@a;($i*$j,$i+$j,0,$i-$j,0,$i/$j)[-42+ord]}for@F;say$a[0]'

Size 95 bytes (diff with perl -e '' which is 10 bytes).

Ungolfed, expanding command line flags (thanks to perl -MO=Deparse '-anE...) and slightly edited:

use feature 'say';
while (defined($_ = readline)) {
    our @F = split(' ', $_, 0);
    my @a;
    push @a, /\d/ ? $_ : do {
        $j = pop @a;
        $i = pop @a;
        ($i * $j, $i + $j, 0, $i - $j, 0, $i / $j)[-42 + ord($_)]
    } foreach (@F);
    say $a[0];
}

Notes:

  • See documentation of perl command line switches about -a, -n and -E
  • ASCII values of the following chars are useful to understand the expression involving ord:
    * 42
    + 43
    - 45
    / 47
    

An alternate implementation using regexp matching and replacement: 100 bytes

perl '-pEwhile(s!\b([-0-9.]+)\s+([-0-9.]+)\s+([-+*/])!" ".($1*$2,$1+$2,0,$1-$2,0,$1/$2)[-42+ord$3]!e){}y/ //d'

Ungolfed:

use feature 'say';

while (defined($_ = readline ARGV)) {
    while (s[\b([-0-9.]+)\s+([-0-9.]+)\s+([-+*/])][' ' . ($1 * $2, $1 + $2, 0, $1 - $2, 0, $1 / $2)[-42 + ord($3)];]e) {
        ();
    }
    y/ //d;
} continue {
    die "-p destination: $!\n" unless print $_;
}
\$\endgroup\$
  • \$\begingroup\$ You can just say perl 5 \$\endgroup\$ – ASCII-only Jan 3 at 1:44
  • \$\begingroup\$ @ASCII-only say and -E appeared only with Perl v5.10. Sorry if I'm an old-schooler and pedant. \$\endgroup\$ – dolmen Jan 25 at 13:33
  • \$\begingroup\$ hmm. "-a implicitly sets -n". also... what do you need -E for then \$\endgroup\$ – ASCII-only Jan 26 at 0:00
0
\$\begingroup\$

Javascript, 112 bytes

r=c=>(s=[],f=(a,b,o)=>eval(`${b}${o}${a}`),c.split(' ').forEach(e=>s.push(!+e?f(s.pop(),s.pop(),e):+e)),s.pop())

Zero error checking, uses the eval function, but it works with all valid RPN expressions.

r is a function (eg. r('2 3 +') returns 4)

\$\endgroup\$
  • \$\begingroup\$ Quote from the OP: You are not allowed to use any kind of "eval" in the program. \$\endgroup\$ – mickmackusa Sep 1 at 5:46
0
\$\begingroup\$

PHP, 172 bytes (Demo)

<?foreach(preg_split('~ +~',fgets(STDIN))as$v)if(floatval($v))$s[]=$v;else{[$e,$d]=array_splice($s,-2);$s[]=$v=="+"?$e+$d:($v=="-"?$e-$d:($v=="*"?$e*$d:$e/$d));}echo $s[0];

Previously entertained techniques:

<?do{$_GET[a]=preg_replace_callback('~(-?[\d.]+) +(-?[\d.]+) +([*/+-])~',fn($m)=>($m[3]=='+'?$m[1]+$m[2]:($m[3]=='-'?$m[1]-$m[2]:($m[3]=='*'?$m[1]*$m[2]:$m[1]/$m[2]))),$_GET[a],1,$c);}while($c);echo $_GET[a]; // 208

<?$v=$_GET[a];do{$v=preg_replace_callback('~(-?[\d.]+) +(-?[\d.]+) +([*/+-])~',fn($m)=>($m[3]=='+'?$m[1]+$m[2]:($m[3]=='-'?$m[1]-$m[2]:($m[3]=='*'?$m[1]*$m[2]:$m[1]/$m[2]))),$v,1,$c);}while($c);echo $v; // 202

<?while(preg_match('~(.*?)(-?[\d.]+) (-?[\d.]+) ([*/+-])(.*)~',$_GET[a],$m))$_GET[a]=$m[1].($m[4]=='+'?$m[2]+$m[3]:($m[4]=='-'?$m[2]-$m[3]:($m[4]=='*'?$m[2]*$m[3]:$m[2]/$m[3]))).$m[5];echo $_GET[a]; // 198

<?$v=$_GET[a];while(preg_match('~(.*?)(-?[\d.]+) +(-?[\d.]+) +([*/+-])(.*)~',$v,$m))$v=$m[1].($m[4]=='+'?$m[2]+$m[3]:($m[4]=='-'?$m[2]-$m[3]:($m[4]=='*'?$m[2]*$m[3]:$m[2]/$m[3]))).$m[5];echo $v;  // 194
\$\endgroup\$

Your Answer

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