# No parentheses shall be omitted

This expression actually has an omitted pair of parentheses.

1 + 2 * 3


To make things clear, it should be,

1 + (2 * 3)


Even this has its parentheses missing.

1 + 2 + 3


It actually means,

(1 + 2) + 3


People often assume left-to-right evaluation to such an arithmetic expression, but I want to make everything very clear.

Given an arithmetic expression, add parentheses until the order of evaluation is clear without any assumption, and don't remove any pre-existing parentheses.

Here are some examples of possible inputs and their expected output.

IN
OUT

IN  1
OUT 1

IN  (((1)))
OUT (((1)))

IN  1+2+3+4+5
OUT (((1+2)+3)+4)+5

IN  1/2/3/4/5
OUT (((1/2)/3)/4)/5

IN  1/2/((3/4))/5
OUT ((1/2)/((3/4)))/5

IN  1+2-3*4/5+6-7*8/9
OUT (((1+2)-((3*4)/5))+6)-((7*8)/9)

IN  1+(2-3*4/5+6-7)*8/9
OUT 1+(((((2-((3*4)/5))+6)-7)*8)/9)


The expression will be composed of single-digit numbers, operators (+, -, *, /), and parentheses. The typical rules of evaluation apply; left-to-right, parentheses first, multiplication first.

The input may have whitespaces, which has no effect, but your program should be able to handle them. The output must have no whitespace and have the same format as given in the examples. The input should be read either as a command line argument or from stdin, and the code should be runnable with no additional code.

This is a code-golf challenge.

Here's a rather formal definition of an arithmetic expression.

primary-expression
[0-9]
(arithmetic-expression)

multiplicative-expression
primary-expression
multiplicative-expression (* | /) primary-expression

multiplicative-expression

arithmetic-expression


This is a python script that you can use to validate your output (in a very manual way..).

I had fun writing Lisp in Python.

def addop(op):
return op == '+' or op == '-'

def match(l):
if l[1:] == []:
return [1, l]
if l[3:] == [] or addop(l[3]):
return [3, l[0:3]]
else:
m = match(l[2:])
return [m[0] + 2, l[0:2] + [m[1]]]
else:
if l[3:] == [] or addop(l[3]):
return [3, l[0:3]]
else:
m = match([l[0:3]] + l[3:])
return [m[0] + 2, m[1]]

def tree__(l):
m = match(l)
if l[m[0]:] == []:
return m[1]
else:
return tree__([m[1]] + l[m[0]:])

def tree_(l):
if l == []:
return []
elif isinstance(l[0], list):
return [tree_(tree__(l[0]))] + tree_(l[1:])
else:
return [l[0]] + tree_(l[1:])

def tree(l):
return tree_(tree__(l))

def afterParen(s, n):
if s == '':
return '';
if s[0] == '(':
return afterParen(s[1:], n + 1)
if s[0] == ')':
if n == 0:
return s[1:]
else:
return afterParen(s[1:], n - 1)
else:
return afterParen(s[1:], n)

def toList(s):
if s == '' or s[0] == ')':
return []
elif s[0] == '(':
return [toList(s[1:])] + toList(afterParen(s[1:], 0))
elif s[0].isspace():
elif s[0].isdigit():
return [int(s[0])] + toList(s[1:])
else:
return [s[0]] + toList(s[1:])

def toString(l):
if l == []:
return ''
elif isinstance(l[0], list):
return '(' + toString(l[0]) + ')' + toString(l[1:])
elif isinstance(l[0], int):
return str(l[0]) + toString(l[1:])
else:
return l[0] + toString(l[1:])

exp = "1+2*3+4+2+2-3*4/2*4/2"
print(exp)
exp = "((1+2*(3+4)+(((((2))+(2-3*4/2)*4)))/2))"
print(exp)

• Maybe add some test cases, e.g. 1/2/3
Jan 4 at 10:35
• @Adám Due to left-to-right evaluation, that should be (1/2)/3 Jan 4 at 10:36
• Best if you have some test cases listed on their own in the OP. This makes it all so much clearer. Jan 4 at 11:46
• can 1*2 give (1*2) Jan 4 at 18:10
• @Noodle9 I made a big edit to make things clear, but even before the edit it had the example that 1+2*3+4+2+2-3*4/2*4/2 should output ((((1+(2*3))+4)+2)+2)-((((3*4)/2)*4)/2), and I thought it was clear enough. Jan 4 at 19:02

# Pip 1.0, 20 19 bytes

a&TM(ST V"{}"Ja)DCs


Attempt This Online!

Verify all test cases

### Explanation

Episode 2 in the "Hey, my language happens to do exactly that!" saga...

In Pip 1.0, the string representation of a function is derived by "unparsing" the function's parse tree. Because I was lazy, I decided to just put parentheses around every subexpression, rather than trying to eliminate the parentheses that weren't necessary. Also, because I was lazy, redundant layers of parenthesization are kept in the parse tree, so they also remain in the string representation.

Thus, all this program does is convert the input to a function, get that function's string representation, and delete a few extra characters. The empty string is a corner case that costs +2 bytes.

a&TM(ST V"{}"Ja)DCs
a                    First command-line argument
&                   If it is truthy (not empty or 0), then:
"{}"          This string
Ja        Joined on the argument (essentially, wrap the arg in {})
V              Eval the resulting string as a Pip expression
The string will always be a valid function literal, so
the result is a Pip function
ST                Stringify
TM(          )       Trim off the curly braces
DCs    Delete all spaces
If the arg is falsey, use the arg itself ("" or "0")


# Retina 0.8.2, 237 bytes

\s

+1(?<=(^|$$)?)(\d|\(((\()|(?<-4>$$)|[^()])+(?(4)$)\))[*/](\d|$$((\()|(?<-7>$$)|[^()])+(?(7)$)\))(?(1)(?!$|\))) ($&)
+1(?<=(^|$$)?)(\d|\(((\()|(?<-4>$$)|[^()])+(?(4)$)\))[-+](\d|$$((\()|(?<-7>$$)|[^()])+(?(7)$)\))(?(1)(?!$|\))) ($&)


Try it online! Link includes test cases. Explanation:

\s



Delete white space.

+


Repeat until no more replacements can be made.

1


Make only one replacement at a time.

(?<=(^|$$)?)  See whether this subexpression begins at the beginning of the string or after a (. (\d|\(((\()|(?<-4>$$)|[^()])+(?(4)$)\))  Match either a digit or a balanced subexpression (using a .NET balancing group). [*/]  Match either a * or a / sign. (\d|$$((\()|(?<-7>$$)|[^()])+(?(7)$)\))


Match another digit or balanced subexpression.

(?(1)(?!$|\)))  If the match started at the beginning of the string or after a (, it must not match at the end of the string or after a ), because this subexpression is already parenthesised (or is the whole expression, which does not need to be parenthesised). ($&)


Parenthesise this match.

+1(?<=(^|$$)?)(\d|\(((\()|(?<-4>$$)|[^()])+(?(4)$)\))[-+](\d|$$((\()|(?<-7>$$)|[^()])+(?(7)$)\))(?(1)(?!$|\))) ($&)


Do the - and +` signs in the same way.