19
\$\begingroup\$

In this challenge, you implement an interpreter for a simple stack-based programming language. Your language must provide the following instructions:

  • push a positive number
  • pop two numbers and push their sum
  • pop two numbers and push their difference (second number - first number)
  • pop a number and push it twice (dup)
  • pop two numbers and push them so that they are in opposite order (swap)
  • pop a number and discard it (drop)

You may assume instructions will never be called with less arguments on the stack than are needed.

The actual instructions can be chosen for each implementation, please specify how each instruction is called in the solution. Your program/function must output/return the stack after all instructions are performed sequentially. Output the stack in whatever format you prefer. The stack must be empty at the start of your program.

Examples

For these examples, the stack is represented bottom-to-top.

1 2 + -> [3]
1 drop -> []
10 2 - 3 + -> [11]
9 dup - -> [0]
1 2 3 -> [1 2 3]
1 dup 2 + -> [1 3]
3 2 5 swap -> [3 5 2]
\$\endgroup\$
9
  • 1
    \$\begingroup\$ How large must the numbers be? In the language I’m using this is going to be difficult if I’m using ints greater than 999. May I restrict the stack size to the same number? Do I have to support negative numbers? \$\endgroup\$
    – noodle man
    Dec 11, 2023 at 13:12
  • 2
    \$\begingroup\$ “whatever format” includes stack order? I see both solutions printing top to bottom and bottom to top. \$\endgroup\$
    – manatwork
    Dec 11, 2023 at 14:41
  • 3
    \$\begingroup\$ If "arbitrary integer" is intended to include negative integers, can we get an example involving pushing one of those? Some solutions look like they only handle positive integers. \$\endgroup\$
    – DLosc
    Dec 11, 2023 at 17:28
  • 1
    \$\begingroup\$ My answer supports only positive integers (not even 0) currently \$\endgroup\$
    – mousetail
    Dec 11, 2023 at 19:12
  • 2
    \$\begingroup\$ Can we get some clarification on whether negative numbers must be supported? (It would be much preferred if they did not need to be since 1: Requiring this would invalidate a bunch of answers and 2: You could get a negative number with something like 10 0 - anyway) \$\endgroup\$
    – DJMcMayhem
    Dec 12, 2023 at 0:21

22 Answers 22

12
\$\begingroup\$

Regex (PCRE 2), 104 bytes (60 + 46)

  • +2 bytes to properly remove excess spaces after ~ commands

Search:

((1+) (1+) a)|((1+) \5(1+) -)|((1+) :)|((1+) (1+) s)|(1+ ~ ?)

Replacement:

${1:+$2$3:${4:+$6:${7:+$8 $8:${9:+$11 $10:}}}}

Input and output in unary.

Each regex substitution resolves one operation, so you need to repeatedly use the regex to replace until the result doesn't change to get a final output.

Try it online!

No language seems to support the PCRE 2 replacement syntax to allow writing an easy wrapper

  • 11111 push a number in unary
  • a add 2 numbers
  • - subtract the first number from the second
  • : duplicate
  • s swap
  • ~ pop
\$\endgroup\$
10
\$\begingroup\$

JavaScript (Node.js), 103 bytes

-2bytes by l4m2

p=>p.split` `.reduce(([a=[],b=[],...S],i)=>[{A:a+b,S:b-a,X:[b,a],P:b}[i]??[1/i?+i:a,a,b],S].flat(2),[])

Attempt This Online!

Operators:

  • A: Add
  • S: Sub
  • D: Dupe
  • X: eXchange
  • P: Pop
  • \d+: push Number

One space between each tokens.

Output is the array where first value is stack top, and last value is stack bottom.

\$\endgroup\$
1
  • \$\begingroup\$ split(' ') => split' ' (grave) \$\endgroup\$
    – l4m2
    Dec 11, 2023 at 15:21
9
\$\begingroup\$

TypeScript's type system, 206 bytes

//@ts-ignore
type F<C,S=[0,0]>=[S,C]extends[[infer A,infer B,...infer V],[infer I,...infer R]]?F<R,I extends`${any}`?[I,...S]:[...[[B],[A,A,B],[B,A],[`${A}${B}`],B extends`${A}${infer Z}`?[Z]:0][I],...V]>:S

Try it at the TS playground

This is a generic type F<C> which takes input as a tuple of items which are either unary numbers as strings of 1s, or numbers 0 to 4 for the 5 commands:

num function
0 Pop
1 Duplicate
2 Swap
3 Add
4 Subtract

This solution works identically to the one below, only it skips the step of splitting on spaces, and indexes into an array instead of a dictionary, so it ends up quite a bit shorter.

TypeScript’s type system, 324 309 251 220 bytes

//@ts-ignore
type F<C,S=[0,0]>=[S,C]extends[[infer A,infer B,...infer V],`${infer I} ${infer R}`]?F<R,I extends`1${any}`?[I,...S]:[...{p:[B],d:[A,A,B],x:[B,A],a:[`${A}${B}`],s:B extends`${A}${infer Z}`?[Z]:0}[I],...V]>:S

Try it at the TS playground

This is a generic type F<C> which takes input as a string type of space separated commands or unary numbers, space terminated. Output in unary, first element is top of stack.

Commands:

name function
a Add
s Subtract
x Swap
p Pop
d Duplicate

I was surprised by how short this was when it was 100 bytes longer than it is now, so now I'm really surprised.

Explanation:

type F<
  // C is the input string type
  C,
  // S is the stack, starts with two useless elements
  S=[0,0],
