Implement Anyfix Notation!

Question

In prefix notation, the operator comes before the arguments, so you can kind of imagine that the operator calls next() which is recursively called. In infix notation, the operator goes between the arguments, so you can imagine it simply as a parse tree. In postfix notation, the operator comes after the arguments, so you can just imagine it as stack-based.

In anyfix notation, the operator can go anywhere^*. If an operator shows up and there aren't enough arguments, then the operator waits until there are enough arguments. For this challenge, you are to implement a very basic anyfix evaluator. (Note that anyfix is a recreational language that I abandoned that you can play around with here or check out here)

You will need to support the following commands:

(Arity 1)

• duplicate
• negative

(Arity 2)

• addition
• multiplication
• equality: returns 0 or 1.

You may choose to use any five non-whitespace symbols for these commands. For demonstrational purposes, I will use " as duplicate, × as multiplication, and + as addition.

For literals, you only need to support non-negative integers, but your interpreter must be able to contain all integers (within your language's (reasonable) integer range).

Let's take a look at an example: 10+5. The storage should behave as a stack, not a queue. So first, the stack starts at [], and the queued operator list starts at []. Then, the literal 10 is evaluated which makes the stack [10]. Next, the operator + is evaluated, which requires two arguments. However, there is only one argument on the stack, so the queued operator list becomes ['+']. Then, the literal 5 is evaluated which makes the stack [10, 5]. At this point, the operator '+' can be evaluated so it is, making the stack [15] and the queue [].

The final result should be [15] for + 10 5, 10 + 5, and 10 5 +.

Let's take a look at a harder example: 10+". The stack and queue start as [] and []. 10 is evaluated first which makes the stack [10]. Next, + is evaluated, which doesn't change the stack (because there are not enough arguments) and makes the queue ['+']. Then, " is evaluated. This can run immediately so it is, making the stack [10, 10]. + can now be evaluated so the stack becomes [20] and the queue []. The final result is [20].

What about order of operations?

Let's take a look at ×+"10 10. The stack and queue start both as []:

• ×: The stack is unchanged and the queue becomes ['×'].
• +: The stack is unchanged and the queue becomes ['×', '+'].
• ": The stack is unchanged and the queue becomes ['×', '+', '"'].
• 10: The stack becomes [10]. Even though × should be the first operator to be evaluated since it appears first, " can run immediately and none of the operators before it can, so it is evaluated. The stack becomes [10, 10] and the queue ['×', '+']. × can now be evaluated, which makes the stack [100] and the queue ['+'].
• 10: The stack becomes [100, 10], which allows + to be evaluated. The stack becomes [110] and the queue [].

The final result is [110].

The commands used in these demonstrations are consistent with that of the anyfix language; however, the last example will not work due to a bug in my interpreter. (Disclaimer: Your submissions will not be used in the anyfix interpreter)

Challenge

Select a set of 5 non-whitespace non-digit characters and create an anyfix interpreter according to the specifications above. Your program can either output the singular array or the value contained by it; it is guaranteed that the stack of values will only contain a single value at the end of execution and that the queue of operators will be empty at the end of execution.

This is code-golf so the shortest code in bytes wins.

Test Cases

For these test cases, duplicate is ", negative is -, addition is +, multiplication is ×, and equality is =.

Input -> Output
1+2×3 -> 9
1"+"+ -> 4
2"××" -> 16
3"×+" -> 18
3"+×" -> 36
123"= -> 1 ("= always gives 1)
1+2=3 -> 1
1"=2+ -> 3
1-2-+ -> -3
-1-2+ -> 3 (hehe, the `-1` becomes `+1` at the `-` rather than making the `2` a `-1`)
+×"10 10 -> 200 (after the 10 is duplicated (duplication is delayed), 10 + 10 is performed and then 20 * 10, giving 200)

Rules

• Standard Loopholes Apply
• You may take the anyfix official interpreter and golf it if you would like. Expect to lose horribly.

Input will be given as a string and output as an array, a single integer, out the string representation of either. You may assume that the input will only contain spaces, digits, and the 5 characters you choose.

^{* not actually}

Answer 1

JavaScript (ES6), 204 203 200 bytes

Returns an integer.

e=>e.replace(/\d+|\S/g,v=>{for((1/v?s:v>','?u:b)[U='unshift'](v);!!u[0]/s[0]?s[U](u.pop()>'c'?s[0]:-S()):!!b[0]/s[1]?s[U](+eval(S(o=b.pop())+(o<'$'?'==':o)+S())):0;);},s=[],u=[],b=[],S=_=>s.shift())|s

Characters used:

• +: addition
• *: multiplication
• #: equality
• d: duplicate
• -: negative

Test cases

let f =

