3
\$\begingroup\$

Introduction

Given a String containing an arithmetic expression, your task is to output a truthy or falsey value based on whether it contains unmatched parentheses.


Input

Your program should take in a String containing an arithmetic expression. It may take input in any way except assuming it to be present in a pre-defined variable. Reading from file, input box, modal dialog box etc. is fine. Taking input as function argument is allowed as well!


Output

Your program should output a truthy or falsey value based on whether the input String contains any unmatched parentheses. It may output in any way except except writing to a variable. Writing to file, screen, console, terminal etc. is allowed. Outputting with function return is allowed as well!


Rules

  • For the purpose of this challenge, a parentheses is defined as any one of [, {, (, ), }, ]. A parentheses is said to be unmatched if it does not have any corresponding opening/closing parentheses. For example, [1+3 does contain unmatched parentheses.

  • Ordering of parentheses does not matter in this challenge. So, ]1+3[ does not contain any unmatched parentheses. {[)(}] doesn't, as well.

  • The input String will only contain following characters : {, [, (, ), ], }, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, +, -, *, / and ^.

  • Your program should output a truthy value if the input String contains an unmatched parentheses.

  • Your program should output a falsey value if the input String does not contain an unmatched parentheses.

  • You must specify the truthy and falsey values in your post.

  • The input String will never be empty.

  • If the input String does not contain any parentheses, your program should output falsey value.

  • Standard loopholes apply.


Test Cases

Input            ->            Output

"{"                            Truthy
"{{{{}}"                       Truthy
"{[]}"                         Falsey
"[]]["                         Falsey
")()()()("                     Falsey
"1+4"                          Falsey
"{)"                           Truthy
"([)]"                         Falsey
"(()"                          Truthy
"2*{10+4^3+(10+3)"             Truthy
"-6+[18-{4*(9-6)}/3]"          Falsey
"-6+[18-{4*)9-6](/3}"          Falsey

Winning Criterion

This is , so the shortest code in bytes wins!


Note

I'll be adding a similar challenge but in which order will matter, after some time! Stay Tuned!

\$\endgroup\$
  • \$\begingroup\$ I'm 99% sure this is a dupe but I can't find the older one. \$\endgroup\$ – Stephen Jun 3 '17 at 16:14
  • \$\begingroup\$ @StephenS This one is the one that came to my mind, but I don't think it's quite a dupe... \$\endgroup\$ – ETHproductions Jun 3 '17 at 16:21
  • 3
    \$\begingroup\$ Possible duplicate of Are the brackets fully matched? \$\endgroup\$ – Stephen Jun 3 '17 at 19:42
  • 5
    \$\begingroup\$ @StephenS I think the fact that this is entirely orderless makes it quite different. Neither ][ or ([)] would be valid in the other challenge but are valid here. \$\endgroup\$ – Martin Ender Jun 3 '17 at 21:01
  • 2
    \$\begingroup\$ This question's title should really make it clearer that order is irrelevant. That's not what most people think about when talking about unmatched parentheses. \$\endgroup\$ – user62131 Jun 5 '17 at 16:30

17 Answers 17

3
\$\begingroup\$

05AB1E, 14 10 bytes

žuS¢2ô€ËP_

Try it online!

-4 thanks to Adnan.

1 for truthy, 0 for falsey.

Its main power point is the žu builtin.

Explanation:

žuS¢2ô€ËP_
žu         Push '()<>[]{}'
  S        Split into individual chars
   ¢       Count occurrences of each char in the input. For <>, the count will always be 0
    2      Push 2
     ô     Split the array into pieces of that length, corresponding to respective matching brackets
      €    Map next command over the chunks
       Ë   Check if all elements are equal. If equal, it means that the corresponding bracket type is matched. <> will always be matched, since they will never occur in the input, so they'll both always have 0 occurrences
        P  Take the product of the boolean values. <> won't affect this, since it would always be 1
         _ Logically negate, convert 1 to 0 and non-1 (always 0 in this case) to 1
\$\endgroup\$
  • 3
    \$\begingroup\$ Who doesn't have a command that pushes ()<>[]{}? \$\endgroup\$ – caird coinheringaahing Jun 3 '17 at 18:48
  • \$\begingroup\$ @cairdcoinheringaahing CJam doesn't, but you can get it with [{(<>)}]` . \$\endgroup\$ – Esolanging Fruit Jun 4 '17 at 5:57
  • \$\begingroup\$ @Challenger5 You just correctly ordered the brackets so that the (<>) won't affect the stack since it's in a code block, and then the codeblock goes into the list? Well, this challenge doesn't have <>, so you could just use [{()}]` or {[()]}` or even {([])}`. Oh wait a sec, you can actually use {()}a`. \$\endgroup\$ – Erik the Outgolfer Jun 4 '17 at 6:48
  • \$\begingroup\$ @EriktheOutgolfer Yeah, I forgot about that. \$\endgroup\$ – Esolanging Fruit Jun 4 '17 at 6:52
  • 1
    \$\begingroup\$ @Arjun They're not handled, since they'll never be in the input. \$\endgroup\$ – Erik the Outgolfer Jun 5 '17 at 7:51
4
\$\begingroup\$

Python 2, 47 bytes

lambda s:map(s.count,'([{')!=map(s.count,')]}')

Try it online! Test cases from musicman523.

Checks if list of counts for each type of open paren matches that for the corresponding close parens.

The program is one byte longer

q=input().count
print map(q,'([{')!=map(q,')]}')
\$\endgroup\$
2
\$\begingroup\$

Python 2, 61 bytes

Saved 4 bytes thanks to WheatWizard!

lambda s:any(s.count(i)^s.count(j)for i,j in['{}','[]','()'])

Try it online!

\$\endgroup\$
  • \$\begingroup\$ This can be made slightly shorter by ditching r. Try it online \$\endgroup\$ – Wheat Wizard Jun 3 '17 at 17:54
  • \$\begingroup\$ Thanks! I changed it to match the two characters into separate variables, removing the indexing and therefore saving 4 more bytes. \$\endgroup\$ – musicman523 Jun 3 '17 at 17:58
1
\$\begingroup\$

Python 3, 62 61 bytes

Surprisingly pythonic for codegolf.

lambda x:all(x.count(y)-x.count(z)for y,z in("[]","()","{}"))

-1 byte thanks to @musicman523

\$\endgroup\$
  • \$\begingroup\$ You can use musicman's trick to make this shorter. TIO \$\endgroup\$ – Wheat Wizard Jun 3 '17 at 17:58
  • 1
    \$\begingroup\$ And now we have the same answers :) Although your post came before my edit, I did come up with it independently \$\endgroup\$ – musicman523 Jun 3 '17 at 17:59
  • \$\begingroup\$ Yeah, I'll leave it as is. \$\endgroup\$ – L3viathan Jun 3 '17 at 18:00
  • \$\begingroup\$ You could change == to - and keep all, then we have the same byte count but different answers \$\endgroup\$ – musicman523 Jun 3 '17 at 18:01
  • \$\begingroup\$ @musicman523 Alright then! \$\endgroup\$ – L3viathan Jun 3 '17 at 18:04