>=[S,C]extends[
    // get the top 2, A and B, and the rest V, of the stack
    [infer A,infer B,...infer V],
    // get the first word I and the rest R of C
    `${infer I} ${infer R}`
  ]
    // recurse, setting C to R, and setting S to...
    ?F<R,
      // does I start with a 1?
      I extends`1${any}`
        // if so, prepend it to S
        ?[I,...S]
        // otherwise, it's a command; index into this object
        // to replace the top 2 of the stack:
        :[...{
          // pop- just the second
          p:[B],
          // dup- first twice, then second
          d:[A,A,B],
          // swap: second, then first
          x:[B,A],
          // add: concatenate the first and second
          a:[`${A}${B}`],
          // subtract: the second with the first taken away
          s:B extends`${A}${infer Z}`?[Z]:0
        // then append V
        }[I],...V]
    >
  // if C is empty (no more commands are left), return S
  :S
\$\endgroup\$
8
\$\begingroup\$

Trivial Eval/Exec Answers in Stack Languages

For languages where the command set required is already a thing, and evaluating a string is the shortest solution.

Don't add answers in stack languages that aren't purely "exec".

Vyxal W, 1 byte

Ė

Try it Online!

Uses the command set +-:$_ and [0-9]+ for pushing numbers.

05AB1E, 3 bytes

.V)

Try it online.

Uses the command set +-Ds\ for add; subtract; duplicate; swap; drop respectively. .V executes the (implicit) input as 05AB1E code; and ) wraps the entire stack into a list (which is output implicitly at the end).

sclin, 1 bytes

#

Try it on scline! Uses dup, pop, swap, +, -.

dc, 2 characters

?f

Where ? reads a line from stdin and executed it as dc code and f dumps the stack.

In the simple stack language use d for dup, r for swap and ss for drop.

Try it online!

RProgN, 1 byte

C

Try it online!

Requires space between commands, []\ are Drop, Dup, and Swap respectively.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ @KevinCruijssen there's a flag for that :p \$\endgroup\$
    – lyxal
    Dec 11, 2023 at 10:49
  • 1
    \$\begingroup\$ Why am I not surprised. ;) Let me guess, there are 256 flags, one for each single-byte builtin? ;p \$\endgroup\$ Dec 11, 2023 at 11:08
  • 1
    \$\begingroup\$ @KevinCruijssen I wish. If I did that, I'd never hear the end of it from people already critical about flags :p \$\endgroup\$
    – lyxal
    Dec 11, 2023 at 11:17
4
\$\begingroup\$

flex, 179 bytes

%{
s[9];i;t;
%}
%%
a s[--i-1]+=s[i];
s s[--i-1]-=s[i];
d s[i++]=s[i-1];
x s[i-2]^=s[i-1]^(s[i-1]=s[i-2]);
p --i;
[0-9]+ s[i++]=atoi(yytext);
\n for(t=i;t--;)printf("%d ",s[t]);
%%

Try it online!

Uses:

  • [0-9]+ push a number
  • a sum
  • s difference
  • d dup
  • x swap
  • p drop
\$\endgroup\$
4
\$\begingroup\$

Brain-flak, 294 bytes

{(()[]<(({}()))({[()](<{}>)}(){}){{}<>({}{})((<>))}{}(({}()))({[()](<{}>)}(){}){
{}<>([{}]{})((<>))}{}(({}()))({[()](<{}>)}(){}){{}<>(({}))((<>))}{}(({}()))({[()
](<{}>)}(){}){{}<>(({}({}))[({}[{}])])((<>))}{}(({}()))({[()](<{}>)}(){}){{}<>{}
((<>))}{}>[[]]){{}({}[()()()()()]<>)(((<>)))}{}{}{}}<>

Try it Online!

What better way to "Implement a simple stack language" than by using "a simple stack language"! And also a nice excuse to show off a new online interpreter for brain-flak that I have been working on.

Conveniently, a lot of the behavior described in the challenge is built-in to how brain-flak works. For example, Your program/function must output/return the stack after all instructions are performed sequentially is just describing the fundamental operation of brain-flak. And also, we could take each of the listed operations and transliterate it to brain-flak:

# Sum
({}{})

# Subtract
([{}]{})

# Duplicate
(({}))

# Swap
(({}({}))[({}[{}])])

# Pop
{}

Unfortunately, transliteration does not a valid answer make. So we need to do a bit of parsing to figure out which operation to call.

Without clarification from OP (and seeing as many answers have assumed positive input integers), this answer assumes that "push an arbitrary integer" means "an arbitrary positive integer". Here is the input format:

  • -1: sum
  • -2: subtract
  • -3: duplicate
  • -4: swap
  • -5: pop
  • All other positive integers: Push that integer

Technically, negative numbers other than 5 listed also work to push a number. 0 does not work.

("TOS" means "Top of Stack")

Commented/readable version:

