13
\$\begingroup\$

Write a program that translates an arithmetic expression to a Brainfuck program which evaluates the expression and prints the result in decimal numbers. For example, this arithmetic expression,

2 * (3 + 4)

can be translated to Brainfuck as,

++ 2
>+++ 3
>++++ 4
[-<+>]< add
<[>[->+>+<<]>[-<+>]<<-]>[-]>>[-<<<+>>>]<<< mul
[->+<]>[>>>>++++++++++<<<<[->+>>+>-[<-]<[<<[->>>+<<<]>>>>+<<-<]<<]
++++++++[->++++++<]>[-<+>]>>>>[-<<<<+>>>>]<[-]<<<]<[.<] print decimal

The Brainfuck program doesn't take input. However, each integer constant or operator in the original expression must have a distinct translated form contained in the resulting Brainfuck program.

This is the definition of an arithmetic expression.

primary-expression
  integer-constant
  (arithmetic-expression)

multiplicative-expression
  primary-expression
  multiplicative-expression multiplicative-operator primary-expression

additive-expression
  multiplicative-expression
  additive-expression additive-operator multiplicative-expression

arithmetic-expression
  additive-expression

additive-operator
  + | -

multiplicative-operator
  * | /

integer-constant
  a decimal constant in the range [0-255],
  which cannot start with '0' unless the number is 0

In other words, a multiplicative-expression is evaluated before anadditive-expression. An arithmetic-expression enclosed in parentheses is evaluated prior to the outer expressions. Otherwise, a chain of expressions is evaluated from left to right.

All whitespaces are ignored.

The Brainfuck machine to run the output will have 8-bit cells, each holding an unsigned integer. It is guaranteed that 255 + 1 == 0 and 0 - 1 == 255, so you can use this fact to implement your Brainfuck operations. At the same time, you may safely assume that the initial input of an arithmetic expression does not overflow or underflow during its evaluation.

This is a code-golf challenge.


The print function in the example BF code won't print anything if it reads 0. However, your program's BF output should print 0 if the result of the expression is 0. This BF function for example will print 0 for 0, but it's longer.

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

You are free to find or make a shorter version for any BF operation. Here is a list of common operations implemented in BF. This is a webpage where you can test BF code and also look at the memory dump.

\$\endgroup\$
16
  • \$\begingroup\$ @Arnauld The BF program doesn't have an input. The challenge is to translate a human-readable arithmetic expression to brainfuck terms. I've edited for clarity. \$\endgroup\$
    – xiver77
    Dec 16, 2021 at 12:37
  • 3
    \$\begingroup\$ I see what you mean now, thank you for clarifying. This might be a borderline non-observable requirement, although it applies to the output rather than the solution itself. (I personally think that's OK, but let's see what others have to say about that.) \$\endgroup\$
    – Arnauld
    Dec 16, 2021 at 12:45
  • \$\begingroup\$ Welcome to Code Golf! This looks like a fun challenge, but I think the lack of a specified way of converting it will make it difficult to determine what counts as enough computation. \$\endgroup\$ Dec 16, 2021 at 14:31
  • 1
    \$\begingroup\$ @RedwolfPrograms As I wrote "each integer constant or operator must have a distinct translated form contained in the resulting Brainfuck program", the borderline is objectively clear, I think. \$\endgroup\$
    – xiver77
    Dec 16, 2021 at 15:08
  • 1
    \$\begingroup\$ @Arnauld Made edits. You can ignore overflow or underflow. The print function's behavior was unintended. I added a different one which can print 0. \$\endgroup\$
    – xiver77
    Dec 16, 2021 at 16:47

2 Answers 2

4
\$\begingroup\$

JavaScript (Node.js),  427  417 bytes

s=>[...(a=s.match(/\d+|./g),o=[],d="+-/<>[]./",Buffer("kla`XslY`^KfMflY[`d^[jY`^jYa^ZeaXedfmY`f`t[[KfdM[CdtkqkqSMDsldd@@@@@[[MDd`iK^]kadX[fdD[Y^s@@@@MD@@XfMCtddM[[`dtkq[sk_V").map(c=>d+=d[c&7]+d[c/8&7]),g=S=>!(s=a.shift())|s==')'?o=[...o,...S]:g(S,s<')'?g([]):1/s?o.push(s):(h=_=>/u|[+-][*/]/.test(S[0]+s)?S.unshift(s):h(o.push(S.shift())))()))([]),'<'].map(s=>1/s?">"+"+".repeat(s):d.split`/`[d.indexOf(s)+3]).join``

Try it online!

Try the Brainfuck code online!

This is using the BF code provided in the challenge and the division algorithm suggested by Nitrodon.

Brainfuck compression

The BF code snippets are joined together with /'s. The resulting string is compressed by turning each pair of character codes \$(a,b)\$ into a single character of ASCII code \$N\in[64\dots 116]\$:

$$N=a+8b+64$$

where \$a\$ and \$b\$ are computed according to the following table:

+ - / < > [ ] .
0 1 2 3 4 5 6 7

Hence the decompression code:

d = "+-/<>[]./"
Buffer("... compressed data ...")
.map(c => d += d[c & 7] + d[c / 8 & 7])

