第 3 回 決定性オートマトン

Java の列挙型では、各要素毎にコンストラクタを起動させり、メソッドを持 てたりします。 さらに共通のメソッドを持たせ、抽象メソッドを定義させるとポリモーフィズ ムを利用することができるため、 switch case 文を取り除くことができます。

前述の例と等価で switch case 文を取り除いたプログラムを示します。 但し、これは Java 特有の機能で、他の言語にはあまり無いと思われます。

import java.io.*;
enum State {
    STATE1 { 
	public State nextState(int c) throws IllegalStateException {
	    if(c=='A'){  return STATE2; }
	    if(c=='C'){  return STATE3; }
	    throw new IllegalStateException(); 
	}
    },
    STATE2 {
	public State nextState(int c) throws IllegalStateException {
	    if(c=='A'){  return STATE2; }
	    if(c=='B'){  return STATE3; }
	    throw new IllegalStateException(); 
	}
    },
    STATE3 {
	public State nextState(int c) throws IllegalStateException {
	    if(c=='B'){ return STATE1; }
	    throw new IllegalStateException();
	}
    };
    abstract public State nextState(int c) throws IllegalStateException;
}
class Rei {
    private static int get(Reader r) throws IOException {
	int c;
        do{
            c=r.read();
	}while(c=='\n' || c=='\r');
	return c;
    }
    public static void main(String[] arg)throws IOException{
	final Reader r = new InputStreamReader(System.in);
	int c;
	State s=State.STATE1;
	try{
	    while((c=get(r))!=-1){
		s = s.nextState(c);
	    }
	    if(s!=State.STATE3){
		throw new IllegalStateException();
	    }
	    System.out.println("Accept");
	}catch(IllegalStateException e){
	    System.out.println("Reject");
	}
    }
}

Python の列挙型では、各要素毎にコンストラクタを起動させり、メソッドを持 てたりします。 さらに共通のメソッドを持たせ、抽象メソッドを定義させるとポリモーフィズ ムを利用することができるため、 switch case 文を取り除くことができます。

前述の例と等価で switch case 文を取り除いたプログラムを示します。 但し、これは Java 特有の機能で、他の言語にはあまり無いと思われます。

from enum import Enum,auto

class IllegalStateException(Exception):
    pass

class State(Enum):
  STATE1 = auto()
  STATE2 = auto()
  STATE3 = auto()

  def nextState(self, c):
      if self == State.STATE1:
          if c == 'A':
              return State.STATE2
          elif c == 'C':
              return State.STATE3
          else:
              raise IllegalStateException()
      elif self == State.STATE2:
          if c == 'A':
              return State.STATE2
          elif c == 'B':
              return State.STATE3
          else:
              raise IllegalStateException()
      elif self == State.STATE3:
          if c == 'B':
              return State.STATE1
          else:
              raise IllegalStateException()
      else:
          raise IllegalStateException()

s=State.STATE1
try:
    for c in list(input()):
        s = s.nextState(c)
    if s !=State.STATE3:
        raise IllegalStateException()
    print("Accept")
except IllegalStateException:
    print("Reject")

入力の仕様として、実行のさせ方が java Rei pattern string と コマンドの引数にパターンと文字列を与えることとします。 そして、 string の中から pattern がいくつあるかを計算するプログラムを 書きます。 これは java の main の宣言文を public static void main(String[] arg) とした場合、 arg[0] が pattern で、 arg[1] が string になります。

pattern を string にマッチさせていきますが、どこからマッチさせるかがポ イントになります。 プログラムの設計として、 string を一文字ずつ読み込み、そこで pattern がどれくらい検出できたかを調べます。 string を一文字ずつ読み込むのに、 java.io.StringReader を使用します (Reader 系を使用しておくと、あとでファイルなど別の入力に置き換えること が楽になります)。 一方、オブジェクト指向分析的にこの正規表現を処理するもの自体が一つのオ ブジェクトとして考えられます。 そこで、そのオブジェクトのクラス(Matcher と名づける) を作ります。 Matcher クラスはパターンにより初期化されます。 そして、一文字ずつの入力に対し受理状態に入った入ってないかを判定するメ ソッド match(int c) を持たせます。