e=>e.replace(/\d+|\S/g,v=>{for((1/v?s:v>','?u:b)[U='unshift'](v);!!u[0]/s[0]?s[U](u.pop()>'c'?s[0]:-S()):!!b[0]/s[1]?s[U](+eval(S(o=b.pop())+(o<'$'?'==':o)+S())):0;);},s=[],u=[],b=[],S=_=>s.shift())|s

;[ '10+5', '10+d', '*+d10 10', '1+2*3', '1d+d+', '2d**d', '3d*+d', '3d+*d', '123d#', '1+2#3', '1d#2+', '1-2-+', '-1-2+' ]
.forEach(e => console.log(e, '-->', f(e)))

Formatted and commented

e => e.replace(                     // given an expression e, for each value v matching
  /\d+|\S/g, v => {                 // a group of digits or any other non-whitespace char.
    for(                            //   this loop processes as many operators as possible
      (                             //   insert v at the beginning of the relevant stack:
        1 / v ? s : v > ',' ? u : b //     either value, unary operator or binary operator
      )[U = 'unshift'](v);          //     (s[], u[] or b[] respectively)
      !!u[0] / s[0] ?               //   if there's at least 1 value and 1 unary operator:
        s[U](                       //     unshift into s[]:
          u.pop() > 'c' ?           //       for the duplicate operator:
            s[0]                    //         a copy of the last value
          :                         //       else, for the negative operator:
            -S()                    //         the opposite of the last value
        ) :                         //     end of unshift()
      !!b[0] / s[1] ?               //   if there's at least 2 values and 1 binary operator:
        s[U](                       //     unshift into s[]:
          +eval(                    //       the result of the following expression:
            S(o = b.pop()) +        //         the last value, followed by the
            (o < '$' ? '==' : o) +  //         binary operator o with '#' replaced by '=='
            S()                     //         followed by the penultimate value
          )                         //       end of eval()
        ) : 0;                      //     end of unshift()
    );                              //   end of for()
  },                                // end of replace() callback
  s = [],                           // initialize the value stack s[]
  u = [],                           // initialize the unary operator stack u[]
  b = [],                           // initialize the binary operator stack b[]
  S = _ => s.shift()                // S = helper function to shift from s[]
) | s                               // return the final result

Answer 2

JavaScript (ES6), 162 152 143 150 bytes

(s,N=s.replace(/(-?\d+)-|-(-)/g,'- $1 ').match(/(- ?)*?\d+|R/g))=>+eval(`R=${N[0]>'9'?N[1]:N[0]},${s.match(/[+*=]/g).map((o,i)=>'R=R'+o+'='+N[i+1])}`)

Slightly ungolfed:

(s,
 N=s.replace(/(-?\d+)-|-(-)/g,'- $1 ').      //change postfix negatives to prefix,
                                             //and change "--" to "- - "
     match(/(- ?)*?\d+|R/g)                  //grab numbers and duplicates
)=>+eval(`R=${N[0] > '9' ?  N[1] : N[0]},    //handle a delayed duplicate
          ${s.match(/[+*=]/g).               //grab the operators
              map((o,i)=>'R=R'+o+'='+N[i+1]) //create a comma-separated list of assignments
           }
         `)

Explanation

I'm using * for multiplication and R for duplicate. The other operators are the same as in the question.

N becomes the array of the numbers (including the duplicates).

The replace handles the case where the negative sign comes after the number. For example, it will change 1- to - 1 and -1- to - -1.

Within the eval, s.match creates the array of binary operators. Note that this will always have one fewer elements than N.

The result of the function is the eval of the mapping of the numbers and operators.

Here is what is evaled for each of the test cases:

0+2*3        R=0,R=R+=2,R=R*=3        = 6 
1+2*3        R=1,R=R+=2,R=R*=3        = 9 
1R+R+        R=1,R=R+=R,R=R+=R        = 4 
2R**R        R=2,R=R*=R,R=R*=R        = 16 
3R*+R        R=3,R=R*=R,R=R+=R        = 18 
3R+*R        R=3,R=R+=R,R=R*=R        = 36 
123R=        R=123,R=R==R             = 1 
1+2=3        R=1,R=R+=2,R=R==3        = 1 
1R=2+        R=1,R=R==R,R=R+=2        = 3 
1-2-+        R=- 1,R=R+=- 2           = -3 
-1-2+        R=1,R=R+=2               = 3 
*+R10 10     R=10,R=R*=10,R=R+=10     = 110 
+*R10 10     R=10,R=R+=10,R=R*=10     = 200 
-1+--2       R=-1,R=R+=- -2           = 1 
-1+-2        R=-1,R=R+=-2             = -3 

The comma operator in a JavaScript expression returns the result of its last expression, so the map automatically returns a usable expression.

The + sign is needed before the eval to change true to 1 and false to 0.