Try it online!

Infix to postfix conversion

s => (                        // s = infix expression, as a string
  a = s.match(/\d+|./g),      // a[] = s split into numbers and operators
                              //       (including parentheses)
  o = [],                     // o[] = postfix output, as a list
  g =                         // g is a recursive function taking
  S =>                        // an operator stack S[]
  !(s = a.shift()) |          // s = next entry extracted from a[]
  s == ')' ?                  // if s is undefined or ')':
    o = [...o, ...S]          //   append S[] to o[]
  :                           // else:
    g(                        //   recursive call:
      S,                      //     pass S[] unchanged
      s < ')' ?               //     if s is '(':
        g([])                 //       recursive call with an empty stack
      :                       //     else:
        1 / s ?               //       if s is a number:
          o.push(s)           //         push it in o[]
        :                     //       else (s is an operator):
          ( h = _ =>          //         helper function:
            /u|[+-][*/]/      //           if S[0] is undefined or S[0] is
            .test(S[0] + s) ? //           '+' or '-' and s is '*' or '/':
              S.unshift(s)    //             insert s at the beginning of S[]
            :                 //           else:
              h(              //             recursive call:
                o.push(       //               extract the first entry of S[]
                  S.shift()   //               and push it in o[]
                )             //
              )               //             end of recursive call
          )()                 //         initial call to h()
    )                         //   end of recursive call
)([])                         // initial call to g()

Try it online!

Brainfuck output

o =>                          // o[] = postfix list
[...o, '<']                   // append a '<' to trigger the 'print'
.map(s =>                     // for each entry s:
  1 / s ?                     //   if s is a number:
    ">" +                     //     append a '>'
    "+".repeat(s)             //     followed by '+' repeated s times
  :                           //   else:
    d.split`/`[               //     split the BF code snippets
      d.indexOf(s) + 3        //     and append the relevant one
    ]                         //
).join``                      // end of map(); join everything

Try it online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ It's been I while I've posted this challenge, and your program is the only one with correct output, also with a clever compression approach. I see that some people click the green check for his/her favorite answer, and some people just leave it as is. Will it be okay for you to leave the answer unticked for future challengers? \$\endgroup\$
    – xiver77
    Jan 4, 2022 at 7:07
  • \$\begingroup\$ @xiver77 Not accepting any answer is fine. Also, we've recently decided to unpin the accepted answer on Code Golf because it doesn't make much sense on our site. \$\endgroup\$
    – Arnauld
    Jan 4, 2022 at 7:20
3
\$\begingroup\$

Python 3, 675 bytes

import shlex
s,b,o=[],'',{'+':'[-<+>]<','-':'[-<->]<','*':'<[>[->+>+<<]>[-<+>]<<-]>[-]>>[-<<<+>>>]<<<','/':'[->>>+<<<]<[->+>>+>-[<-]<[<<[->>>+<<<]>>>>+<<-<]<<]>>>>>[-<<<<<+>>>>>]<[-]<<[-]<[-]<'}
for c in list(shlex.shlex(input())):
 try:
  b+='>'+'+'*int(c)
 except:
  if c=='(':s+='('
  elif c==')':
   t=s.pop()
   while t!='(':b+=o[t];t=s.pop()
  else:
   while len(s)>0 and s[-1]!='('and c in'+-':b+=o[s.pop()]
   s+=c
for c in range(len(s)):b+=o[s.pop()]
print(b+'>>++++++++++<<[->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<]>>[-]>>>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>[-]>>[>++++++[-<++++++++>]<.<<+>+>[-]]<[<[->-<]++++++[->++++++++<]>.[-]]<<++++++[-<++++++++>]<.[-]<<[-<+>]<')

Try it online!

Example:

Input: (8 - 4 / 2) * 7 + 1

Output:

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

Output of brainfuck program: 43

\$\endgroup\$
7
  • 1
    \$\begingroup\$ I finally put in a division algorithm, and be warned, it sucks. \$\endgroup\$ Dec 16, 2021 at 19:33
  • \$\begingroup\$ Multiplication and division are traditionally evaluated left to right: 36 / 6 / 6 should be 1, not 36. (Also, division can be shorter.) \$\endgroup\$
    – Nitrodon
    Dec 16, 2021 at 21:37
  • \$\begingroup\$ What is shlex used for? If it just for removing spaces, there's shorter ways to do so. If it is neccesary though, you can omit the input() part \$\endgroup\$
    – Jo King
    Dec 16, 2021 at 22:57
  • 1
    \$\begingroup\$ @JoKing shlex is used for parsing the expression into the atomic units. For example shlex.shlex('1+(34*3)') evaluates to ['1', '(', '34', '*', '3', ')']. This makes translating the expression significantly easier. \$\endgroup\$ Dec 17, 2021 at 14:00
  • 1
    \$\begingroup\$ While I like your program is very simple and elegant, it still doesn't handle chained division correctly. 8/2/2/2 should be 1 for example, but your program's Brainfuck program outputs 4. It would be good to place a note that the program has to be fixed. \$\endgroup\$
    – xiver77
    Jan 4, 2022 at 7: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.