[今週の問題]カッコをつける
久しぶりに問題ですっ！
9 名前：大会告知の人 [sage]： 2008/08/31(日) 00:57:28.38 ID:HpRjEhge0
お久しぶりですっ，久々の問題投下ですっ
いくつか企画を用意していますが，前回久しぶりに大型企画やったら滑ったので
とりあえず普段の問題を１問投下して様子を見てみますっｗ
トリップ回答方式がちょっと厳しくなってきたので，通常の問題形式にしましたっ
解けてるかどうかすぐわかる問題なので，多分チェックいらないんじゃないかな・・・？
前の形式の方がいいーとかいうのが言ってくださいっ
できちゃったらソース貼っちゃっていただけるとうれしいですー，いろんな言語のソース期待してますっ
[問題]
「 ( 」と「) 」の２つが連続して含まれている文字列が与えられる．
左側に「 ( 」を，右側に「 ) 」を最小の個数追加し，括弧が全て閉じた状態になったものを出力せよ．
[入力例]→[出力例]
))((
→(())(())
)(()((
→()(()(()))
(())
→(())
)))()())))()))())()))()((((())())))((((())(((((())()((()()()(((()()((()()((((()()(((
→((((((((((()))()())))()))())()))()((((())())))((((())(((((())()((()()()(((()()((()()((((()()((()))))))))))))))))))))
以下みなさんの解答です。
ネタバレ注意！
一応、正解のものだけ載せてるつもりだけど間違いあるかも
主なアルゴリズムは以下の２つですね。若干違いはありますが。
探査→先頭から探査して、()を調べていく
括弧潰し→()の組を潰してうはｗw
Java
(に対して)を探して潰していく方法。
25 名前：以下、名無しにかわりましてVIPがお送りします [sage]： 2008/08/31(日) 01:14:30.31 ID:m7+XrTGS0
>>9
タブなしスマン。
public class Kakkotsuke{
public static void main(String args[]){
StringBuffer base = new StringBuffer(")))()())))()))())()))()((((())())))((((())(((((())()((()()()(((()()((()()((((()()(((");
String[] array= base.toString().split("");
for(int ii = 0;ii < array.length;ii++){
if(array[ii].compareTo("(") == 0){
for(int jj = ii+1;jj < array.length;jj++){
if(array[jj].compareTo(")") == 0){
array[jj] = ";";
array[ii] = ";";
break;
}
}
}
}
for(int ii = 0;ii < array.length;ii++){
if(array[ii].compareTo(")") == 0){
base.insert(0,"(");
}else if(array[ii].compareTo("(") == 0){
base.append(")");
}
}
System.out.println(base.toString());
}
}
Java(探査)
32 名前：以下、名無しにかわりましてVIPがお送りします [sage]： 2008/08/31(日) 01:19:47.48 ID:os/Nc6aF0
>>9
using System;
class Program
{
static void Main(string[] args)
{
while (true)
{
string s = Console.ReadLine();
int b = 0;
int c = 0;
foreach (char i in s)
switch (i)
{
case '(':
c++;
break;
case ')':
if (c == 0)
b++;
else
c--;
break;
}
Console.WriteLine(new string('(', b) + s + new string(')', c));
}
}
}
PHP(括弧潰し)
33 名前：以下、名無しにかわりましてVIPがお送りします []： 2008/08/31(日) 01:21:29.42 ID:z+nFazzU0
<?
$str = ')))()())))()))())()))()((((())())))((((())(((((())()((()()()(((()()((()()((((()()(((';
$tmp = $str;
while (strpos($tmp, '()') !== FALSE) {
$tmp = implode('', explode('()', $tmp));
}
echo str_repeat('(', strpos($tmp, '(')).$str.str_repeat(')', (strlen($tmp) - strpos($tmp, '(')))."\n";
?>
出力結果チェックするのめんどくせぇ、誰か頼む
Perl(探査)
42 名前：以下、名無しにかわりましてVIPがお送りします [sage]： 2008/08/31(日) 01:30:21.75 ID:m7+XrTGS0
もういっこできたよー。
多分あってると思うんだけれども。
my $str = ")))()())))()))())()))()((((())())))((((())(((((())()((()()()(((()()((()()((((()()(((";
my $backup = $str;
while($str =~ /^(.*)\(([^\)]*)\)(.*)/){
$str = $1.$2.$3;
}
my @ss = split(//,$str);
my $left = "";
my $right = "";
foreach my $s(@ss){
if( $s eq ")"){
$left .= "(";
}elsif($s eq "("){
$right .= ")";
}
}
print $left.$backup.$right;
Perl(探査)
46 名前：以下、名無しにかわりましてVIPがお送りします []： 2008/08/31(日) 01:35:52.01 ID:g1qVfdgm0
#/bin/usr/local/perl
while(<>) # 標準入力や「それっぽいファイル」から一行読み込む
{
my $line = $_; # 読み込んだ一行を $line に代入
$line =~ s/\s//g; # 改行を取り除くついでに空白も取り除く（コピペすると最後に空白が付くから）
last if( $line eq '' or $line =~ /[^()]/ ); # 空行か括弧以外が含まれていたら終了
my ($last,$min) = CheckParenthesis($line); # 括弧の数を数えて、最後の状態と最小の状態を取得
$left = 0; if( $min < 0 ) { $left = -$min; $last += $left; }
$right = $last; if( $last < 0 ) { $right = -$last; }
print '→'.('('x$left).$line.(')'x($right))."\n";
}
sub CheckParenthesis
{
my $line = shift;
my ($last,$min) = (0,0);
$line =~ s<([()])>
{
my $c = $1;
++$last if $c eq '(';
--$last if $c eq ')';
$min = $last if $min > $last;
}mesg;
return($last,$min);
}
Perl(括弧潰し)
56 名前：以下、名無しにかわりましてVIPがお送りします []： 2008/08/31(日) 01:43:21.26 ID:g1qVfdgm0
>>49とても短くなったｗｗｗｗ
#/bin/usr/local/perl
while(<>) # 標準入力や「それっぽいファイル」から一行読み込む
{
my $line = $_; # 読み込んだ一行を $line に代入
$line =~ s/\s//g; # 改行を取り除くついでに空白も取り除く（コピペすると最後に空白が付くから）
last if( $line eq '' or $line =~ /[^()]/ ); # 空行か括弧以外が含まれていたら終了
my $tmp = $line;
1 while $tmp =~ s/\(\)//g;
my ($left,$right) = (0,0);
$tmp =~ s<([()])>{if($1 eq')'){++$left;}elsif($1 eq'('){++$right;}}mesg;
print '→'.('('x$left).$line.(')'x($right))."\n";
}
C言語(探査)
58 名前：以下、名無しにかわりましてVIPがお送りします []： 2008/08/31(日) 01:45:15.11 ID:LuXbwKno0
くそう、へんなとこで手間取った
#include <stdio.h>
int main( int argc, char* argv[] )
{
char* p;
int l=0, r=0;
if( argc<2 ){printf("arg error.\n");return 0;}
p = argv[1];
while( *p ){
if( *p == ')' ){
if( r ) r--;
else l++;
}else if ( *p == '(' ) r++;
p++;
}
{
int i;
for( i = 0; i < l; i++ ) printf("(");
printf(argv[1]);
for( i = 0; i < r; i++ ) printf(")");
printf("\n");
}
return 1;
}
Perl(探査)
69 名前：以下、名無しにかわりましてVIPがお送りします [sage]： 2008/08/31(日) 01:52:23.33 ID:LCsbnm3L0
これでいいのか？
#!/usr/bin/perl
my $r = 0;
my $l = 0;
while (<STDIN>) {
chomp;
for my $i (0..(length($_) - 1)) {
my $char = substr($_, $i, 1);
if ($char eq '(') {
++$l;
} elsif ($char eq ')') {
if ($l > 0) {
--$l;
} else {
++$r;
}
} else {
die "invalid character $char";
}
}
printf "%s%s%s\n", ('(' x $r), "$_", (')' x $l);
}
HSP
頭からとケツからダブルで探査してるのでO(2N)
70 名前：以下、名無しにかわりましてVIPがお送りします [sage]： 2008/08/31(日) 01:52:33.32 ID:0qt/tq1dP
>>59
これはひどい…
言語はHSP ゆとり言語で悪かったなｗｗｗ
()入れてもそのまま()が返ってくる
他のやり方のもできた
text=")))()())))()))())()))()((((())())))((((())(((((())()((()()()(((()()((()()((((()()((("
out=text
i=0:j=0:Left=0:Right=0
len=strlen(text)
repeat len
byte=peek(text,cnt)
if byte==')'{
if i:i--:else:Left++
}else:i++
byte=peek(text,len-cnt-1)
if byte=='('{
if j:j--:else:Right++
}else:j++
loop
repeat Right
out+=")"
loop
repeat Left
out="("+out
loop
mes out
C言語(探査)
77 名前：以下、名無しにかわりましてVIPがお送りします [sage]： 2008/08/31(日) 01:57:08.42 ID:HpRjEhge0
>>73
じゃあ一応用意してた模範解答張っちゃいますね，Cですっ
#include<stdio.h>
int main(){
char c[100];
int i, max = 0, now = 0;
scanf("%s",c);
for(i=0;c[i]!=0;i++){
if(c[i]==')') now++; else now--;
if(now>max) max=now;
}
for(i=0;i<max;i++) printf("(");
printf("%s",c);
for(i=0;i<max-now;i++) printf(")");
return 0;
}
Io(探査)
83 名前：以下、名無しにかわりましてVIPがお送りします [sage]： 2008/08/31(日) 02:00:34.27 ID:cMZ60bRQ0
block(s,
open := 0
close := 0
s foreach(v,
v switch(
40, open = open + 1,
41, if(open == 0,
close = close + 1,
open = open - 1)))
("(" repeated(close)) .. s .. (")" repeated(open))
) call(")))()())))()))())()))()((((())())))((((())(((((())()((()()()(((()()((()()((((()()(((")
J言語
括弧潰しとほぼおなじ？
t =: ‘))((‘みたいにして実行しまつ
92 名前：以下、名無しにかわりましてVIPがお送りします []： 2008/08/31(日) 02:06:08.67 ID:xuxV9OBB0
('('#~+/p=')'),t,')'#~+/'('=p=.t{~(i.#t)-.q#~2=+/"1(t{~"1 q=.(2,~<:#t)$}.2#i.#t)="1'()'
>>51だと出来なかったので修正
これで完璧だと思う
C++(探査)
137 名前：以下、名無しにかわりましてVIPがお送りします [sage]： 2008/08/31(日) 02:37:38.76 ID:jubv+1wf0
>>9
#include <iostream>
#include <string>
using namespace std;
int main(void) {
string input;
cin >> input;
int n = 0, min = 0;
for (string::iterator i = input.begin(); i != input.end(); ++ i) {
if (*i == '(') ++ n;
if (*i == ')') {
if (-- n < min) min = n;
}
}
string output = input;
if (min < 0) output.insert(0, -min, '(');
if (n > min) output.insert(output.length(), n-min, ')');
cout << output << endl;
}
sed(括弧潰し)
226 名前：以下、名無しにかわりましてVIPがお送りします [sage]： 2008/08/31(日) 09:51:06.70 ID:cs/kJrM40
>>155
sedだよっ！
おっきしたら、短くなったプロポーショナルフォント的に
h;:.;s.()..;t.;y.().:(.;G;:,;/:/s.$.).;s.:..;t,;s.\n..g
つかれたので解説は明日……
さてさて、ぱっと見Perlが多いが、
| 4 | Perl |
| 2 | C |
| 2 | Java |
といった順だった。
他には、プロトタイプベースが2つ(JavaScript,Io) (今回JavaScriptを載せていないスマソ
PHPやC++,HSPなどが続く。
どうやらRubyは無い模様Ruby厨ROMってないで出てきなさい！！
マイナー／特殊言語はJとsedだった。この２つどっちも変態的だ……
解説： http://vipprog.tumblr.com/post/48883078/quiz-add-parenthese-answer