Using R as both the variable and the duplicate operator greatly simplifies the map's sub-expressions.

Test cases:

let f=

(s,N=s.replace(/(-?\d+)-|-(-)/g,'- $1 ').match(/(- ?)*?\d+|R/g))=>+eval(`R=${N[0]>'9'?N[1]:N[0]},${s.match(/[+*=]/g).map((o,i)=>'R=R'+o+'='+N[i+1])}`)

console.log(f('1+2*3'))    // 9
console.log(f('1R+R+'))    // 4
console.log(f('2R**R'))    // 16
console.log(f('3R*+R'))    // 18
console.log(f('3R+*R'))    // 36
console.log(f('123R='))    // 1
console.log(f('1+2=3'))    // 1
console.log(f('1R=2+'))    // 3
console.log(f('1-2-+'))    // -3
console.log(f('-1-2+'))    // 3
console.log(f('*+R10 10')) //110
console.log(f('+*R10 10')) //200
console.log(f('-1+--2'));  // 1
console.log(f('-1+-2'));  // -3

Answer 3

JavaScript, 321 311 bytes

_="f=a=>(a.replace(/\\d+|./g,mq!~(b='+*=\"- '.indexOf(a))|b>2j3j4j5&&o+aw1/y?(y*=-1wcz:1/y?oywcz:hz,rql.map(z=>m(lki,1)[0],i)),hq1/s[1]?sk0,2,+eval(`y${a=='='?a+a:a}s[1]`)):cz,cqlki,0,a),s=[],l=[],e='splice'),s)z(a,i)ys[0]w)^r``:q=z=>os.unshift(k[e](j?b-";for(i of"jkoqwyz")with(_.split(i))_=join(pop());eval(_)

Try it online!

The five characters are the same as in the question, except * is for multiplication.
The script is compressed using RegPack. The original script is stored in the variable _ after evaluation.

Answer 4

Haskell, 251 bytes

