Parse basic arithmetic into an AST

Question

Introduction

An abstract syntax tree (AST) is a tree of tokens that shows their connection to each other and syntactical meaning. They are commonly used in compilers and static analysis tools, as parsing a language into an AST helps remove any ambiguity and can be helpful for optimizations. Many ASTs are large and complex, but in this thread, your task is to create a basic parser to convert an arithmetic expression into a basic AST.

Challenge

The main part of this challenge is resolving the order of operations. In this challenge, assume PEMDAS so that multiplication is before division and addition is before subtraction. Also, assume left associativity. Every node in the tree should either be an operator or a number. Operators with other operators as children resolve their children first, so nodes at the bottom of the tree resolve first. Number nodes should have no children. Your solution may assume the input is valid, all numbers are positive, and that the input contains no parentheses (unless you'd like to add support for fun).

The input will be a string with only the characters 0123456789+-*/ (and optionally ()). Your program/function may return nested objects/dictionaries, nested arrays/lists, or even a built-in data structure; as long as your output can be interpreted as a tree you're OK (note: if you are going to abuse this rule by using weird formats, then explain how it represents a tree).

Test cases

1+2+3*5-7 -> ['-', ['+', ['+', 1, 2], ['*', 3, 5]], 7], where the first element of the array is the operator, and the second and third are the children.

13*7+9-4+1 -> {op: '-', left: {op: '+', left: {op: '*', left: 13, right: 7}, right: 9}, right: {op: '+', left: 4, right: 1}}

8/2*6+4-1 -> ['-', ['+', ['/', 8, ['*', 2, 6]], 4], 1]

This is code-golf, so the shortest code wins!

Answer 1

Python, 69 68 bytes

f=lambda x:[*([i,*map(f,x.split(i,1))]for i in'-+/*'if i in x),x][0]

Attempt This Online!

Answer 2

sed, 96 bytes

s/^/x_/
:a
s/([^*/+-]*)\*([^*/+-]*)/['_',\1,\2]/
ta
y#/+-_SAD#*/+SADM#
/xM/!ba
s///
y#MDAS#*/+-#

Attempt This Online!

Answer 3

Wolfram Language 99 bytes

Wolfram Language have built-in tools for working with AST, for example

FullForm@MakeExpression@"1-(4/2)+3*(5+7)"

produce

HoldComplete[Plus[1,Times[-1,Times[4,Power[2,-1]]],Times[3,Plus[5,7]]]]

and

TreeForm@MakeExpression@"1-(4/2)+3*(5+7)"

produce

But firstly it looks like cheating. Secondly, it's a bit difficult to obtain the required form from WL output.
Maybe someone can do it, it will be interesting.
Here is a solution based on more common functions.

If[StringLength@#1 == 1,#1,#0/@StringSplit[#1, x__ ~~ # ~~ y__ :> {#,x,y}&/@ {"-", "+", "/", "*"}, 2][[2]]]&

Answer 4

JavaScript (Node.js), 82 bytes

f=(x,i=5,b,j=x.split(b=' */+-'[--i]))=>i?j[1]?[f(j.pop()),b,f(j.join(b))]:f(x,i):x

Try it online!

Seem not that golfed but anyway

Output is reversed

Answer 5

Vyxal 44 23 bytes

λ`+-:*`(n~ḟ0>[:∇ẇWfvx|_

Thanks to @emanresuA for full refactoring, I began to understand better how lambda works.

    λ        # Open lambda
    `+-:*`(  # Open loop over operators  
    n~ḟ0> [  # If there is such operator   
    :∇ẇWf   # Split and wrap into list  
    vx       # Recursive call lambda as map
    |_       # If there is no continue
             # ]); Closing If, loop and lambda   
                 expected but not required

Answer 6

Charcoal, 63 bytes

≔⟦Ｓ⟧θ⊞υθＦ-+/*ＦΦυ№§κ⁰ι«≔Ｅ⮌⪪⊟κι⟦λ⟧ζＦζ⊞υλＷ⊖Ｌζ⊞ζ⟦ι⊟ζ⊟ζ⟧Ｆ⊟ζ⊞κλ»⁻⭆¹θ'

Try it online! Link is to verbose version of code. Outputs values in one-element sublists and operators in three-element sublists. Explanation:

≔⟦Ｓ⟧θ

Wrap the input string in a list.

⊞υθ

Push it to the list of lists to be processed.

Ｆ-+/*

Loop over the operators in ascending order of precedence.

ＦΦυ№§κ⁰ι«

Loop over the terms that contain this operator.

≔Ｅ⮌⪪⊟κι⟦λ⟧ζ

Remove the term from its list, split it on the operator, and wrap all of the resulting terms in lists.

Ｆζ⊞υλ

Push all of those lists to the list of lists to be processed.

Ｗ⊖Ｌζ⊞ζ⟦ι⊟ζ⊟ζ⟧

Build up consecutive terms into a nested structure.

Ｆ⊟ζ⊞κλ

Re-insert the top-level terms back into the original list.

»⁻⭆¹θ'

Pretty-print the final list.

Answer 7

Retina, 53 bytes

+0`(\w+)\*(\w+)
aUb$1b$2c
4}T`V*/+-`_o
T`abcV`[,]*/+-

Try it online! Link includes test cases. Explanation: Port of @Jiří's sed answer.

(\w+)\*(\w+)
aUb$1b$2c

Replace (parameter)*(parameter) with [*,(parameter),(parameter)], except encoding * with U, [ with a, , with b and ] with c as they are all letters and will therefore be treated as part of the same parameter in subsequent replacements (both with the current operator and with subsequent operators of lower precedence).

0`

Only perform one replacement at a time.

+`

Repeat the above replacement until no more changes can be made.

T`V*/+-`_o

Step the operators and their encodings in sequence so that - becomes + etc. allowing each operator in turn to be encoded as a U, but those then in turn get stepped to previous vowels.

4}`

Repeat the whole of the above four times, once for each operator.

T`abcV`[,]*/+-

Translate all of the letter placeholders back to the characters they represent.

Answer 8

Haskell + hgl, 61 bytes

z#y=Fe<Rv<sQ[y<*χ z,z#y,p3 z]++y

gk$bkw$rF(#)(p<rv<dg_)"-+/*"

Explanation

This takes input as a string and outputs as a Free List String. In haskell a list can only contain one type of thing. A free list of strings is basically a list that is allowed to contain strings or other free lists of strings. That makes it the perfect sort of structure for this challenge.

A good deal of the machinery here is devoted to making things left associative. Right associativity would be quite easy, but if we naively modify the algorithm to be left associative it creates recursion without a base case. So what we do instead is that we actually just do right associativity but parse the entire thing backwards. Of course this means we have to do a bunch of extra reversing things, but that's how it goes.

For reference here's a right associative version:

z#y=Fe<sQ[pp[z],y<*χ z,z#y]++y

gk$rF(#)(p<dg_)"-+/*"

It's 9 bytes shorter.

The actual code is quite extensible. We do a fold over a list of operations, and adding new operations is as simple as adding their symbol in the right spot (later entries have higher precedence).

Reflection

This is pretty alright, there could be some improvements.

• m p should get a shorthand. I keep thinking it already exists, but I can't find it, so I should make it.
• I wasn't able to use (*:*), but if it had a prefix version I could.
• Although I use p3, I did at one point have a chain of 4 ps, so I guess p4 has a potential use.
• bkw doesn't save any bytes here over just using Rv. It's a nice little function and I was excited to use it here, but it seems of limited use. Probably not deserving of a 2 byte name though.

Answer 9

Go, 79 bytes

import(."go/parser";."go/ast")
func f(s string)Expr{e,_:=ParseExpr(s)
return e}

Attempt This Online!

Returns an ast.Expr from go/ast in Go's standard library, which represents a Go expression.