Task1
We use a stack to find the maximum number of valid parentheses:
#!/usr/bin/env perl
use strict;
use warnings;
use List::Util qw(max);
sub longest_parenthesis{
my @s = split '',$_[0];
my ($max,@stk) = (0,-1);
foreach my $i(0..$#s) {
if($s[$i] eq '(') {push @stk,$i}
else {
pop @stk;
if(@stk == 0) {push @stk,$i}
else {
$max = max($max,$i - $stk[$#stk])
}
}
}
$max
}
printf "%d\n",longest_parenthesis('(()())');
printf "%d\n",longest_parenthesis(')()())');
printf "%d\n",longest_parenthesis('((()))()(((()');
printf "%d\n",longest_parenthesis('))))((()(');
printf "%d\n",longest_parenthesis('()(()');
Task2
We use Depth First Search to search for all the possible solutions:
#!/usr/bin/env perl
use strict;
use warnings;
use Algorithm::Combinatorics qw(variations_with_repetition);
use List::Util qw(mesh);
use Data::Show;
sub magic_expression{
my ($str,$target) = @_;
my @ds = split '',$str;
my $it = variations_with_repetition(['+','-',,'*',''],$#ds);
my @res;
while(my $ops = $it->next) {
my $expr = join '',mesh(\@ds,[@$ops,'']);
next if $expr =~ /\b0[0-9]/;
my $eval = $expr =~ s/-/+-/gr;
$eval =~ s/(\d+)\*(\d+)/$1*$2/ge while $eval =~ /\*/;
$eval =~ s/(-?\d+)\+(-?\d+)/$1+$2/ge while $eval =~ /\+/;
push @res,$expr if $eval == $target
}
@res
}
show magic_expression("123",6);
show magic_expression("105",5);
show magic_expression("232",8);
show magic_expression("1324",10);
show magic_expression("1001",2)
