2013-12-06

4.1 コンちゃん(Lunatic)について

最近、新しいコンちゃん(Twitter bot)を作った。

おちんちんっていうツイートする。その各々でいいとする必要単位を開発してる
— コンちゃん(Lunatic) (@lunatic_club) 2013, 12月 5

前のコンちゃんはEasyBotterを利用していたためPHPで作成していたが、色々と自由度が減る上にcronサービス*1が不安定だったため、あまり良い出来とは言えなかった(ウザさは一級品だったが)。

というわけで、今回はRubyとTwitter gemを使ってTwitter botを作成した。
その軌跡について、かなり詳しく書いてみる。

準備

実は、今回のbot作成はRubyとgemの扱いに慣れることが主目的だったりする(他にやりたいことがある)。
開発環境は様々なことを考慮してLinuxの方が良いので、Virtual Boxを利用してUbuntu12.04をWindows7に入れた。実は既にUbuntuはデュアルブートさせているのだが、いちいち再起動するのがめんどいのと作業中に遊びが欲しいのでWindowsと同時に使えるVirtual Boxを選択した。

Ubuntuの何がいいかって、欲しいパッケージは魔法の呪文「sudo apt-get install hogehoge」でダウンロードからインストールまで全部やってくれるってところ。Androidと同じような感じ。開発環境とかWindowsより圧倒的に楽に準備できる。あと、Terminalカチャカチャやってるとなんだかカッコいいです。

Ruby

プログラミング言語 Rubyは、日本人によって作られたオブジェクト指向言語である。
と言っても、Rubyは恐ろしく自由度が高い言語で、そもそもmain関数というものが存在しない。基本的にはコードの一番上から順番に実行される。でも、関数やクラスを用いてパッケージングも出来る。

puts 'Hello World!!'  # RubyのHello World

数字や演算子に至るまですべてがオブジェクト（Java風にいうとインスタンス）であり、それらには初めから基本メソッドが存在している。基本メソッドは結構な数があり、痒いところに手が届くように作られていて非常に快適にコーディング出来る。

108.to_s  # 108を文字列に変換する
string.to_i  # 文字列stringを整数に変換する

また、変数宣言が必要ない。変数は、必要に応じて型が自動的に割り当てられる。型ももちろんオブジェクト。

hoge = 7  # 整数型になる
st = '文字列'  # 文字列型になる
hoge = 'ふが'  # 文字列型に変換される
puts hoge  # 'ふが'が表示される(7は表示されない)

配列は動的で、異なる型(クラス)のオブジェクトを1つに配列に入れることも可能。

list = [1, '2', hoge]  # できる。

正規表現を気軽に扱えるのも強みだ。

st = 'this is a pen.'
st = st.gsub(/[^ ]*is/, 'hoge')  # //で囲まれた部分は正規表現と見なされる
puts st  # hoge hoge a pen.

また、対話環境も自動でついてくる。irbで起動できる。
ちなみに、インタプリタなので、

% ruby hogehoge.rb

これでプログラムを実行する。今回はRuby1.9.3で作成した。

gem

Rubyに必要なライブラリを自動的に落としてくれる便利なもの。

% gem install hogehoge

これでhogehogeというライブラリを落としてきてくれる。重いものを落としているとフリーズしたように見えるのが欠点。
今回はgem1.8.23を使用した。

必要なライブラリを落としまくる

先ほどのgemでどんどん入れていく。以下、gem install hogehogeを使うこと。

twitter

Twitter APIを叩く便利なもの。たぶん公式ドキュメント→http://rdoc.info/gems/twitter
自由度がとても高い。すごい。

igo-ruby

形態素解析用のライブラリ。バージョンが1未満だからまだ未完成っぽい。

mecab

igo-rubyを入れた時に一緒に来たような気がする。形態素解析のための日本語辞書。重い(100MBくらい)。

アカウントを準備する

