Translate an arithmetic expression to Brainfuck

Question

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.

Answer 1

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!

Answer 2

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