(#([],[]))
(x:r)#(o,n)|x>'9'=r#h(o++[x],n)|[(a,t)]<-lex$x:r=t#h(o,read a:n)
_#(o,n:_)=n
h=e.e
e(o:s,n:m:r)|o>'N'=e(s,g[o]n m:r)
e(o:s,n:r)|o=='D'=e(s,n:n:r)|o=='N'=e(s,-n:r)
e(o:s,n)|(p,m)<-e(s,n)=(o:p,m)
e t=t
g"a"=(+)
g"m"=(*)
g"q"=(((0^).abs).).(-)

Try it online! Uses the following characters: a for addition, m for multiplication, q for equality, D for duplicate and N for negation. (I wanted to use e for equality, but ran into the problem that lex parses 2e3 as a number.) Example usage: (#([],[])) "2a3 4m" yields 20.

Answer 5

VB.NET (.NET 4.5) 615 576 bytes

-39 bytes thanks to Felix Palmen by changing \r\n to \n

Requires Imports System.Collections.Generic (included in byte count)

Dim s=New Stack(Of Long),q=New List(Of String),i=Nothing,t=0,c=0
Function A(n)
For Each c In n
If Long.TryParse(c,t)Then
i=i &"0"+t
Else
If c<>" "Then q.Add(c)
If i<>A Then s.Push(i)
i=A
End If
If i=A Then E
Next
If i<>A Then s.Push(i)
E
A=s
End Function
Sub E()
c=s.Count
If c=0Then Exit Sub
For Each op In q
If op="-"Or op="d"Or c>1Then
Select Case op
Case"*"
s.Push(s.Pop*s.Pop)
Case"+"
s.Push(s.Pop+s.Pop)
Case"="
s.Push(-(s.Pop=s.Pop))
Case"-"
s.Push(-s.Pop)
Case"d"
s.Push(s.Peek)
End Select
q.Remove(op)
E
Exit Sub
End If
Next
End Sub

The entry point is Function A, which takes a string as input and returns a Stack(Of Long).

Symbols:

• Addition - +
• Multiplication - *
• Equality - =
• Negation - -
• Duplication - d

Overview:

Function A takes the input and tokenizes it. It uses a Long? to do a running total for multi-digit integers, which Nothing signifying we are not currently reading an integer.

Subroutine E takes the stack of integers and queue of operators, and evaluates the anyfix notation. It calls itself recursively until there are no actions left.

I declare global params all at once to save bytes on both declaration and parameter passing.

The return value from A is set by assigning a value to the matching variable A.

VB True is equivalent to -1, so that operation has to negate the result to get the correct value.

Try it online!

Answer 6

6502 machine code (C64), 697 bytes

00 C0 A2 00 86 29 86 26 86 27 86 28 86 4B 86 4C 86 CC 20 E4 FF F0 FB C9 0D F0
10 C9 20 30 F3 A6 27 9D B7 C2 20 D2 FF E6 27 D0 E7 C6 CC A9 20 20 1C EA A9 0D
20 D2 FF 20 95 C0 20 09 C1 20 95 C0 A6 26 E4 27 F0 4E BD B7 C2 E6 26 C9 20 F0
E8 C9 2D D0 09 A6 4C A9 01 9D B7 C3 D0 32 C9 22 D0 09 A6 4C A9 02 9D B7 C3 D0
25 C9 2B D0 09 A6 4C A9 81 9D B7 C3 D0 18 C9 2A D0 09 A6 4C A9 82 9D B7 C3 D0
0B C9 3D D0 0D A6 4C A9 83 9D B7 C3 E6 28 E6 4C D0 A3 4C 8A C2 A6 29 F0 6F A4
28 F0 6B CA F0 4B C6 28 A6 4B E6 4B BD B7 C3 F0 F5 30 14 AA CA D0 0B 20 7B C2
20 E1 C1 20 4D C2 D0 D9 20 5C C2 D0 D4 29 0F AA CA D0 0B 20 6D C2 20 08 C2 20
4D C2 D0 C3 CA D0 0B 20 6D C2 20 16 C2 20 4D C2 D0 B5 20 6D C2 20 F4 C1 20 4D
C2 D0 AA A4 4B B9 B7 C3 F0 02 10 AC C8 C4 4C F0 0F B9 B7 C3 F0 F6 30 F4 AA A9
00 99 B7 C3 F0 A6 60 A0 00 A6 26 E4 27 F0 15 BD B7 C2 C9 30 30 0E C9 3A 10 0A
E6 26 99 37 C4 C8 C0 05 D0 E5 C0 00 F0 08 A9 00 99 37 C4 20 39 C2 60 A2 FF E8
BD 37 C4 D0 FA A0 06 88 CA 30 0A BD 37 C4 29 0F 99 37 C4 10 F2 A9 00 99 37 C4
88 10 F8 A9 00 8D 3D C4 8D 3E C4 A2 10 A0 7B 18 B9 BD C3 90 02 09 10 4A 99 BD
C3 C8 10 F2 6E 3E C4 6E 3D C4 CA D0 01 60 A0 04 B9 38 C4 C9 08 30 05 E9 03 99
38 C4 88 10 F1 30 D2 A2 06 A9 00 9D 36 C4 CA D0 FA A2 10 A0 04 B9 38 C4 C9 05
30 05 69 02 99 38 C4 88 10 F1 A0 04 0E 3D C4 2E 3E C4 B9 38 C4 2A C9 10 29 0F
99 38 C4 88 10 F2 CA D0 D6 C0 05 F0 06 C8 B9 37 C4 F0 F6 09 30 9D 37 C4 E8 C8
C0 06 F0 05 B9 37 C4 90 F0 A9 00 9D 37 C4 60 A9 FF 45 FC 85 9F A9 FF 45 FB 85
9E E6 9E D0 02 E6 9F 60 A2 00 86 9F A5 FB C5 FD D0 07 A5 FC C5 FE D0 01 E8 86
9E 60 A5 FB 18 65 FD 85 9E A5 FC 65 FE 85 9F 60 A9 00 85 9E 85 9F A2 10 46 FC
66 FB 90 0D A5 FD 18 65 9E 85 9E A5 FE 65 9F 85 9F 06 FD 26 FE CA 10 E6 60 20
33 C1 A6 29 AD 3D C4 9D 3F C4 AD 3E C4 9D 3F C5 E6 29 60 A6 29 A5 9E 9D 3F C4
A5 9F 9D 3F C5 E6 29 60 A6 29 BD 3E C4 9D 3F C4 BD 3E C5 9D 3F C5 E6 29 60 C6
29 A6 29 BD 3F C4 85 FD BD 3F C5 85 FE C6 29 A6 29 BD 3F C4 85 FB BD 3F C5 85
FC 60 A6 29 BD 3E C5 10 13 20 7B C2 20 E1 C1 20 4D C2 A9 2D 20 D2 FF A6 29 BD
3E C5 8D 3E C4 BD 3E C4 8D 3D C4 20 8B C1 A9 37 A0 C4 4C 1E AB

Online demo

Usage sys49152, then enter the anyfix expression and press return.

• close to no error checking, so expect funny outputs on invalid expressions.
• the symbol for multiplication is *, all others as suggested.
• maximum input length is 256 characters, there can be no more than 127 operators queued.
• The input routine doesn't handle control characters, so don't mistype ;)
• integers are 16bit signed, overflow will silently wrap around.
• byte count is a bit large because this CPU doesn't even know multiplication and the C64 OS / ROM doesn't give you any integer arithmetics or conversions to/from decimal strings.

Here's the readable ca65-style assembler source code.