アカウントを作って、Twitter Developersでログイン。新しくアプリケーションを作成する。OAuthのAccess LevelはRead and Writeとしておき、アプリの管理画面からAccess Tokenを生成する。
Access Tokenの生成が終わったら、Consumer Key、Consumer Secret、Access Token、Access Token Secretの値をメモっておく。

コードを書く

とりあえず呟かせてみよう。

# -*- coding: utf-8 -*-
require 'twitter'
 
# アクセス設定
client = Twitter::REST::Client.new do |config|
    config.consumer_key        = "さっき取得したやつ"
    config.consumer_secret     = "さっき取得したやつ"
    config.access_token        = "さっき取得したやつ"
    config.access_token_secret = "さっき取得したやつ"
end

client.update("テスト")

これで「テスト」と投稿されるはずである。
その他の例については、公式(たぶん)を見て欲しい。

マルコフ連鎖

おちんちんっていうツイートする。その各々でいいとする必要単位を開発してる
— コンちゃん(Lunatic) (@lunatic_club) 2013, 12月 5

コンちゃんは、このような文章を延々と吐いている。これは、コンちゃんのTLから拾った文章を形態素解析して、マルコフ連鎖でランダムに繋げて文章を生成しているのである。

マルコフ連鎖の数学的定義は置いといて、コンちゃんでは以下の様な仕組みで文章を生成している。