1
\$\begingroup\$

Jelly, 17 bytes

ċЀ“[]{}()”s2E€ẠṆ

Try it online!

1 is truthy, 0 is falsey.

\$\endgroup\$
1
\$\begingroup\$

MATL, 15 bytes

!'[](){}'=sHeda

This outputs 1 if unmatched, 0 if matched.

Try it online!

Explanation

!          % Implicitly input string. Tranpose into vertical vector of chars
'[](){}'   % Push this string
=          % Compare for equalty, with broadcast
s          % Sum of each column. This gives the count of each char of '[](){}'
He         % Reshape as a two-row column (in column-major order)
d          % Difference of the two entries of each column
a          % Any: gives true (1) if some entry is nonzero, false (0) otherwise
           % Implicitly display
\$\endgroup\$
1
\$\begingroup\$

Javascript, 71 bytes:

x=>['()','[]','{}'].some(a=>x.split(a[0]).length!=x.split(a[1]).length)
\$\endgroup\$
1
\$\begingroup\$

Ruby, 58+1 = 59 bytes

+1 byte for the -n flag.

f=->c{$_.count c}
p %w"() [] {}".any?{|s|f[s[0]]!=f[s[1]]}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Javascript 57 bytes

x=>(g=z=>x.split(z).length,g`(`-g`)`|g`[`-g`]`|g`{`-g`}`)

