阅读 35

确定性下推自动机,判断是括号是否合法

参考:www.nosuchfield.com/2017/01/07/…


修改了一些小错误

# -*- coding: UTF-8 -*-
"""
确定性下推自动机,Deterministic PushDown Automaton
"""


# 定义一个栈
class Stack(object):
    # 初始时栈底的元素
    def __init__(self, init):
        self.__storage = init

    def top(self):
        return self.__storage[-1]

    def push(self, p):
        # 压入的内容做遍历,靠近后面的内容应该先被压入
        for i in reversed(p):
            self.__storage.append(i)

    def pop(self):
        return self.__storage.pop()


# 名词[配置]表示一个状态和一个栈的组合,其实上相当于以前的[一个状态]
# 为什么要定义[配置]呢?目的在于把状态和栈这两种元素组合起来形成一个整体,方便使用
class PDAConfiguration(object):
    def __init__(self, state, stack):
        self.state = state
        self.stack = stack


# DDPA的转移规则
class PDARule(object):
    # 参数:当前状态,输入,下一个状态,(栈)弹出字符,压入字符
    def __init__(self, state, character, next_state, pop_character, push_characters):
        self.state = state
        self.character = character
        self.next_state = next_state
        self.pop_character = pop_character
        self.push_characters = push_characters

    # 下一个配置:1. 下一个状态就是 next_state 参数,2. 下一个配置的栈由方法 next_stack 根据当前的栈信息算出
    def follow(self, configuration):
        return PDAConfiguration(self.next_state, self.__next_stack(configuration.stack))

    # 判断指定配置执行指定输入时是否可用当前的转移规则
    def applies_to(self, configuration, character):
        #判断会不会发生自动转移
        return self.state == configuration.state \
               and self.pop_character == configuration.stack.top() and self.character == character

    # 下一个栈的计算,先弹出再压入即可
    def __next_stack(self, stack):
        stack.pop()  # 弹出
        stack.push(self.push_characters)  # 压入
        return stack


# 转移规则集合
class DPDARulebook(object):
    def __init__(self, rule_set):
        self.ruleSet = rule_set

    # 用于获取下一个配置
    def next_configuration(self, configuration, character):
        return self.__rule_for(configuration, character).follow(configuration)

    # 根据当前的配置和输入来查找对应的转移规则
    def __rule_for(self, configuration, character):
        for rule in self.ruleSet:
            if rule.applies_to(configuration, character):
                return rule
        raise Exception("找不到可供使用的规则 ...")


rulebook = DPDARulebook([
    PDARule(1, '(', 2, '$', ['b', '$']),
    PDARule(2, '(', 2, 'b', ['b', 'b']),
    PDARule(2, ')', 2, 'b', []),
    PDARule(2, None, 1, '$', ['$'])
])


class DPDA(object):
    # 参数:初始配置,接受状态,规则集合
    def __init__(self, current_configuration, accept_states, rule_book):
        self.current_configuration = current_configuration
        self.accept_states = accept_states
        self.rule_book = rule_book

    # 判断当前的状态是否是接受状态
    def accepting(self):
        return self.current_configuration.state in self.accept_states

    # 输入
    def read_character(self, character):
        self.current_configuration = self.rule_book.next_configuration(self.current_configuration, character)
        #使状态自动转移
        if (self.current_configuration.stack.top() == '$' and self.current_configuration.state == 2):
            self.current_configuration.state=1

    # 同样为了简化操作,方便连续输入
    def read_string(self, string):
        for c in string:
            self.read_character(c)


if __name__ == '__main__':
    dpda = DPDA(PDAConfiguration(1, Stack(['$'])), [1], rulebook)
    print(dpda.accepting())
    dpda.read_string('(())') #用来匹配的文本
    print(dpda.accepting())
    
复制代码