Balanced brackets: Difference between revisions
→{{header|J}}: Generate & test pairs |
→{{header|C++}}: Added C++ implementation |
||
Line 10: | Line 10: | ||
[][] OK ][][ NOT OK |
[][] OK ][][ NOT OK |
||
[[][]] OK []][[] NOT OK |
[[][]] OK []][[] NOT OK |
||
=={{header|C++}}== |
|||
<lang cpp>#include <algorithm> |
|||
#include <iostream> |
|||
#include <string> |
|||
std::string generate(int n, char left = '[', char right = ']') |
|||
{ |
|||
std::string str = std::string(n, left) + std::string(n, right); |
|||
std::random_shuffle(str.begin(), str.end()); |
|||
return str; |
|||
} |
|||
bool balanced(const std::string &str, char left= '[', char right= ']') |
|||
{ |
|||
int count = 0; |
|||
for (std::string::const_iterator it = str.begin(); it != str.end(); ++it) |
|||
{ |
|||
if (*it == left) |
|||
count++; |
|||
else if (*it == right) |
|||
if (--count < 0) return false; |
|||
} |
|||
return count == 0; |
|||
} |
|||
int main() |
|||
{ |
|||
srand(time(NULL)); // seed rng |
|||
for (int i = 1; i < 9; ++i) |
|||
{ |
|||
std::string s(generate(i)); |
|||
std::cout << (balanced(s) ? " ok: " : "bad: ") << s << "\n"; |
|||
} |
|||
}</lang> |
|||
Output: |
|||
<pre>bad: ][ |
|||
ok: [][] |
|||
bad: ]][[][ |
|||
bad: ]][][[[] |
|||
ok: [][][[]][] |
|||
bad: []][[]][[]][ |
|||
ok: [[[][][]]][][] |
|||
bad: [[][]]]]][[[[]][ |
|||
</pre> |
|||
=={{header|D}}== |
=={{header|D}}== |
Revision as of 04:18, 21 February 2011
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
Task:
- Generate a string with opening brackets (“
[
”) and closing brackets (“]
”), in some arbitrary order. - Determine whether the string is balanced; that is, whether it consists entirely of pairs of opening/closing brackets (in that order), none of which mis-nest.
Examples:
(empty) OK [] OK ][ NOT OK [][] OK ][][ NOT OK [[][]] OK []][[] NOT OK
C++
<lang cpp>#include <algorithm>
- include <iostream>
- include <string>
std::string generate(int n, char left = '[', char right = ']') {
std::string str = std::string(n, left) + std::string(n, right); std::random_shuffle(str.begin(), str.end()); return str;
}
bool balanced(const std::string &str, char left= '[', char right= ']') {
int count = 0; for (std::string::const_iterator it = str.begin(); it != str.end(); ++it) { if (*it == left) count++; else if (*it == right) if (--count < 0) return false; } return count == 0;
}
int main() {
srand(time(NULL)); // seed rng for (int i = 1; i < 9; ++i) { std::string s(generate(i)); std::cout << (balanced(s) ? " ok: " : "bad: ") << s << "\n"; }
}</lang> Output:
bad: ][ ok: [][] bad: ]][[][ bad: ]][][[[] ok: [][][[]][] bad: []][[]][[]][ ok: [[[][][]]][][] bad: [[][]]]]][[[[]][
D
<lang d>import std.stdio, std.algorithm, std.string, std.random;
auto generate(int n) {
auto r = "[]".repeat(n).dup; randomShuffle(r); return r;
}
void main() {
foreach (i; 0 .. 9) { auto s = generate(i); writefln("%-16s %s", s, s.balancedParens('[',']') ? "OK" : "bad"); }
}</lang> One output:
OK [] OK [[]] OK ]][[][ bad ]][[][[] bad [[[][]][]] OK [[]][[][]][] OK []]]][[[[[]]][ bad [[[[][[]][]]]][] OK
J
Solution: <lang j>genBracketPairs =: (?~@# { ])@#"0 1&'[]' NB. bracket pairs in arbitrary order bracketDepth =: '[]' -&(+/\)/@:(=/) ] checkBalanced =: _1 -.@e. bracketDepth</lang> Examples:<lang j> (,&' ' , ('bad';'OK') {::~ checkBalanced)"1 genBracketPairs i. 10
OK
][ bad
][[] bad
[[[]]] OK
[][[]][] OK
[][[[][]]] OK
[]][]][]][[[ bad
[[]][[][][]][] OK
]]]][[][][[[[]][ bad
[]]][][][[[[]][[]] bad</lang>
Comments: This task highlights the versatility and usefulness of J's scanning modifiers, /
and \
.
The checkBalanced
verb would need modification ( checkBalanced =: ((0 = {:) *. _1 -.@e. ])@bracketDepth
) if the task was extended to include uneven numbers of opening and closing brackets.
Perl 6
<lang perl6>sub balanced($s) {
my $l = 0; for $s.comb { when "]" { --$l; return False if $l < 0; } when "[" { ++$l; } } return $l == 0;
}
my $N = get; my $s = (<[ ]> xx $N).pick(*).join; say "$s {balanced($s) ?? "is" !! "is not"} well-balanced"</lang>
PureBasic
<lang PureBasic>Procedure.s Generate(N)
For i=1 To N sample$+"[]" Next For i=Len(sample$)-1 To 2 Step -1 r=Random(i-1)+1 If r<>i a.c=PeekC(@sample$+r*SizeOf(Character)) b.c=PeekC(@sample$+i*SizeOf(Character)) PokeC(@sample$+r*SizeOf(Character), b) PokeC(@sample$+i*SizeOf(Character), a) EndIf Next ProcedureReturn sample$
EndProcedure
Procedure Balanced(String$)
Protected *p.Character, cnt *p=@String$ While *p\c If *p\c='[' cnt+1 ElseIf *p\c=']' cnt-1 If cnt<0: Break: EndIf EndIf *p+SizeOf(Character) Wend If cnt=0 ProcedureReturn #True EndIf
EndProcedure
- - Test code
OpenConsole() For i=1 To 5
TestString$ = Generate(i) Print(TestString$) If Balanced(TestString$) PrintN(" is ballanced.") Else PrintN(" is not ballanced") EndIf
Next</lang> Output sample
[] is ballanced. [[]] is ballanced. [[[]]] is ballanced. [][]]][[ is not ballanced [][][][]][ is not ballanced
Python
<lang python>>>> def gen(N): ... txt = ['['] * N + [']'] * N ... random.shuffle( txt ) ... return .join(txt) ... >>> def balanced(txt): ... braced = 0 ... for ch in txt: ... if ch == '[': braced += 1 ... if ch == ']': ... braced -= 1 ... if braced < 0: return False ... return braced == 0 ... >>> for txt in (gen(N) for N in range(10)): ... print ("%-22r is%s balanced" % (txt, if balanced(txt) else ' not')) ... is balanced '[]' is balanced '[][]' is balanced '][[[]]' is not balanced '[]][[][]' is not balanced '[][[][]]][' is not balanced '][]][][[]][[' is not balanced '[[]]]]][]][[[[' is not balanced '[[[[]][]]][[][]]' is balanced '][[][[]]][]]][[[[]' is not balanced</lang>
Tcl
<lang tcl>proc generate {n} {
if {!$n} return set l [lrepeat $n "\[" "\]"] set len [llength $l] while {$len} {
set tmp [lindex $l [set i [expr {int($len * rand())}]]] lset l $i [lindex $l [incr len -1]] lset l $len $tmp
} return [join $l ""]
}
proc balanced s {
set n 0 foreach c [split $s ""] {
# Everything unmatched is ignored, which is what we want switch -exact -- $c { "\[" {incr n} "\]" {if {[incr n -1] < 0} {return false}} }
} expr {!$n}
}
for {set i 0} {$i < 15} {incr i} {
set s [generate $i] puts "\"$s\"\t-> [expr {[balanced $s] ? {OK} : {NOT OK}}]"
}</lang> Sample output:
"" -> OK "][" -> NOT OK "]][[" -> NOT OK "]]][[[" -> NOT OK "[][][[]]" -> OK "[[[][[]]]]" -> OK "[][][[][]][]" -> OK "[[]][]]]][[[][" -> NOT OK "][][[][][][[]]][" -> NOT OK "][[[][]][]]][][[][" -> NOT OK "]][][]][[][[][[]][][" -> NOT OK "[[[][[][]]][]]][[]]][[" -> NOT OK "[[]]][]][[[[]]][[][][[]]" -> NOT OK "][[][][]][[[]][[[[][]]]][]" -> NOT OK "]][[][[][[[[]][[][]][[]]]]][" -> NOT OK
TUSCRIPT
<lang tuscript>$$ MODE DATA $$ SET brackets=*
[ [] ][ []] ][][ ][][] [[[]][ []][[[] ][][][[] ][]][][[] []][[]][[] ][[]]][]]][ [[]][[[[]]]] [[]] [[[[]]]]
[[]][][]]]][[ _____________ $$ BUILD X_TABLE brackets=*
[[(4 ]] )4 [[[ (3 ]]] )3 (2 )2 [ (1 ] )1
$$ MODE TUSCRIPT LOOP b=brackets status=CHECK_BRACKETS (b,brackets,a1,e1,a2,e2) PRINT b," ",status ENDLOOP</lang> Output:
[ ERROR [] OK ][ ERROR []] ERROR ][][ ERROR ][][] ERROR [[[]][ ERROR []][[[] ERROR ][][][[] ERROR ][]][][[] ERROR []][[]][[] ERROR ][[]]][]]][ ERROR [[]][[[[]]]] OK [[]] OK [[[[]]]] OK [[]][][]]]][[ ERROR _____________ OK