文章を形態素にバラす。この時、先頭には'__BEGIN__'タグを、最後には'__END__'タグをつける。
それぞれ2つずつをペアにして配列に入れる。たとえば、"私はLです"だと["__BEGIN__","私],["私","は"],["は","L"],["L","です"],["です","__END__"]のようになる。
溜まった形態素ペア群からまず__BEGIN__を探してきて、ランダムに選択。次に、__BEGIN__とペアになっている単語を生成文章の後ろに追加し、次はペアになっていた単語から始まる形態素ペア群をランダムに選択、それを__END__が現れるまで繰り替えす。

形態素ペアはグループにする数を増やせば増やすほどまともな文章が現れる確率は上がる(もっとも、下手に数を増やしても元の文章とそのままのものが出てくる確率が上がってあまりおもしろくない)。今回だとグループは2つの要素を持つので、2次マルコフ連鎖と呼ばれるらしい？？
かの有名なしゅうまい君も、基本的にはこのような仕組みで動いている。

というわけで、マルコフ連鎖部分だけコードを載せる～～

# -*- coding: utf-8 -*-
 
def make_markov(texts) # textsから2次マルコフ連鎖で文章を生成。中身は1次配列。
  message = '' # 返す文章
  next_front = '__BEGIN__' # 次のデータの先頭文字
  while 1 > 0
    list = [] #候補に上がったデータ
    (texts.length).times do |m|
      if m%2 == 0
        # データの先頭文字とnext_frontが一致すれば、その後の文字をリストにpush
        if texts[m] == next_front
          list = list + [texts[m+1]]
        end
      end
    end
    if list.length == 0 # リストが空なら終了。
      message = '__FAILED__'
      break
    elsif message.length > 140 # 140文字以上なら終了。
      message = '__FAILED__'
      break
    else
      m = list[rand(list.length)]
      if m == '__END__'
        break
      else
        message = message + m
        next_front = m
      end
    end
  end
  return message
end

cronの設定

botのコードが無事書けたら、最後はcronを設定して定期的に実行させてやろう。
Ubuntuの場合、以下のように叩けば良い。

% crontab -e

初めて起動するときは使用エディタを聞いてくる。私の場合はemacsなのでemacsを選んだ。
なんかいっぱいコメントが書いてあるが、最後の行に以下のように書こう*2。

0,30 * * * * cd /hoge/fuga; /hoge/.rbenv/shims/ruby /hoge/fuga/bot.rb

これで、毎時0分と30分に"% ruby bot.rb"を起動してくれる。cdでrbファイルがある場所に移動しとく必要があるのと、すべてフルパスで書く必要があることに注意。
もちろん、Ubuntuの起動中にしか動かないぞ☆
あと、

% crontab -r

これは、設定したcronを確認なしで全て消去するコマンドなので注意。eとrは隣にあるからタイプミスし易いのだが…。色々と対策はあるので気になる人は各自対策しよう。

その他

一度まともに動いたのになんかエラー出る…ってときは、だいたいAPIエラーです。要するにAPI制限がかかっています。エラーメッセージ読んで。ちょっと時間を置いてテストしよう。
特殊文字系は形態素解析時にエラーが発生する可能性があるので、begin・rescue・endで例外処理しておきましょう(botが正常に動かなくなる)。

*1:定期的に指定したwebページにアクセスするサービス

*2:最後は改行を入れないとエラーが発生するので注意

2013-09-14

3.1 ユークリッドの互除法

暗号理論入門アルゴリズム

四条にあるジュンク堂で、暗号理論入門を購入。少し読んでみた。

暗号理論入門原書第3版

作者: 林芳樹
出版社/メーカー: 丸善出版
発売日: 2012/04/20
メディア: 単行本
この商品を含むブログを見る

最初の方は、微積の教科書を思い出すような感じだった。実数や整数の定義や性質から始まる。暗号理論なので、整数がメイン。整数の性質について、非常に詳しく述べられている。む、難しい…。

御約束ともいえるが、ユークリッドの互除法が出てきた。
最大公約数(gcd)を求めるアルゴリズムで、明示的に書かれた最古のアルゴリズムである(らしい)。

自然数 a, b の最大公約数は、b, a mod b の最大公約数に等しい。

これを利用したgcd(a,b)なる関数は、これまで何度も書いてきた。
…のだが、実はこのアルゴリズムが何故成立するのか、という証明は、恥ずかしながら理解していなかった。この機会に日本酒を煽りながら様々な文献を漁り、ようやく自分的に納得のいく証明が得られたので、ここに書いておく。

[証明]*1
全ての文字は整数とする。
a = bq + r とする。また、ある m, n が存在して、a = mx, b = nx とする。すなわち、x は a, b の公約数である。
このとき、
r = a - bq
r = mx - nxq
r = (m - nq)x
より、x は r の約数である。すなわち、「a, b の全ての公約数は、b, r の公約数でもある」ことが示せた。
また、r < b より、

int gcd(int a, int b){
	return (b == 0 ? a : gcd(b, a%b));
}

なる関数gcdの第2引数は強い意味で単調減少であり、いずれ0になる*2。
ところで、ある整数 c について、gcd(c, 0) = c である。なぜなら、c は c の最大の約数であり、0 = 0*c が成立するからである。よって、上記アルゴリズムで a, b の最大公約数が求まる。

次回は拡張ユークリッドアルゴリズムについて学ぶ。

*1:やっぱ、コレはまだ不完全なので後に考察したい

*2:aがbより小さい場合でも、次に第1引数がb、第2引数がaなるgcdが呼ばれるので問題ない。

2013-09-11

0.1 二分探索(binary search)

アルゴリズム

ムラサちゃんとskypeで雑談してたら、こんな問題が飛んできた。

ｎ個の整数の集合Sとある整数ｘが与えられたとき、Sの中の２個の要素でそれらの和がちょうどｘになるものの組を見つける、実行時間Θ（ｎｌoｇ2(ｎ)）のプログラムを作れ。

整数は面倒なので、10億程度までの自然数で考える。0は含めても含めなくても良い。

普通に考えると、以下のような探索が思いつく。

for(int i=0; i<n-1; ++i){
	for(int j=i+1; j<n; ++j){
		if(s[i] + s[j] == x){
			...
		}
	}
}

これの(時間)計算量はO(n^2)*1である。計算量のお話はまた今度する。
まぁ、これでも十分なんだけど、nが1,000になると計算量が1,000,000となり、実行時間的には少し怪しげになる。
そこで、O(nlogn)のアルゴリズムを考えてみる。これだと、nが1,000になっても計算量は32,000程度である。すごい。

O(logn)を見ると真っ先に思い浮かぶのが、二分探索(binary search)であった。ので、二重めのループで二分探索を用いたコードを書いた。

二分探索は、あらかじめソートされたデータ群を前提とする探索方法である。
たとえば、以下のようなデータ群から''13''をサーチしたいとする。

{1,2,4,6,7,9,10,13,15,16}

このデータ群の真ん中に位置するデータをチェックする。「真ん中」は真ん中付近であれば大雑把で良い。今回は、データ群の個数kが偶数のときは、左から(k/2)+1番目を見ることにしよう。

上の例で、真ん中のデータは''9''である。サーチデータ''13''ではなかった。ここで、サーチデータ''13''は、少なくとも''9''より右側に存在することが分かる*2。
よって、今度は以下のデータ群で再び同様のチェックを行う。

{10,13,15,16}

真ん中のデータは''15''である。サーチデータ''13''は、少なくとも''15''より左側に存在することが分かる。
今度は、以下のデータ群で見てみる。

{10,13}

真ん中のデータは''13''である。サーチデータ''13''と一致し、めでたく探索が終了する。

この探索の凄い所は、1回の探索で探索せねばならないデータ数が半分に減ることである。よって、n個のデータ群の探索で最悪O(logn)の計算量である*3。

二重めのループで二分探索を用いることで、探索アルゴリズムの計算量はO(nlogn)となる。

#include <iostream>
using namespace std;

const int max_n = 10000;
int s[max_n]; //集合S
int culc_num; //計算回数(比較回数)

//二分探索
//見つかった:0 見つからなかった:-1
int binary_search(int *data, int data_num, int target){
	int m = data_num / 2;
	++culc_num;

	/*
	if(m >= 0){
		cout << "\t(";
		for(int i=0; i<data_num; i++){
			cout << data[i];
			if(i < data_num-1)	cout << ",";
			else	cout << ")" << endl;
		}
		cout << "\tcheck:" << data[m] << endl;
	}
	*/
	
	if(data_num < 1)	return -1;
	else if(data[m] == target)	return 0;
	else{
		if(data_num == 1)	return -1;
		else if(data[m] < target)	return binary_search(&data[m+1], data_num-m-1, target);
		else	return binary_search(&data[0], m, target);
	}
}

int main(){
	//見つけたい解を入力
	int x;
	cin >> x;
	
	//データ数の入力
	int n;
	cin >> n;
	
	//n個のデータを入力。昇順入力じゃないとぉこだょ
	for(int i=0; i<n; ++i)	cin >> s[i];
	
	//s[i] + s[j] = xなる解を探索
	int ans_num = 0; //解の個数
	for(int i=0; i<n-1; ++i){
		int target = x - s[i]; //どの数値を見つければ良いか
		// cout << "search:" << target << endl;
		if(binary_search(&s[i+1], n-i-1, target) == 0){
			cout << "(" << s[i] << "," << target << ")" << endl;
			++ans_num;
		}
	}

	//解の出力
	if(ans_num == 0)	cout << "NA" << endl;
	cout << "ans_num:" << ans_num << endl;
	cout << "culc_num:" << culc_num << endl;
	
	return 0;
}

コメント化している命令を解除すれば、どのような動きで探索が為されているか見れる。
たとえば、x=13,n=10,S={1,3,4,4,5,6,7,8,9,10}なる入力を与えると、その結果は以下のようになる。

入力:
13
10
1
3
4
4
5
6
7
8
9
10
出力:
(3,10)
(4,9)
(4,9)
(5,8)
(6,7)
ans_num:5
culc_num:20

同じことを、最初のO(n^2)アルゴリズムで行うと、culc_numは45となる。

*1:O(n^2)とか、Θ(n^2)とか書かれる。読み方は「オーダー」。

*2:sorted dataが前提のため。

*3:情報学に於いてlogの底は2が前提であることが多い。今回もlogの底は2としている。

2013-08-26

2.3 AOJ-0006 to 0010

AOJ アルゴリズム

今日もAOJの問題を解いていた。

0006

文字列の反転問題。

0007

毎週5%の利子がついて、しかも1000円未満は切り上げられるという闇金業者の借金が、n週間後にはいくらになるか、という教育上よろしいのか疑われる問題。
1000円未満の切り上げ処理がポイント。むしろそこしかポイントが無い。

//一の位から数えてketa桁未満で繰り上げる
void keta_up(int &num, int keta){
	int p = pow(10, keta);
	int n = num / p;
	if(num-n*p > 0){
		num /= p;
		num += 1;
		num *= p;
	}
}

0008

0~9なる整数a,b,c,dで、a+b+c+d=nなる組み合わせは何通りか、という問題。
探索系の問題だけど、この場合はコレで解ける。

#include <iostream>

using namespace std;

int main(){
	int n;
	while(cin >> n){
		int ans_num = 0;
		for(int a=0; a<10; ++a){
			for(int b=0; b<10; ++b){
				for(int c=0; c<10; ++c){
					for(int d=0; d<10; ++d){
						if(a+b+c+d == n)	++ans_num;
					}
				}
			}
		}
		cout << ans_num << endl;
	}
	
	return 0;
}

こんな問題もあったねぇ。

0009

n以下の素数はいくつあるか、という問題。範囲が決められているのでエラトステネスの篩を使う。これ以外の選択肢は無い。篩のために使う変数は、グローバルにしておくこと(スタック領域じゃオーバーフローを起こす)。

#include <iostream>
#include <vector>

using namespace std;

const int MAX_NUM = 1000000;

bool prime_flag[MAX_NUM];
vector<int> prime;

void check_prime(){
	prime_flag[0] = false;
	for(int i=1; i<MAX_NUM; ++i){
		if(prime_flag[i] == true){
			int num = i+1;
			for(int j=2*num; j<MAX_NUM+1; j+=num){
				prime_flag[j-1] = false;
			}
			prime.push_back(i+1);
		}
	}
}

int main(){
	for(int i=0; i<MAX_NUM; ++i)	prime_flag[i] = true;
	check_prime();
	int n;
	while(cin >> n){
		int i;
		for(i=0; i<(int)prime.size(); ++i){
			if(prime[i] > n)	break;
		}
		cout << i << endl;
	}
	
	return 0;
}

0010

三点が与えられるので、それで作られる三角形の外接円の中心座標と半径を求めよ、とのこと。
中心座標の導出がめっちゃめんどい。2弦の垂直二等分線の交点がそれなので、それを導出してみる。
まず、(x1,y1)と(x2,y2)の垂直二等分線は以下のような直線である。

$2(x_2-x_1)x + 2(y_2-y_1)y = x_2^2 - x_1^2 + y_2^2 - y_1^2$

この時点で割と吐き気がする。
よって、

$2(x_2-x_1)x + 2(y_2-y_1)y = x_2^2 - x_1^2 + y_2^2 - y_1^2$
$2(x_3-x_2)x + 2(y_3-y_2)y = x_3^2 - x_2^2 + y_3^2 - y_2^2$

この連立方程式を解けば良い。ゲェ～ッ。
行列使って解いて、解は以下のようになる。

$x=\frac{1}{2}\cdot\frac{(y_3-y_2)(x_2^2-x_1^2+y_2^2-y_1^2) - (y_2-y_1)(x_3^2-x_2^2+y_3^2-y_2^2)}{(x_2-x_1)(y_3-y_2)-(y_2-y_1)(x_3-x_2)}$
$y=\frac{1}{2}\cdot\frac{-(x_3-x_2)(x_2^2-x_1^2+y_2^2-y_1^2) + (x_2-x_1)(x_3^2-x_2^2+y_3^2-y_2^2)}{(x_2-x_1)(y_3-y_2)-(y_2-y_1)(x_3-x_2)}$

これはひどい。
一応、ちゃんと正解は出せる。動作も非常に高速である。見た目はともかく。
半径の導出は簡単なので省略。

2013-08-26

2.2 AOJ-0000 to 0005

AOJ アルゴリズム

POJが重すぎて繋がらないので、AOJ(http://judge.u-aizu.ac.jp/onlinejudge/index.jsp)に浮気した。問題文も日本語だし、難易度も低いし。あの会津大学が主催してるらしい。

で、練習問題を数問解いた後、レーティングに反映される問題を6問ほど解いた。

0000

九九の表を出力する問題。懐かしい。

0001

入力された10整数のうち、大きいものから3つ出力する問題。
バブルソートをちゃちゃっと書けるようになっておけば楽勝。バブルソートは4行で書けるので、それで解ける問題なら実装が面倒なクイックソートとかより経済的。ただ、ライブラリは存在する気がする。
大きい順でソートするバブルソート。

void bubble_sort(int *data, const int data_num){
	for(int i=0; i<data_num; ++i){
		for(int j=0; j<data_num-i-1; ++j){
			if(data[j] < data[j+1])	swap(data[j], data[j+1]);
		}
	}
}

0002

入力した2整数の和の桁数を表示する問題。
以下の関数で8ケタまで求められる。

int check_keta(int n){
	int i;
	for(i=1; i<9; ++i){
		if(n/(int)pow(10, i) == 0)	break;
	}
	return i;
}

ホントはbreakをreturnに変えて、intをforの中で宣言してもっとスマートにしたかったが、「returnせずに終了する可能性がある」ってg++に怒られた(警告)ので泣く泣く書き換えた。

0003

入力した3整数で直角三角形が作れるか、という問題。
最も大きい数を斜辺とした直角三角形を考えれば良い。バブルソートで3整数を整理すればスムーズに処理できる。

0004

$ax+by=c, dx+ey=f$
連立方程式を解いてください。ただし、解は一意に与えられますよ、とのこと。
行列使って計算するのが早い。即座に、以下のように解が導き出せる。
$x=\frac{ce-bf}{ae-bd}$
$y=\frac{-cd+af}{ae-bd}$
解は一意に与えられるとのことなので、ae-bd=0は無いと考えれば良い。
さて、解は小数第3位まで表示するのだが、その関係で「-0.000」なる出力が為されることがある。これはWrong Answerとなるので、abs(x) < 0.0005のときはx=0とするなどすると良い。

0005

GCDとLCMを求める問題。
GCDに関しては、ユークリッドの互除法が有名なので、それを使う。
LCMに関しては、2数をA,B、GCD=Gとすると、
$L=\frac{AB}{G}$
となることを用いて導出する。

GCDは再帰関数の良い練習問題として有名。
LCMのこの計算順序は、オーバーフローを防ぐため。

int gcd(int a, int b){
	if(b == 0)	return a;
	else	return gcd(b, a%b);
}

int lcm(int a, int b){
	return a/gcd(a,b)*b;
}

2013-08-25

2.1 POJ-1068

POJ

整数ナンバリング2は、蟻本関連にしようかなぁ、と思う。

蟻本に載ってた、POJ(http://poj.org/)っていうオンラインジャッジシステムのあるプログラミングコンテスト練習サイトに、ちょっと足を運んでいる。

Solvedは今の所、1000、1001、1068の3問。1000は「a,b2つの入力が与えられる。a+bの結果を出力せよ」っていう練習用問題で、1001は「R(0 < R < 99.9)とn(0 < n <= 25)が与えられる。R^nを「正確に」出力せよ」っていうちょっと骨のある問題。問題文が英語ってのもあって、R^nを見た時は「いきなりn次元ユークリッド空間の問題か…ヤバ」って思ってしまった。

で、これを解くのに色々と疲れたので、次は正答率の最も高い奴を解くことにした。それが1068だった。

ID.1068
Description
Let S = s1 s2...s2n be a well-formed string of parentheses. S can be encoded in two different ways:
q By an integer sequence P = p1 p2...pn where pi is the number of left parentheses before the ith right parenthesis in S (P-sequence).
q By an integer sequence W = w1 w2...wn where for each right parenthesis, say a in S, we associate an integer which is the number of right parentheses counting from the matched left parenthesis of a up to a. (W-sequence).
Following is an example of the above encodings:
　　S　　(((()()())))
　　P-sequence　　4 5 6666
　　W-sequence　　1 1 1456
Write a program to convert P-sequence of a well-formed string to the W-sequence of the same string.

Input
The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case is an integer n (1 <= n <= 20), and the second line is the P-sequence of a well-formed string. It contains n positive integers, separated with blanks, representing the P-sequence.

Output
The output file consists of exactly t lines corresponding to test cases. For each test case, the output line should contain n integers describing the W-sequence of the string corresponding to its given P-sequence.

Sample Input
2
6
4 5 6 6 6 6
9
4 6 6 6 6 8 9 9 9

Sample Output
1 1 1 4 5 6
1 1 2 4 5 1 1 3 9

Source
Tehran 2001

要は、カッコ(parentheses)で表現された文字列があって、その数列での表し方が2通りあるんだけど、一方の表現方法をもう一方の表現方法に変換してね、っていう問題。

アルゴリズムはいろいろあると思うけど、まずはカッコを用いた文字列に変換して、それを基にもう一方の表現方法に変換するようにした。
そんなに面白い問題ではないし、これ以上解説しても無意味っぽいので、練習問題がてらコードを載せてこの記事を締める。

#include <iostream>

using namespace std;

const int MAX_N = 20;
const int MAX_STRING = 64;

int main(){
	int t;
	cin >> t;
	for(int i=0; i<t; ++i){
		int n;
		cin >> n;
		int p[MAX_N];
		for(int j=0; j<n; ++j)	cin >> p[j];
		
		//()に変換
		char st[MAX_STRING];
		for(int j=0,k=0,left_num=0; j<2*n; ++j){
			if(left_num == p[k]){
				st[j] = ')';
				if(k < n-1)	++k;
			}
			else{
				st[j] = '(';
				++left_num;
			}
		}
		
		//W-sequenceに変換
		int w[MAX_N];
		for(int j=0,check_num=0; j<2*n; ++j){
			if(st[j] == ')'){
				for(int k=j-1,ok=0,left_num=0; k>=0; --k){
					if(st[k]=='(' && ok==0){
						++left_num;
						w[check_num] = left_num;
						break;
					}
					else if(st[k]=='('){
						--ok;
						++left_num;
					}
					else	++ok;
				}
				cout << w[check_num] << " ";
				++check_num;
			}
		}
		cout << endl;
	}
}

2013-08-16

1.3.2 動的確保のスタック・キューへの適用

汎用探索パッケージ制作 C++ アルゴリズム

//dynamic_stack
#include <iostream>

template <class T> class stack{
	class set_of_datum{
	private:
		T value;
		set_of_datum *next;
	public:
		set_of_datum(T value){
			this->value = value;
			next = NULL;
		}
		void set_next(set_of_datum *next){
			this->next = next;
		}
		set_of_datum *get_next(){return next;}
		T get_value(){return value;}
	};
private:
	set_of_datum *data; //スタックの本体
public:
	stack(); //コンストラクタ
	~stack(); //デストラクタ
	void clear(); //スタックの中身を空にする
	void push(T obj); //スタックにobjを追加する
	T pop(); //スタックからobjを取り出す
	void show(); //スタックの中身を見せる
	int get_data_num(); //スタックデータの数を返す
};

template <class T> stack<T>::stack(){
	data = NULL;
}

template <class T> stack<T>::~stack(){
	clear();
}

template <class T> void stack<T>::clear(){
	while(data != NULL){
		set_of_datum *target = data; //delete対象
		data = (*data).get_next();
		delete target;
	}
}

template <class T> void stack<T>::push(T obj){
	set_of_datum *new_datum = new set_of_datum(obj);
	(*new_datum).set_next(data);
	data = new_datum;
}

template <class T> T stack<T>::pop(){
	T dummy; //error発生時に返すダミーデータ
	if(data != NULL){
		T value = (*data).get_value();
		set_of_datum *target = data; //delete対象
		data = (*data).get_next();
		delete target;
		return value;
	}
	else{
		std::cout << "error: this stack is EMPTY! -- in stack<T>::pop()" << std::endl;
		return dummy;
	}
}

template <class T> void stack<T>::show(){
	set_of_datum *ptr = data; //表示するデータ
	for(int i=0; ptr!=NULL; i++){
		std::cout << i << ":" << (*ptr).get_value() << std::endl;
		ptr = (*ptr).get_next();
	}
}

template <class T> int stack<T>::get_data_num(){
	int value = 0;
	set_of_datum *ptr = data;
	while(ptr != NULL){
		value ++;
		ptr = (*ptr).get_next();
	}
	return value;
}

まぁ、こんなものだろう。
同様に、キューも。

//dynamic_queue
#include <iostream>

template <class T> class queue{
	class set_of_datum{
	private:
		T value;
		set_of_datum *before;
		set_of_datum *next;
	public:
		set_of_datum(T value){
			this->value = value;
			before = NULL;
			next = NULL;
		}
		void set_before(set_of_datum *before){
			this->before = before;
		}
		void set_next(set_of_datum *next){
			this->next = next;
		}
		set_of_datum *get_before(){return before;}
		set_of_datum *get_next(){return next;}
		T get_value(){return value;}
	};
private:
	set_of_datum *data; //キューの本体(先頭)
	set_of_datum *pop_target; //キューの本体(末尾)
public:
	queue(); //コンストラクタ
	~queue(); //デストラクタ
	void clear(); //キューの中身を空にする
	void enqueue(T obj); //キューにobjを追加する
	T dequeue(); //キューからobjを取り出す
	void show(); //キューの中身を見せる
	int get_data_num(); //キューのサイズを返す
};

template <class T> queue<T>::queue(){
	data = NULL;
	pop_target = NULL;
}

template <class T> queue<T>::~queue(){
	clear();
}

template <class T> void queue<T>::clear(){
	while(data != NULL){
		set_of_datum *target = data; //delete対象
		data = (*data).get_next();
		delete target;
	}
}

template <class T> void queue<T>::enqueue(T obj){
	set_of_datum *new_datum = new set_of_datum(obj);
	if(get_data_num() == 0)	pop_target = new_datum;
	else{
		(*new_datum).set_next(data);
		(*data).set_before(new_datum);
	}
	data = new_datum;
}

template <class T> T queue<T>::dequeue(){
	T dummy; //error発生時に返すダミーデータ
	if(data != NULL){
		T value = (*pop_target).get_value();
		set_of_datum *target = pop_target; //delete対象
		if(data == target)	data = NULL;
		else	(*(*target).get_before()).set_next(NULL);
		pop_target = (*target).get_before();
		delete target;
		return value;
	}
	else{
		std::cout << "This queue is EMPTY! -- error in queue<T>::pop()" << std::endl;
		return dummy;
	}
}

template <class T> void queue<T>::show(){
	set_of_datum *ptr = data;
	for(int i=0; ptr!=NULL; i++){
		std::cout << i << ":" << (*ptr).get_value() << std::endl;
		ptr = (*ptr).get_next();
	}
}

template <class T> int queue<T>::get_data_num(){
	int value = 0;
	set_of_datum *ptr = data;
	while(ptr != NULL){
		value++;
		ptr = (*ptr).get_next();
	}
	return value;
}

queue< T >::dequeue()のif文の中身が若干汚いけど、他に書き方はあるのだろうか。

技術的なやつ