Balanced brackets: Difference between revisions
m (→{{header|Tcl}}: restore comment) |
m (→{{header|PureBasic}}: Update) |
||
Line 63: | Line 63: | ||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
⚫ | |||
{{incomplete|PureBasic|Strings are not generated.}} |
|||
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 |
Protected *p.Character, cnt |
||
*p=@String$ |
*p=@String$ |
||
Line 72: | Line 87: | ||
ElseIf *p\c=']' |
ElseIf *p\c=']' |
||
cnt-1 |
cnt-1 |
||
⚫ | |||
EndIf |
EndIf |
||
⚫ | |||
*p+SizeOf(Character) |
*p+SizeOf(Character) |
||
Wend |
Wend |
||
Line 79: | Line 94: | ||
ProcedureReturn #True |
ProcedureReturn #True |
||
EndIf |
EndIf |
||
EndProcedure |
EndProcedure |
||
Testing the procedure |
|||
;- Test code |
|||
<lang PureBasic>Debug Balanced("") ; #true |
|||
OpenConsole() |
|||
Debug Balanced("[]") ; #true |
|||
For i=1 To 5 |
|||
Debug Balanced("][") ; #false |
|||
TestString$ = Generate(i) |
|||
Debug Balanced("[][]") ; #true |
|||
Print(TestString$) |
|||
Debug Balanced("][][") ; #false |
|||
If Balanced(TestString$) |
|||
PrintN(" is ballanced.") |
|||
Debug Balanced("[]][[]") ; #false</lang> |
|||
Else |
|||
PrintN(" is not ballanced") |
|||
EndIf |
|||
Next</lang> |
|||
Output sample |
|||
[] is ballanced. |
|||
[[]] is ballanced. |
|||
[[[]]] is ballanced. |
|||
[][]]][[ is not ballanced |
|||
[][][][]][ is not ballanced |
|||
=={{header|Python}}== |
=={{header|Python}}== |
Revision as of 14:45, 20 February 2011
You are encouraged to solve this task according to the task description, using any language you may know.
Task:
- Generate a string with
$N
opening brackets ("["
) and$N
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
D
<lang d>import std.stdio, std.algorithm, std.string,
std.range, std.random, std.conv;
auto generate(int n) {
return text(map!((i){ return "[]"[uniform(0,2)]; })(iota(n)));
}
void main() {
foreach (i; 0 .. 14) { auto s = generate(i); writefln("%-15s is%s balanced", '"' ~ s ~ '"', s.balancedParens('[', ']') ? "" : " not"); }
}</lang> Output:
"" is balanced "[" is not balanced "][" is not balanced "[]]" is not balanced "][][" is not balanced "][][]" is not balanced "[[[]][" is not balanced "[]][[[]" is not balanced "][][][[]" is not balanced "][]][][[]" is not balanced "[]][[]][[]" is not balanced "][[]]][]]][" is not balanced "[[]][[[[]]]]" is balanced "[[]][][]]]][[" is not balanced
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