Starting from asgallant's solution.

Matching returns 0. Non-matching returns non-zero.

\$\endgroup\$
0
\$\begingroup\$

Python 2, 85 bytes

I can definitely golf this using subtraction instead but I'm running out of time. D:

lambda s,c=str.count:(c(s,'(')!=c(s,')'))or(c(s,'{')!=c(s,'}'))or(c(s,'[')!=c(s,']'))

Try it online!

\$\endgroup\$
  • \$\begingroup\$ All instances of != can be -. \$\endgroup\$ – CalculatorFeline Jun 6 '17 at 21:52
  • \$\begingroup\$ This answer has already been out-golfed by a far better answer. Hence, I'd rather not try to golf this. \$\endgroup\$ – totallyhuman Jun 6 '17 at 21:56
0
\$\begingroup\$

PowerShell, 95 86 bytes

param($s)$h=@{};[char[]]$s|%{$h["$_"]++};$h.'['-$h.']'-or$h.'('-$h.')'-or$h.'{'-$h.'}'

Try it online!

Previous version

param($s)switch([char[]]$s){'('{$k++}')'{$k--}'['{$l++}']'{$l--}'{'{$m++}'}'{$m--}}$k-or$l-or$m

Try it online!

\$\endgroup\$
0
\$\begingroup\$

C#, 87 bytes

using System.Linq;s=>s.Count(c=>c=='['|c=='{'|c=='(')==s.Count(c=>c==']'|c=='}'|c==')')

Pretty self explanatory, just test to see if the of left parenthesis equals the count of right parenthesis.

\$\endgroup\$
  • \$\begingroup\$ Please check on {). \$\endgroup\$ – CalculatorFeline Jun 6 '17 at 21:54
0
\$\begingroup\$

PHP>7.1, 124 Bytes

$t=!!$p=preg_replace("#[\d+/*^-]#","",$argn);for(;$p;$p=substr($p,1,-1))$t*=chr(($o=ord($p[0]))%5?$o+2:$o+1)==$p[-1];echo$t;

Instead of #[\d+/*^-] you can use [^]{()}[] or [^\p{Pe}\p{Ps}]

IntlChar::charMirror IntlChar::charMirror($p[0])==$p[-1] instead of chr(($o=ord($p[0]))%5?$o+2:$o+1)==$p[-1] checks not if the char is an openining or closing punctation so we can not use it without additional check &$p[0]<$p[-1] +8 Bytes

Online Version

PHP, 151 bytes

A full Regex Solution

for($c=$t=!!$p=($r=preg_replace)("#[^]{()}[]#","",$argn);$p&&$c;)$p=$r(["#^{(.*)}$#","#^\[(.*)]$#","#^\((.*)\)$#"],[$a="$1",$a,$a],$p,1,$c);echo$t&!$p;

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Visual Basic.Net, 218 192 Bytes

function t(m as string,v as string)
return Len(m)-Len(m.Replace(v,""))
end function
function b(q as String)
return not(t(q,"{")=t(q,"}")and t(q,"[")=t(q,"]")and t(q,"(")=t(q,")"))
end function
\$\endgroup\$
  • \$\begingroup\$ "around 218 bytes" I count 217. Also, if (expr) then return false else return true can be return not (expr). \$\endgroup\$ – CalculatorFeline Jun 6 '17 at 21:54
  • \$\begingroup\$ "around 218 bytes" I count 192. Do you have a trailing newline? \$\endgroup\$ – CalculatorFeline Jun 6 '17 at 21:59
  • \$\begingroup\$ I dont know how to put line through 218 \$\endgroup\$ – polyglotrealIknow Jun 6 '17 at 22:00
  • \$\begingroup\$ <s>218</s> works. \$\endgroup\$ – CalculatorFeline Jun 6 '17 at 22:02
  • \$\begingroup\$ well I don't have trailing newline \$\endgroup\$ – polyglotrealIknow Jun 6 '17 at 22:09
