Balanced brackets: Difference between revisions
(an alternative Perl 6 solution) |
m (→{{header|C++}}) |
||
Line 145: | Line 145: | ||
} |
} |
||
bool balanced(const std::string &str, char left= '[', char right= ']') |
bool balanced(const std::string &str, char left = '[', char right = ']') |
||
{ |
{ |
||
int count = 0; |
int count = 0; |
Revision as of 08:05, 22 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 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
Ada
brackets.adb: <lang Ada>with Ada.Numerics.Discrete_Random; with Ada.Text_IO; with Ada.Strings.Fixed; procedure Brackets is
package Random_Positive is new Ada.Numerics.Discrete_Random (Positive); Positive_Generator : Random_Positive.Generator; procedure Swap (Left, Right : in out Character) is Temp : constant Character := Left; begin Left := Right; Right := Temp; end Swap; function Generate_Brackets (Bracket_Count : Natural; Opening_Bracket : Character := '['; Closing_Bracket : Character := ']') return String is use Ada.Strings.Fixed; All_Brackets : String := Bracket_Count * Opening_Bracket & Bracket_Count * Closing_Bracket; begin for I in All_Brackets'Range loop Swap (All_Brackets (I), All_Brackets (Random_Positive.Random (Positive_Generator) mod (Bracket_Count * 2) + 1)); end loop; return All_Brackets; end Generate_Brackets; function Check_Brackets (Test : String; Opening_Bracket : Character := '['; Closing_Bracket : Character := ']') return Boolean is Open : Natural := 0; begin for I in Test'Range loop if Test (I) = Opening_Bracket then Open := Open + 1; elsif Test (I) = Closing_Bracket then if Open = 0 then return False; else Open := Open - 1; end if; end if; end loop; return True; end Check_Brackets;
begin
Random_Positive.Reset (Positive_Generator); Ada.Text_IO.Put_Line ("Brackets"); for I in 0 .. 4 loop for J in 0 .. I loop declare My_String : constant String := Generate_Brackets (I); begin Ada.Text_IO.Put_Line (My_String & ": " & Boolean'Image (Check_Brackets (My_String))); end; end loop; end loop;
end Brackets;</lang>
Output:
Brackets : TRUE []: TRUE ][: FALSE []][: FALSE ][][: FALSE ][][: FALSE [[]]][: FALSE [][][]: TRUE []]][[: FALSE ][][][: FALSE ]]][[[[]: FALSE [[[]][]]: TRUE [][][]][: FALSE [[][]]][: FALSE []]]][[[: FALSE
C#
<lang csharp>using System; using System.Linq;
class Program {
static bool IsBalanced(string text, char open = '[', char close = ']') { var level = 0; foreach (var character in text) { if (character == close) { if (level == 0) { return false; } level--; } if (character == open) { level++; } } return level == 0; }
static string RandomBrackets(int count, char open = '[', char close = ']') { var random = new Random(); return string.Join(string.Empty, (new string(open, count) + new string(close, count)).OrderBy(c => random.Next())); }
static void Main() { for (var count = 0; count < 9; count++) { var text = RandomBrackets(count); Console.WriteLine("\"{0}\" is {1}balanced.", text, IsBalanced(text) ? string.Empty : "not "); } }
}</lang> Sample output: <lang>"" is balanced. "[]" is balanced. "[]][" is not balanced. "[][][]" is balanced. "[[[]][]]" is balanced. "[][[][[]]]" is balanced. "[]][][][[][]" is not balanced. "[]]][][]][[][[" is not balanced. "[]]][]]][[][[][[" is not balanced.</lang>
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 = 0; i < 9; ++i) { std::string s(generate(i)); std::cout << (balanced(s) ? " ok: " : "bad: ") << s << "\n"; }
}</lang> Output:
ok: ok: [] ok: [][] bad: []][[] ok: [[[]][]] bad: ][[[[]][]] ok: [[[]][[]][]] bad: ]][[]][[[[][]] bad: [[]]]][]][[][[[]
D
D has a built-in method for this. <lang d>import std.stdio, std.algorithm, std.string, std.random;
void main() {
foreach (i; 0 .. 9) { auto s = "[]".repeat(i).dup; randomShuffle(s); writeln(s.balancedParens('[', ']') ? " OK: " : "bad: ", s); }
}</lang> One output:
OK: OK: [] bad: []][ OK: [][][] bad: [][]]][[ OK: [[[]][]][] bad: ][][[[][][]] bad: [[]][[]]]]][[[ bad: ][]]][[[[][][][]
F#
<lang fsharp>let isBalanced str =
let rec loop count = function | ']'::_ when count = 0 -> false | '['::xs -> loop (count+1) xs | ']'::xs -> loop (count-1) xs | [] -> count = 0 | _::_ -> false
str |> Seq.toList |> loop 0
let shuffle arr =
let rnd = new System.Random() Array.sortBy (fun _ -> rnd.Next()) arr
let generate n =
new string( String.replicate n "[]" |> Array.ofSeq |> shuffle )
for n in 1..10 do
let s = generate n printfn "\"%s\" is balanced: %b" s (isBalanced s)</lang>
Output:
"[]" is balanced: true "][][" is balanced: false "][[]][" is balanced: false "[][[]][]" is balanced: true "[[]][[]][]" is balanced: true "[[]][[[]][]]" is balanced: true "][[[]][[[]][]]" is balanced: false "][[][][]][[]][[]" is balanced: false "][[]][][]][[]][[[]" is balanced: false "][[]]][[][]][[]][[[]" is balanced: false
J
Solution: <lang j>bracketDepth =: '[]' -&(+/\)/@:(=/) ] checkBalanced =: _1 -.@e. bracketDepth genBracketPairs =: (?~@# { ])@#"0 1&'[]' NB. bracket pairs in arbitrary order</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.
Java
<lang java5>public class Brackets {
public static boolean checkBrackets(String str){ int mismatchedBrackets = 0; for(char ch:str.toCharArray()){ if(ch == '['){ mismatchedBrackets++; }else if(ch == ']'){ mismatchedBrackets--; }else{ return false; //non-bracket chars } if(mismatchedBrackets < 0){ //close bracket before open bracket return false; } } return mismatchedBrackets == 0; }
public static String generate(int n){ if(n % 2 == 1){ //if n is odd we can't match brackets return null; } String ans = ""; int openBracketsLeft = n / 2; int unclosed = 0; while(ans.length() < n){ if(Math.random() >= .5 && openBracketsLeft > 0 || unclosed == 0){ ans += '['; openBracketsLeft--; unclosed++; }else{ ans += ']'; unclosed--; } } return ans; }
public static void main(String[] args){ String[] tests = {"", "[]", "][", "[][]", "][][", "[[][]]", "[]][[]"}; for(int i = 0; i < 10; i++){ System.out.println(generate(i)); }
for(String test: tests){ System.out.println(test + ": " + checkBrackets(test)); } }
}</lang> Sample output (generate uses random numbers, so it should not be the same every time):
null [] null [[]] null [][[]] null [[[][]]] null : true []: true ][: false [][]: true ][][: false [[][]]: true []][[]: false
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>
A solution using junctions is possible, too. (Though it doesn't work in Rakudo yet, because state
isn't implemented.
<lang perl6>sub balanced($s) {
return none(my @l) < 0 and @l[* - 1] == 0 given @l = map { state $l = 0; $l += $_ eq "]" ?? -1 !! +1 }, $s.comb;
}
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 ... 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>
Ruby
<lang ruby>re = /\A # beginning of string
(?<bb> # begin capture group <bb> \[ # literal [ \g<bb>* # zero or more <bb> \] # literal ] )* # end group, zero or more such groups
\z/x # end of string
(0..9).each do |i|
s = "[]" * i
# There is no String#shuffle! method. # This is a Knuth shuffle. (s.length - 1).downto(1) do |a, b| b = rand(a + 1) s[a], s[b] = s[b], s[a] end
puts((s =~ re ? " OK: " : "bad: ") + s)
end
["[[]", "[]]", "[letters]"].each do |s|
puts((s =~ re ? " OK: " : "bad: ") + s)
end</lang>
One output:
OK: OK: [] bad: ][][ bad: ][][][ bad: ]]][[[][ bad: ][]][][][[ bad: ][[][]]]][[[ bad: ]][][[[]]][][[ OK: [][[][][[][]]][] OK: [[[[[]]][[][]]][]] bad: [[] bad: []] bad: [letters]
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