import java.io.*;
class Matcher {
    public Matcher(String pattern){...}
    public boolean match(int c){...}
}
class Rei {
    public static void main(String[] arg) throws IOException {
	final Matcher m = new Matcher(arg[0]);
	final Reader r = new StringReader(arg[1]);
	int count=0;
	int c;
	while((c=r.read())!=-1){
	    if(m.match(c)){
               count++;
            }
	}
	System.out.println(count);
    }
}

入力の仕様として、実行のさせ方を python rei.py pattern string と コマンドの引数にパターンと文字列を与えることとします。 そして、 string の中から pattern がいくつあるかを計算するプログラムを 書きます。 これには sys ライブラリを import して、 args = sys.argv で引数リ ストを取り込むと args[1] が pattern で、 args[2] が string になります。

pattern を string にマッチさせていきますが、どこからマッチさせるかがポ イントになります。 プログラムの設計として、 string を一文字ごとのリストとします。 一方、この正規表現を処理するもの自体が一つのオブジェクトとして考えられます。 そこで、そのオブジェクトのクラス(Matcher と名づける) を作ります。 Matcher クラスはパターンにより初期化されます。 そして、一文字ずつの入力に対し受理状態に入った入ってないかを判定するメ ソッド match(c) を持たせます。

import sys

class Matcher:
    def __init__(self, pattern):
        ...
    def match(c):
        ...
args = sys.argv
m = Matcher(args[1])
r = arg[2]
count=0
for c in list(r):
    if m.match(c):
        count += 1
print(count)

アルゴリズムは、次の文字が来たとき、パターンのどこと照合するかを覚えて おくというものです。 そのため、整数で表した位置を無制限で保存できる LinkedList を使います。 一文字読む毎に、その LinkedList に保存されている位置を順に取り出します(*1)。 そして、その位置のパターンの文字と得られた文字を比較し、異なっていたら その保存していた位置を破棄します(*2)。 同一だった場合、最後まで読めていたら「マッチした」と言うことにします(*3)。 まだパターンが残っている場合は位置を一つ進めて保存します(*4)。

その他に、読み込んだ文字がパターンの 0 番目の文字に一致したら 1 番目と いう位置を新たに LinkedList に加えます(*5)。 なお、パターンが 1 文字だった場合は「マッチした」ことにします(*6)。

import java.util.*;
class Matcher {
    final private String pattern;
    final private LinkedList<Integer> pointer;
    public Matcher(String pattern){
	this.pattern = pattern;
	pointer = new LinkedList<Integer>();
    }
    public boolean match(int c){
	boolean result = false;
	final ListIterator<Integer> i = pointer.listIterator();
	while(i.hasNext()){    //*1
	    int j = i.next();
	    if(c==pattern.codePointAt(j)){
		j++;
		if(j==pattern.length()){
		    result=true;   //*3
                    i.remove();
		}else{
		    i.set(j);  //*4
		}
	    }else{
		i.remove();  //*2
	    }
	}
	if(c==pattern.codePointAt(0)){
	    if(pattern.length()==1){
		result=true;    //*6
	    }else{
		pointer.add(1); //*5
	    }
	}
	return result;
    }
}

アルゴリズムは、次の文字が来たとき、パターンのどこと照合するかを覚えて おくというものです。 そのため、整数で表した位置を無制限で保存できる LinkedList を使います。 一文字読む毎に、その LinkedList に保存されている位置を順に取り出します(*1)。 そして、その位置のパターンの文字の次の文字と得られた文字を比較します。 同一だった場合、最後まで読めていたら「マッチした」と言うことにします(*3)。 まだパターンが残っている場合は保存します(*4)。