# While primary stack is not empty...
{
    # Keep track of the stack height +1 at this point...
    (()[]<

        # Increment TOS
        (({}()))

        # TOS != 0
        ({[()](<{}>)}(){})

        # If TOS != 0...
        {
            # OPCode -1: Sum
            # Pop two numbers and push their sum to the alternate stack
            {}
            <>
            ({}{})

            # Go back to main stack and replace TOS with 2 zeros
            ((<>))
        }{}

        # Increment TOS
        (({}()))

        # TOS != 0
        ({[()](<{}>)}(){})

        # If TOS != 0...
        {
            # OPCode -2: subtract
            # Pop two numbers and push their difference to the alternate stack. Second number - first number.
            {}
            <>
            ([{}]{})

            # Go back to main stack and replace TOS with 2 zeros
            ((<>))
        }{}

        # Increment TOS
        (({}()))

        # TOS != 0
        ({[()](<{}>)}(){})

        # If TOS != 0...
        {
            # OPCode -3: duplicate
            # to the alternate stack
            {}
            <>
            (({}))

            # Go back to main stack and replace TOS with 2 zeros
            ((<>))
        }{}

        # Increment TOS
        (({}()))

        # TOS != 0
        ({[()](<{}>)}(){})

        # If TOS != 0...
        {
            # OPCode -4: swap
            # on the alternate stack
            {}
            <>
            (({}({}))[({}[{}])])

            # Go back to main stack and replace TOS with 2 zeros
            ((<>))
        }{}

        # Increment TOS
        (({}()))

        # TOS != 0
        ({[()](<{}>)}(){})

        # If TOS != 0...
        {
            # OPCode -5: pop
            # from the alternate stack
            {}
            <>
            {}

            # Go back to main stack and replace TOS with 2 zeros
            ((<>))
        }{}


    # And see whether any extra values were added to the stack during that last bit
    # Essentially this means: "Push a 1 if none of the opcodes in that snippet matched, otherwise 0"
    # Additionally, if one of the opcodes matched, there will be an extra value on this stack. Remember that, it's important.
    >[[]])

    # If none of the opcodes matched...
    {
        # Pop a useless '1'
        {}

        # Push TOS - 5 onto alternate stack
        # This is the original positive integer that needs to be pushed
        ({}[()()()()()]<>)

        # Push THREE zeroes onto main stack
        (((<>)))
    }

    # Pop three values off the stack
    {}{}{}

}

# Switch to main stack
<>

I'm certain this could be golfed further.

\$\endgroup\$
3
\$\begingroup\$

Ruby, 114 bytes