0
\$\begingroup\$

Clojure, 65 bytes

 #(let[f(frequencies %)](some not(map =(map f"[{(")(map f"]})"))))

So long keywords :/ Returns nil for falsy and true for truthy.

\$\endgroup\$
0
\$\begingroup\$

Retina, 26 bytes

O`.
+`\(\)|\[]|{}

[^*-9^]

Try it online!

Explanation

O`.

Sort all characters so that corresponding brackets are adjacent (since neither \ nor | can appear in the input).

+`\(\)|\[]|{}

Repeatedly remove pairs of matching brackets.

[^*-9^]

Try to match any remaining brackets (the regex matches anything that isn't a ^ or in the ASCII range from * to 9 which, among the valid input characters, are only the 6 brackets). If we find any, that means that there was an unmatched one. The result will be a positive integer if the input was unbalanced, 0 otherwise.

\$\endgroup\$
  • \$\begingroup\$ {{{{}} is matched? Your code return 0 on that input. \$\endgroup\$ – user202729 Jun 7 '17 at 14:20
  • \$\begingroup\$ @user202729 Thanks, it should be fixed now (luckily at the same byte count). \$\endgroup\$ – Martin Ender Jun 7 '17 at 15:23
0
\$\begingroup\$

Javascript, 149 140 bytes

New solution incorporates bitwise operators (Thanks, arjun) and calculates if they are not equal, and uses or instead of and.

function f(x){return x.split("(").length!=x.split(")").length|x.split("{").length!=x.split("}").lengt|x.split("[").length!=x.split("]").length}

I don't yet have a snippet for this, so I'm not sure it works yet.

OLD SOLUTION:

function f(x){return !(x.split("(").length==x.split(")").length&&x.split("{").length==x.split("}").length&&x.split("[").length==x.split("]").length)}

Checks if there are the same amount of one bracket and another, and then returns the opposite.

function f(x){return !(x.split("(").length==x.split(")").length&&x.split("{").length==x.split("}").length&&x.split("[").length==x.split("]").length)}

/*"{"                            Truthy
"{[]}"                         Falsey
"[]]["                         Falsey
")()()()("                     Falsey
"1+4"                          Falsey
"{)"                           Truthy
"([)]"                         Falsey
"2*{10+4^3+(10+3)"             Truthy
"-6+[18-{4*(9-6)}/3]"          Falsey
"-6+[18-{4*)9-6](/3}"          Falsey*/

console.log(f("{"));
console.log(f("{[]}"));
console.log(f("[]]["));
console.log(f(")()()()("));
console.log(f("1+4"));
console.log(f("{)"));
console.log(f("([)]"));
console.log(f("2*{10+4^3+(10+3)"));
console.log(f("-6+[18-{4*(9-6)}/3]"));
console.log(f("-6+[18-{4*)9-6](/3}"));

\$\endgroup\$
  • \$\begingroup\$ I can save 3 bytes by making every == into a != And changing && to || but I'm on mobile \$\endgroup\$ – vityavv Jun 5 '17 at 18:55
  • \$\begingroup\$ I think, bitwise operators instead of logical ones will do fine. Like & instead of && and | instead of ||. \$\endgroup\$ – Arjun Jun 7 '17 at 6:54
  • \$\begingroup\$ You can remove the outermost paren after return !. \$\endgroup\$ – Arjun Jun 7 '17 at 6:55
  • \$\begingroup\$ Do you even need a space after return? \$\endgroup\$ – Zacharý Jun 7 '17 at 15:32
  • \$\begingroup\$ I think you need that space otherwise JavaScript will count it as rerurnx and throw an error \$\endgroup\$ – vityavv Jun 7 '17 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.