その他に、読み込んだ文字がパターンの 0 番目の文字に一致したら 1 番目と いう位置を新たに LinkedList に加えます(*5)。 なお、パターンが 1 文字だった場合は「マッチした」ことにします(*6)。

import sys
class Matcher:
    def __init__(self,pattern):
        self.pattern = pattern
        self.pointer = []
    def match(self,c):
        result = False
        newpointer = []
        for j in self.pointer: #*1
            if self.pattern[j] == c:
                k = j + 1
                if k == len(self.pattern) :
                    result = True #*3
                else:
                    newpointer.append(k) #*4
        if self.pattern[0] == c:
            if len(self.pattern) == 1 :
                result = True #*6
            else:
                newpointer.append(1) #*5
        self.pointer = newpointer
        return result

args = sys.argv
m = Matcher(args[1])
r = args[2]
count=0
for c in list(r):
    if m.match(c):
        count += 1
print(count)
  

しかし、このプログラムでは得られた数を使うのが難しいです。 イテレータのように、呼び出すたびに順々に数を返すようなメソッ ドが実装されているようなオブジェクトがあると便利です。 そこで、 java.io.Reader オブジェクトを与えることにより、数を順に得るメ ソッドを実装した Parser クラスを作ります。

なお、毎回文字列を取り出すような関数を作るときには注意が必要です。 この数を取り出す場合もそうですが、EOF という文字列の最後を読んだとき、 取り出すべき最後の数が確定します。 そのため、 EOF が終わっても、すぐには終了できず、最後の数を返す必要が あります。 そして、その次の呼び出しで、初めて終了処理を行います。 そのため、読み込んだ値を保存しておき、返すべきものが無くなってから終了 処理を行います。

import java.io.*;
class Parser {
    enum State {
	STATE1, STATE2
    }
    private Reader reader;
    private int lastChar;
    private State s;
    public Parser(Reader r)throws IOException{
	reader = r;
	lastChar=reader.read();
	s=State.STATE1;
    }
    public String nextToken() throws IOException{
	final StringBuilder sb = new StringBuilder();
	while(true){
	    switch(s){
	    case STATE1:
		if(lastChar==-1){
		    return null;
		}
		if((lastChar>='1')&&(lastChar<='9')){
		    sb.append((char)lastChar);
		    s=State.STATE2; 
		    break;
		}
		s=State.STATE1;
		break;
	    case STATE2:
		if((lastChar>='0')&&(lastChar<='9')){
		    sb.append((char)lastChar);
		    s=State.STATE2; 
		    break;
		}
		s=State.STATE1;
		return sb.toString();
	    }
	    lastChar = reader.read();
	}
    }
}
class Rei {
    public static void main(String[] arg)throws IOException{
	final Reader r = new InputStreamReader(System.in);
	final Parser p = new Parser(r);
	String str;
	while((str=p.nextToken())!=null){
	    System.out.println(str);
	}
    }
}

しかし、このプログラムでは得られた数を使うのが難しいです。 そのため、イテレータとして数を順に得るメ ソッドを実装した Parser クラスを作ります。

なお、毎回文字列を取り出すような関数を作るときには注意が必要です。 この数を取り出す場合もそうですが、文字列の最後になった時に 取り出すべき最後の数が確定します。 そのため、 文字列が終わっても、すぐには終了できず、最後の数を返す必要が あります。 そして、その次の呼び出しで、初めて終了処理を行います。 そのため、読み込んだ値を保存しておき、 文字列の最後に関しても文字列の最後を示す文字を記憶しておき、 返すべきものが無くなってから終了処理を行います。

import enum
class State(enum.Enum):
    STATE1 = enum.auto()
    STATE2 = enum.auto()