f=->s,*r{s[/.+? ?/]?f[$',*r+(s>?/?[s.to_i]:(q=r.pop;s>?.?[q,q]:s>?-?[]:(w=r.pop;s>?,?[q-w]:s>?+?[q,w]:[q+w])))]:r}

Try it online!

Usage

  • / dup
  • . drop
  • - subtract
  • , swap
  • + add
\$\endgroup\$
3
\$\begingroup\$

Go, 321 320 312 bytes

import(."strings";."fmt")
func f(c string)(o[]int){for _,e:=range Fields(c){n,a,b,A:=0,0,0,len(o)-1
B:=A-1
if A>-1{a=o[A]}
if A>0{b=o[B]}
switch e{case"D":o=o[:A]
case"d":o=append(o,a)
case"s":o=append(o[:B],a,b)
case"+":o=append(o[:B],b+a)
case"-":o=append(o[:B],b-a)
default:Sscan(e,&n);o=append(o,n)}}
return}

Attempt This Online!

Very straight-forward split-on-spaces then switch-on-token.

-1 by aliasing indexes and elements. -8 by using the following instruction names:

  • Drop
  • duplicate
  • swap
  • +, -, and integers
\$\endgroup\$
1
  • \$\begingroup\$ You can use shorter names for the commands, for example . for drop, : for dupe, etc \$\endgroup\$
    – noodle man
    Dec 11, 2023 at 17:40
3
\$\begingroup\$

Perl 5 -a, 101 92 bytes

map{/\W$/?eval"\$a[-2]$&=pop\@a":/x/?pop@a:push@a,/d/?$a[-1]:/s/?(pop@a,pop@a):$_}@F;say"@a"

Try it online!

Operations:

  • + = add

  • - = subtract

  • s = swap

  • d = duplicate

  • x = drop

  • Anything with a digit in it is assumed to be a number. This implies that this will work with integers and floats as well as allowing a sign indicator at the front of the number.

Operators and numbers must be separated from each other by at least one space. No error checking was specified, so this code does not do any.

\$\endgroup\$
3
\$\begingroup\$

Python, 111 bytes

-11 bytes, thanks to emanresu A, uses bytes 0x00-0x03 as commands

def g(s):
 S=[]
 exec(s.translate('S+=[0]; S[-1]+=1; *_,a,b=S;S[-2:]=[b,a-b,a]; S[-1:]=[];'.split()))
 return S

Attempt This Online!


Python, 122 bytes

-8 bytes, thanks to psmears

def f(s):
 S=[]
 for c in s:exec('S+=[0] S[-1]+=1 *_,a,b=S;S[-2:]=[b,a-b,a] S[-1:]=[]'.split()['#*$.'.index(c)])
 return S

Attempt This Online!


Python, 127 bytes (no eval)

taking emanresu A's suggestion to its extreme

def f(s):
 S=[]
 for c in s:
  if"#"==c:S+=[0]
  if"*"==c:S[-1]+=1
  if"$"==c:*S,a,b=S;S+=[b,a-b,a]
  if"."==c:*S,_=S
 return S

Attempt This Online!

  • push number: # followed by n times *
  • drop: .
  • swap: $$..
  • add: $$.$.$$...$$...
  • subt: $.$$...
  • dup: #$.$$.$.$$...

It is possible to go down to 3 operations, by creating a new operation ' that pushes 1 and replacing # with ''$.$$.. and * with '$$.$.$$...$$.... But then the pushed integer is no longer clearly determinable from the push integer instruction


Python, 193 bytes

def f(s):
 S=[]
 for c in s:
  if"/"<c<":":S[-1]=10*S[-1]+int(c)
  if"#"==c:S+=[0]
  if"$"==c:*S,a,b=S;S+=[a+b,a-b]
  if":"==c:S+=[S[-1]]
  if","==c:S[-2:]=S[:-3:-1]
  if"."==c:*S,_=S
 return S

Attempt This Online!

Operations:

According to the comments on the sandbox version it is allowed to split operations into smaller suboperations

Atomics:

  • # push zero
  • 0-9 pop number multiply by 10 add digit
  • $ pop two numbers push their sum and difference
  • : duplicate top number
  • , swap top two numbers
  • . drop top number

simulating operations from requirements:

  • # followed by sequence of digits pushes a number
  • $. pops two numbers and pushes their sum
  • $,. pops two numbers and pushes their difference
\$\endgroup\$
5
  • \$\begingroup\$ You could potentially go even more minimalistic. Why use digits 0-9 instead of just 0/1? You could just have a single "pop two numbers and push difference" and use that to simulate addition. For that matter, dup - - is equivalent to drop. \$\endgroup\$
    – emanresu A
    Dec 11, 2023 at 20:33
  • \$\begingroup\$ You can save a dozen or so bytes in the first one by replacing the body of the for loop with a horrible dict/exec combo: exec({'#':'S+=[0]','*':'S[-1]+=1','$':'*S,a,b=S;S+=[a+b,-b]',',':'S[-2:]=S[:-3:-1]','.':'*S,_=S'}[c]) \$\endgroup\$
    – psmears
    Dec 12, 2023 at 16:35
  • \$\begingroup\$ @psmears I already tried that, python does not store values assigned within an exec block, so only the first two statements work \$\endgroup\$
    – bsoelch
    Dec 13, 2023 at 7:51
  • \$\begingroup\$ @bsoelch: Dammit, I was pressed for time so I only tested the first two statements to check the syntax wasn't completely off! I think you can still save a few bytes though, with something like: exec({'#':'S+=[0]','*':'S[-1]+=1','$':'*_,a,b=S;S[-2:]=[a+b,-b]',',':'S[-2:]=S[:-3:-1]','.':'S[-1:]=[]'}[c]) (can possibly be golfed further...) \$\endgroup\$
    – psmears
    Dec 13, 2023 at 11:20
  • \$\begingroup\$ 111 on the first one with cursed translate hacks, your commands are now \x00 \x01 \x02 \x03 \$\endgroup\$
    – emanresu A
    Dec 16, 2023 at 2:07
3
\$\begingroup\$

Gema, 206 203 characters

<N>=@push{s;$1}
+=@set{s;@add{$s;@pop{s}$s}}
-=@set{t;$s}@set{s;@sub{@pop{s}$s;$t}}
d=@push{s;$s}
r=@set{t;$s}@set{n;@pop{s}$s}@set{s;$t}@push{s;$n}
s=@pop{s}
 =
\Z=@f{}
f:=@cmps{${s;};;;;$s @pop{s}@f{}}

As I like dc, borrowed its commands: d dup, r swap, s drop.
The stack is dumped top to bottom.

Sample run:

bash-5.2$ echo '1 2 + d 3 4 - 5 r 6 7 8 s s 9' | gema '<N>=@push{s;$1};+=@set{s;@add{$s;@pop{s}$s}};-=@set{t;$s}@set{s;@sub{@pop{s}$s;$t}};d=@push{s;$s};r=@set{t;$s}@set{n;@pop{s}$s}@set{s;$t}@push{s;$n};s=@pop{s}; =;\Z=@f{};f:=@cmps{${s;};;;;$s @pop{s}@f{}}'
9 6 -1 5 3

Try it online! / Try all test cases online!

\$\endgroup\$
3
\$\begingroup\$

C (gcc), 131 129 bytes

k[99],*s=k,t;main(p){
for(;p=getchar()-64;*s=p<0?*s*8+p+16:p<4?p=*s--,t=*s,p:p<6?*s+t:p<8?-*s:!++s);
for(;s>k;printf("%d ",*s--));}

Try it online!

Inspired by Python answer, saved 23 bytes by implementing keywords as primitives:

Primitives

  • octal-digit: multiply stack top by 8, add digit value.
  • swap-pop: swap top two items, pop new top into temp register.
  • add: add temp register to stack top
  • negate: negate top of stack
  • push-zero: push a 0 onto top of tack

These primitives are mapped to to ASCII ranges, which allow us to build the following operations with nonsense names.

OPERATION KEYWORDS:

  • ^ = Number entry, should be followed by octal-digits
  • AD = Add (swap-pop;add)
  • AGE = Sub (swap-pop;negate;add)
  • CUE = Swap (swap-pop;push-zero;add)
  • LADLE = Dup (push-zero;swap-pop;add;push-zero;add)
  • CODA = Drop (Swap;swap-pop)
  • @ = terminate and print

USAGE:

$> echo "^1^2AD^1CODA^12^2AGE^3AD^9LADLEAGE^1^2^3^1LADLE^2AD^3^2^5CUE@" | ./a.out
2 5 3 3 1 3 2 1 0 11 3 

previous:

C (gcc), 244, 229, 223, 204, 161, 154 bytes

thanks to @ceilingcat for -7

k[99],*s=k,t;main(p){for(;p=getchar()-42;*s=t=p<0?!++s:p>5?8*t+p-6:p>4?*--s:p>3?
*s++:p>2?*--s-t:p>1?p=*--s,*s++=t,p:*--s+t);for(;s>k;printf("%d ",*s--));}

Try it online!

OPERATIONS:

  • = Number entry: follow with octal digits
  • + = Add
  • - = Sub
  • , = Swap
  • . = Dup
  • / = Drop
  • * = terminate and print

Usage:

$> echo ' 1 2+ 1/ 12 2- 3+ 9.- 1 2 3 1. 2+ 3 2 5,*' |  /a out 
2 5 3 3 1 3 2 1 0 11 3 

How it works: k is the stack storage and s points to the top. p is the next program character from standard input.
p-42 maps the range "*+,-./01234567" into 0..14.

A '*' (0) exits the loop. Otherwise, it's a big if-else statement using ternary operators.
Any ASCII character below '*' starts a number entry by pushing a 0 onto the stack.
Characters from '0' upward are converted to octal digits and added to 8* the stack top t.
The remaining 5 characters manipulate the stack pointer and produce the value that should be on top.

\$\endgroup\$
1
  • \$\begingroup\$ Restricting the stack to 9 values would make a nice even 128 \$\endgroup\$
    – AShelly
    Dec 20, 2023 at 23:09
2
\$\begingroup\$

Charcoal, 48 bytes

WS≡§ι¹+⊞υ⁺⊟υ⊟υ-⊞υ⁻⊟υ⊟υr≔⊟υιu⊞υ↨υ⁰wFE²⊟υ⊞υκ⊞υIιIυ

Try it online! Link is to verbose version of code. Takes a list of newline-terminated words as input (could save two bytes by requiring symbols). Explanation:

WS≡§ι¹

For each input string, switch on its second character.

+⊞υ⁺⊟υ⊟υ
-⊞υ⁻⊟υ⊟υ
r≔⊟υι
u⊞υ↨υ⁰
wFE²⊟υ⊞υκ

Handle +, -, drop, dup and swap respectively.

⊞υIι

Anything else is assumed to be a number to be pushed to the stack.

Iυ

Output the final stack.

\$\endgroup\$
2
\$\begingroup\$

Pip -p, 50 bytes

V"lPU:".{@a?a(a."POl+:POl 0l@>:2 @l lPK1"^sa)}MJgl

Attempt This Online!

Takes commands as separate command-line arguments. Outputs the final stack as a list, top first. The commands are as follows:

42  push nonzero number
i   push 0
0+  +
0-  -
01  drop
02  dup
03  swap

Explanation

As usual for language interpreters in Pip, this is a translate-and-eval solution. Since l is preinitialized to the empty list, we'll use that to store the stack. The overall logic of the program is:

V"lPU:".{...}MJgl
               g   ; List of command-line args
             MJ    ; Map this function to each and join into a single string:
        {...}      ;   Translation code (see below)
 "lPU:".           ;   Prepend lPU: to each translated command
V                  ; Evaluate
                l  ; Print the final value of l (formatted nicely by -p flag)

Inside the translation function:

@a?a(a."POl+:POl 0l@>:2 @l lPK1"^sa)
@a                                    ; First character of command
  ?                                   ; Is it truthy (nonzero)?
   a                                  ; If so, return unchanged (this is a push command)
    (                             a)  ; Otherwise, treat the command as an index into...
     a."                       "      ;   Prepend the command to this string
                                ^s    ;   and split on spaces

which boils down to the following translation table:

42  lPU:42          ; Push 42 onto l
i   lPU:i           ; Push i (preinitialized to 0) onto l
0+  lPU:0+POl+:POl  ; Pop number, add 0, pop another number, add, push result
0-  lPU:0-POl+:POl  ; Pop number, subtract from 0, pop another number, add, push result
01  lPU:0l@>:2      ; Push 0, then remove first two elements of l
02  lPU:@l          ; Push first element of l
03  lPU:lPK1        ; Remove element at index 1, then push it
\$\endgroup\$
2
\$\begingroup\$

Haskell, 143 bytes

([]#).words
(a:b:s)#(c:r)|c=="s"=(b:a:s)#r|c=="+"=(a+b:s)#r|c=="-"=(b-a:s)#r
(a:s)#(c:r)|c=="d"=(a:a:s)#r|c=="x"=s#r
s#(n:r)=(read n:s)#r
s#_=s

Try it online!

Operations

  • + Add
  • - Subtract
  • s Swap
  • d Dupe
  • x Drop
  • Everything else is interpreted as a number

All commands are separated by spaces, and this code does no error checking.

\$\endgroup\$
2
\$\begingroup\$

Vyxal 3, 29 bytes

⸠+⸠-⸠:⸠$⸠_W₈×£?Ṃ(nnK[⌊|O¥iĖ]W

Try it Online! (link is to literate version)

Wow, the SBCS really doesn't do the beauty of literate mode justice:

(. add) (. sub) (. dup) (. swap) (. pop) wrap neg-1 * set-reg
'for (input split-spaces)
  n n
  (is-num?) ? floor : ord get-reg index call
close-all wrap

Command set is:

i -> add
j -> subtract
k -> duplicate
l -> swap
m -> pop
[0-9]+ -> number

Explained

⸠+⸠-⸠:⸠$⸠_W₈×£?Ṃ(nnK[⌊|O¥iĖ]W­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁣‏⁠‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣‏⁠‎⁡⁠⁤‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏‏​⁡⁠⁡‌⁢⁣​‎‏​⁢⁠⁡‌⁢⁤​‎‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏‏​⁡⁠⁡‌⁣⁡​‎‎⁡⁠⁤⁢‏‏​⁡⁠⁡‌⁣⁢​‎‎⁡⁠⁤⁣‏⁠‎⁡⁠⁤⁤‏‏​⁡⁠⁡‌⁣⁣​‎‎⁡⁠⁢⁡⁡‏⁠‏​⁡⁠⁡‌⁣⁤​‎‎⁡⁠⁢⁡⁢‏⁠‎⁡⁠⁢⁡⁣‏‏​⁡⁠⁡‌⁤⁡​‎‎⁡⁠⁢⁡⁤‏‏​⁡⁠⁡‌⁤⁢​‎‎⁡⁠⁢⁢⁡‏⁠‎⁡⁠⁢⁢⁢‏⁠‏​⁡⁠⁡‌⁤⁣​‎‎⁡⁠⁢⁢⁣‏‏​⁡⁠⁡‌⁤⁤​‎‎⁡⁠⁢⁢⁤‏‏​⁡⁠⁡‌⁢⁡⁡​‎‎⁡⁠⁢⁣⁡‏⁠‎⁡⁠⁢⁣⁢‏‏​⁡⁠⁡‌⁢⁡⁢​‎‎⁡⁠⁢⁣⁣‏‏​⁡⁠⁡‌⁢⁡⁣​‎‏​⁢⁠⁡‌⁢⁡⁤​‎‎⁡⁠⁢⁣⁤‏⁠‎⁡⁠⁢⁤⁡‏‏​⁡⁠⁡‌­
⸠+⸠-⸠:⸠$⸠_W                    # ‎⁡Push a list of:
⸠+                             # ‎⁢  lambda x, y: x + y
  ⸠-                           # ‎⁣  lambda x, y: x - y
    ⸠:                         # ‎⁤  lambda (stack): stack.push(stack[-1])
      ⸠$                       # ‎⁢⁡  lambda (stack): stack[-2], stack[-1] = stack[-1], stack[-2]
        ⸠_                     # ‎⁢⁢  lambda (stack): stack.pop()
# ‎⁢⁣Technically, all these lambdas are monadic (take one argument) so far.
           ₈×                  # ‎⁢⁤Multiply each lambda by -1 to make them operate on the stack
             £                 # ‎⁣⁡And put the stack lambda list in the register
              ?Ṃ               # ‎⁣⁢Split the input on spaces,
                (              # ‎⁣⁣and to each command `n` in that,
                 nn            # ‎⁣⁤  Push two copies of `n`
                   K           # ‎⁤⁡  and test whether the second copy is numeric
                    [⌊         # ‎⁤⁢  if so, simply evaluate and leave on the stack
                      |        # ‎⁤⁣  otherwise:
                       O       # ‎⁤⁤    get the unicode code-point of `n`
                        ¥i     # ‎⁢⁡⁡    index into the register
                          Ė    # ‎⁢⁡⁢    and call the pushed lambda.
# ‎⁢⁡⁣That's the reason the command set was chosen - the ord value mod 5 corresponds to the lambda. Any set of 5 characters could have been chosen, but `i` was the closest to `d`, which I knew to be `100`.
                           ]W  # ‎⁢⁡⁤Close all structures, and wrap the stack when finished.
💎

Created with the help of Luminespire.

\$\endgroup\$
2
\$\begingroup\$

Haskell, 99 bytes

foldl(!)[]
s!c|c<0= -c:s|1<2=[j(+),j(-),\(n:x)->n:n:x,\(a:b:x)->b:a:x,tail]!!c$s
j o(a:b:x)=b`o`a:x

Try it online!

Takes a list of integers as input, where:

  • 0: sum
  • 1: subtract
  • 2: dup
  • 3: swap
  • 4: pop
  • -n: push n

Prints the stack as a list with the top element first.


This works by building a list of functions and using the command integer to index into this list. Negative commands are managed separately.

The definitions of dup, swap, and pop are fairly straightforward, but rather than defining two separate functions for sum and subtract I've defined a single function j that takes an operator as an extra argument and applies this operator to the first two elements of the stack. Passing (+) and (-) to j then does the trick.

\$\endgroup\$
2
\$\begingroup\$

PowerShell Core, 118 bytes

switch -r($args){\D{$a,$b,$s=$s}s{$s=$b,$a+$s}[-+]{$s=,("$b$_$a"|iex)+$s}u{$s=$a,$a,$b+$s}r{$s=,$b+$s}\d{$s=,$_+$s}}$s

Try it online!

Takes an array in parameter containing the instructions, returns an array top to bottom.

Explanation for the previous version, but the idea is still more or less the same:

switch -r($args){                       # for each of the instruction switch as regular expressions:
s{$a,$b,$s=$s;$s=$b,$a+$s}              # s for Swap
u{$b,$s=$s;$s=$b,$b+$s}                 # u for dUp
r{$b,$s=$s}                             # r for dRop
[+-]{$a,$b,$s=$s;$s=,("$b$_$a"|iex)+$s} # + or - for subtract and sum
\d{$s=,$_+$s}                           # to push a number
}                                       # end of the foreach
$s                                      # return the stack
\$\endgroup\$
2
\$\begingroup\$

Cabsi, 173 bytes

1PUSH NULL
2GETW
3JNL 8
4DUP
5YEET
6ORD
7GOTO $1
8JNL 64
9PRINT
10GOTO 8
33POP
34GOTO 2
36SWAP
37GOTO 2
43ADD
44GOTO 2
45SUB
46GOTO 2
57YOINK
58MAKEI
59GOTO 2
62DUP
63GOTO 2

Try it here! Implements dup (>) add (+) sub (-) drop (!) and swap ($). Prints stack top-to-bottom. Expects instructions to be separated by spaces/newlines.

Technically, only the first character of non-numeric instructions are parsed, so the "literate" input 10 2 - 3 + >dup 2 + $swap >dup 0 $swap - $swap !drop works just as well as the minified 10 2 - 3 + > 2 + $ > 0 $ - $ !.

Explanation

As Cabsi is a stack language, the code can implement a stack-based language using its own stack. Thankfully, since the target language is not very complex, there is not a lot of overhead we need.

1 PUSH NULL     REM Stack work delimiter
REM ReadLoop:
2 GETW          REM Read word from STDIN
3 JNL 8         REM If end of input, jump to PrintLoop
4 DUP           REM Duplicate token read
5 YEET          REM And place it on the secondary stack
6 ORD           REM Get Ord(Token[0])
7 GOTO $1       REM Goto the line specified by that ordinal
REM PrintLoop:
8 JNL 64        REM If work delimiter reached, end program
9 PRINT         REM Print top of stack 
10 GOTO 8       REM Jump to PrintLoop
REM If "!" (ord 33):
33 POP          REM Pop top of stack
34 GOTO 2       REM Jump to ReadLoop
REM If "$" (ord 36):
36 SWAP         REM Swap top two on stack
37 GOTO 2       REM Jump to ReadLoop
REM If "+" (ord 43):
43 ADD          REM Add top two on stack
44 GOTO 2       REM Jump to ReadLoop
REM If "-" (ord 45):
45 SUB          REM Subtract top two on stack
46 GOTO 2       REM Jump to ReadLoop
REM If "0" through "9" (ords 48 through 57)
57 YOINK        REM Pull the full representation from the secondary stack
58 MAKEI        REM Cast to integer
59 GOTO 2       REM Jump to ReadLoop
REM If ">" (ord 62)
62 DUP          REM Duplicate top on stack
63 GOTO 2       REM Jump to ReadLoop
\$\endgroup\$
2
\$\begingroup\$

brainfuck, 684 649 bytes

,[<<--[>+<++++++]>-[->-<]>[[<]+[>]<-]<<<<<<<<<<<<<<<<[[->]<<<<<<<<<<<<<<<<]>[->+<]>[->+<]>[->+<]>[->+<]>[->+<]>[->+<]>[->+<]>[->+<]>>[-]<[->+<]>[<+[,<<++++[>++++++++<-]>[->-<]>[---------------->[-<++++++++++>]<[->+<]<+>]<[->+<]>]>>>>>>>>>[>]+[<]<<<<<<<-[->>>>>>>>[>]<+[<]<<<<<<<]>->->->->-<<<<<]>[->>>>>>>>[>]<<[->>+<<]>[-<+>]>[-<+>]<[<]<-<-<-<-<-<]>[->>>>>>>[>]<[-]<[<]<-<-<-<-<]>[->>>>>>[>]<[-<->]<[<]<-<-<-<]>[->>>>>[>]<[->+>+<<]>>[-<<+>>]<<<[<]<-<-<]>[->>>>[>]<[-<+>]<[<]<-<]>,]>>[[<++++++++++>[-<-[<+<<]<[+[->+<]<+<<]>>>>>]<[-]-[>+<-----]>---[-<<+>>]<<-<<<<<[<]+[>]>>>>[-<<<<<[<]>+[>]>>>>]<[->>>+<<<]>>>]<<<<<<<[<]>[.[-]>]++++++++++.[-]>>>>>>>]

Try it online!

All numbers have to be followed by a space. Uses +-,./ for add, sub, dup, drop, and swap respectively.

Prints stack from bottom to top separated by newlines.

I confess this is a touch over-engineered, and could be shorter if I used less human-readable I/O.

With Comments

READ AN INSTRUCTION
IF ITS A NUMBER THEN GRAB ALL OF IT UNTIL THE SPACE
OTHERWISE ITS A REGULAR INSTRUCTION
ITS ACTUALLY EASIER TO CHECK IF ITS A REGULAR INSTRUCTION THAN A NUMBER BECAUSE THERE ARE MORE NUMBERS THAN INSTRUCTIONS
SO WE CHECK THAT FIRST
>>>>>>>>>>>>>>>>>>>>>>>>>>>> THIS LINE MAKES DEBUGGING EASIER BUT ISNT NEEDED
,[
    <<--[>+<++++++]>-
    SUBTRACT 42 FROM INP
    [->-<]
    COLLAPSE IT LEFT
    >[
     CLEAR THE ONE AT NEGATIVE SIXTEEN
     THIS IS A GUARD VALUE
     <<<<<<<<<<<<<<<<[-]>>>>>>>>>>>>>>>>
    [<]+[>]<-]
    SUM UP THE FIRST NINE NUMBERS AS THESE ARE THE DIGITS
    WE IGNORE 0 AS ITS NOT USEFUL
    <<<<<<<<<<<<<<<<
    IF THE GUARD IS TRIPPED THEN WE DISCARD THE WHOLE STACK
    [[->]<<<<<<<<<<<<<<<<]>
    [->+<]>[->+<]>[->+<]>[->+<]>[->+<]>[->+<]>[->+<]>[->+<]>
    >[-]<[->+<]> I PUT IT IN THE ZERO ANYWAY FOR SANITY
    IF THIS IS TRUTHY THEN ITS A NUMBER THAT WE NEED TO PUSH
    IN SUCH CASE WE NEED TO KEEP GRABBING DIGITS UNTIL WE SEE A 32 SPACE
    [
        <+[
            ,
            32
            <<++++[>++++++++<-]>
            SUBTRACT FROM INP
            [->-<]
            >
            [
                IF ITS STILL TRUTHY THEN ITS A NUMBER (PROBABLY)
                SUBTRACT 16 THAN MULTIPLY BY TEN ONTO THIS
                ----------------
                >[-<++++++++++>]
                AND COPY BACK
                <[->+<]
                <+> SET THE NOT FLAG
            ]
            COPY THE NOTFLAG UNTO HERE TO CHECK IF WE NEED TO LOOP
            <[->+<]>
        ]
        GO SIX RIGHT AND PUSH A NEW VALUE TO THE STACK
        >>>>>>>>>[>]+[<]<<<<<<<-
        [->>>>>>>>[>]<+[<]<<<<<<<]
        >->->->->-
        <<<<<
    ]
    > IF THIS IS POSITIVE THAN ITS A SWAP INSTEAD
    [
        WE USE SCRATCH SPACE NEXT TO THE NUMBERS TO MAKE SWAPPING THEM POSSIBLE
        -
        >>>>>>>>[>]<<
        COPY THIS NUMBER TWO ACROSS
        [->>+<<]
        >[-<+>] COPY THE NEXT NUMBER INTO THIS PLACE
        >[-<+>] AND THIS ONE TOO
        <[<]<-<-<-<-<-< AND GO HOME
    ]
    > IF THIS IS POSITIVE THAN ITS A DROP
    [
        -
        >>>>>>>[>]< GO TO THE TOP OF THE STACK
        [-] CLEAR IT
        <[<]<-<-<-<-< AND GO HOME
    ]
    > IF THIS IS POSITIVE THAN ITS A SUB
    [
        -
        >>>>>>[>]< GO TO THE TOP OF THE STACK
        [-<->] SUB IT FROM THE LAST
        <[<]<-<-<-< AND GO HOME
    ]
    > IF THIS IS POSITIVE THAN ITS A DUP
    [
        -
        >>>>>[>]< GO TO THE TOP OF THE STACK
        [->+>+<<] COPY IT ACROSS THE NEXT TWO
        >>[-<<+>>] COPY THE ONE BACK TWO
        <<<[<]<-<-< AND GO HOME
    ]
    > FINALLY IF THIS IS POSITIVE THAN ITS ADD
    [
        -
        >>>>[>]< GO TO THE TOP OF THE STACK
        [-<+>] ADD IT UNTO THE LAST
        <[<]<-< AND GO HOME
    ]
    >,
]
ONCE WERE DONE WE NEED TO PRINT ALL VALUES ON THE STACK
>>
[
    GET ALL THE DIGITS
    [
        <++++++++++>
        [-<-[<+<<]<[+[->+<]<+<<]>>>>>] DIVMOD
        <[-] UNNEEDED VALUE
        SET TO 48 AND ADD TO THE MOD VALUE
        -[>+<-----]>---
        [-<<+>>]
        <<
        PUSH THIS VALUE TO THE NUMBERSTACK
        -<<<<<[<]+[>]>>>>
        [-<<<<<[<]>+[>]>>>>]
        <[->>>+<<<] MOVE THE NEW VALUE BACK
        >>>
    ]
    PRINT THEM ALL OUT
    <<<<<<<[<]>[.[-]>]
    PRINT A NEWLINE AS WELL ++++++++++.[-]
    >>>>>>> NEXT NUMBER
]
\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog Classic), 50 bytes

T←{(⍺⍺2↑⍵),2↓⍵}
p←+/T
m←¯1∘⊥T
x←⊃,⊢
s←⌽T
d←1∘↓
⎕←⎕

Try it online!

  • Programs start on the right with (empty array, called zilde) and run as their own lines, not as strings.
  • n, pushes n onto the stack.
  • p adds the top two.
  • m subtracts the top from the second.
  • x duplicates the top.
  • s swaps the top two.
  • d drops the top.

Note that the spaces are necessary.

Polish notation is used, i.e. read right-to-left (opposite of the examples in the question), as APL itself is right-to-left. The stack is stored and displayed top-to-bottom (opposite of the examples in the question). E.g. using Polish notation 1 dup 2 + becomes p 2,x 1,⍬ and outputs 3 1

My first time using dops (user-defined operators) in APL. Doesn't seem too useful for golfing, unless you are defining multiple similar functions. T is a dop defined as {(⍺⍺2↑⍵),2↓⍵}. This is a monadic operator that takes a monadic function on the left, and applies it to the first two elements of the array on the right, then catenates with the rest of the array (you can even use this to define new stack operations).

Would love to know how this can be improved upon.

EDIT: There was a bug in my minus function that would negate the whole stack. None of the test cases noticed it though. Fixed now but had to add one byte.

\$\endgroup\$
5
  • \$\begingroup\$ could you add an example of your input format? usually stack langs use RPN \$\endgroup\$
    – RubenVerg
    Dec 12, 2023 at 12:02
  • \$\begingroup\$ Sure. The TIO link has all of the examples from the original question, and I added one to my answer. \$\endgroup\$
    – Tbw
    Dec 12, 2023 at 21:50
  • \$\begingroup\$ is this a valid answer? I think you might be missing a quad to evaluate input, I don't think parts of program are enough \$\endgroup\$
    – RubenVerg
    Dec 13, 2023 at 10:59
  • \$\begingroup\$ I guess I could add something like f←⍎ that literally just executes strings. I felt my method was ok because we are asked to create an interpreter and this turns the APL command line into an interpreter. \$\endgroup\$
    – Tbw
    Dec 13, 2023 at 18:55
  • \$\begingroup\$ I think what you're missing is something like ⎕←⎕ to run the code from stdin; currently your answer is likely invalid \$\endgroup\$
    – RubenVerg
    Dec 14, 2023 at 15:23
1
\$\begingroup\$

Julia 1.0, 90 bytes

f()=[]
f(+,b...;c=f(b...))=try c[[+;2:end]]catch;try[c[2]+c[1];c[3:end]]catch;[+;c]end;end

Try it online!

input and output stacks are lists in reverse order.

It works by chosing clever ways to represent the commands, grouped in 3 types, detected with try/catch (shorter than multiple dispatch here)

  • Arrays:
    • drop: [], will return c[2:end]
    • dup: [1,1] will return c[[1;1;2:end]]
  • Functions:
    • +: +, returns [c[2]+c[1];c[3:end]]
    • -: -, returns [c[2]-c[1];c[3:end]]
    • swap: vcat, returns [c[2];c[1];c[3:end]]
  • Floats:
    • pushing numbers must be floats, otherwise they might not throw an error in the "array" part
\$\endgroup\$
1
  • \$\begingroup\$ not sure if it counts for this loophole \$\endgroup\$
    – MarcMush
    Dec 20, 2023 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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