class Parser:
    def __init__(self, string):
        self.it = iter(list(string))
        self.state = State.STATE1
        try:
            self.lastchar = next(self.it)
        except StopIteration:
            self.lastchar = '\n'
    def __iter__(self):
        return self
    def __next__(self):
        sb = ""
        while True:
            if self.state == State.STATE1:
                if self.lastchar == '\n':
                    raise StopIteration()
                if self.lastchar >='1' and self.lastchar <='9':
                    sb += self.lastchar
                    self.state = State.STATE2
                else:
                    self.state = State.STATE1
            elif self.state == State.STATE2:
                if self.lastchar >='0' and self.lastchar <='9':
                    sb += self.lastchar
                    self.state = State.STATE2
                else:
                    self.state = State.STATE1
                    return sb
            try:
                self.lastchar = next(self.it)
            except StopIteration:
                self.lastchar = '\n'
p = Parser(input())
for str in p:
    print(str)

なお、このような仕組みは java.util.regex ライブラリに既に用意されてい ます。 これまで説明してきたプログラミングテクニックは重要ですが、実際に文字列 処理を行う場合は下記のように java.util.regex ライブラリを使った方が良 いでしょう。

import java.util.*;
import java.util.regex.*;
import java.io.*;
class Rei2 {
    public static void main(String arg[]) throws IOException {
	final BufferedReader br = new BufferedReader(
                                    new InputStreamReader(System.in));
	String buf;
	final Pattern p = Pattern.compile("[1-9][0-9]*");
	Matcher m;
	while((buf=br.readLine())!=null){
	    m= p.matcher(buf);
	    while(m.find()){
		System.out.println(m.group());
	    }	
	}
    }
}

なお、このような仕組みは re ライブラリに既に用意されてい ます。 これまで説明してきたプログラミングテクニックは重要ですが、実際に文字列 処理を行う場合は下記のように re ライブラリを使った方が良 いでしょう。

import re
p = re.compile("[1-9][0-9]*");
m = p.finditer(input())
for i in m:
    print(i.group())

enum のメソッドでは static を指定しませんが、内部的には static のよう で、メンバ変数を使用したい場合は static の指定をします。

import java.io.*;
enum State {
    STATE1 {
	public State nextState(int c){
	    if((c>='1')&&(c<='9')){
		sb = new StringBuilder();
		sb.append((char)c);
		token = false;
		return STATE2; 
	    }
	    token = false;
	    return STATE1;
	}
    },	
    STATE2 {
	public State nextState(int c){
	    if((c>='0')&&(c<='9')){
		sb.append((char)c);
		token = false;
		return STATE2; 
	    }
	    token = true;
	    return STATE1;
	}
    };
    private static StringBuilder sb; // メンバ変数は static にする。
    public String getToken(){
	return sb.toString();
    }
    private static boolean token=false;
    abstract public State nextState(int c);
    public boolean hasToken(){
	return token;
    }
}
class Rei {
    public static void main(String[] arg)throws IOException{
	final Reader r = new InputStreamReader(System.in);
	int c;
	State s=State.STATE1;
	StringBuilder sb=null;
	while((c=r.read())!=-1){
	    s=s.nextState(c);
	    if(s.hasToken()){
		System.out.println(s.getToken());
	    }
    	}
	if(s==State.STATE2){
	    System.out.println(s.getToken());
	}
	
    }
}

文字バッファと状態はクラス変数を使用します。

import enum

class State(enum.Enum):
    STATE1 = enum.auto()
    STATE2 = enum.auto()
    @classmethod
    def start(cls):
        return State.STATE1
    @property
    def token(self):
        return State.sb
    def nextState(self, c):
        if self == State.STATE1:
            if c>='1' and c <='9':
                State.sb = c
                State.hasToken = False
                return State.STATE2
            else:
                State.hasToken = False
                return State.STATE1
        elif self == State.STATE2:
            if c>='0' and c <='9':
                State.sb += c
                State.hasToken = False
                return State.STATE2 
            else:
                State.hasToken = True
                return State.STATE1

s=State.start()
for c in list(input()):
    s=s.nextState(c)
    if s.hasToken:
        print(s.token)
if s==State.STATE2:
    print(s.token)