Замена буквенных переменных на значения из двоичного вектора в логическом стековом калькуляторе на Python

#python #алгоритм #python_3x

Первая серьезная "работа" на Python. Написал часть, которая отвечает за преобразование
строки -- логического выражения в подобие обратной польской записи. Вот она:

import operator

ops = {
    '&': {'priority': 1, 'action': operator.and_},
    '|': {'priority': 0, 'action': operator.or_},
    '!': {'priority': 3, 'action': operator.not_},
    '(': {'priority': 4},
    ')': {'priority': 1},
}
operands = [chr(x) for x in range(ord('a'), ord('z') + 1)] + ['0', '1'];


def is_empty(string):
    return len(string) == 0;


def a_prior_b(a, b):
    return ops[a]['priority'] >= ops[b]['priority'];


def check_expression(exp):
    stack = [];
    rpn = [];
    for char in exp:
        if char in operands:
            rpn.append(char);
        elif char in ops:
            if (char == ')'):
                tmp = stack.pop();
                while not is_empty(stack) and tmp != '(':
                    rpn.append(tmp);
                    tmp = stack.pop();
            if is_empty(stack):
                stack.append(char);
            else:
                while not is_empty(stack) and a_prior_b(stack[len(stack) - 1], char) \
                        and stack[len(stack) - 1] != '(':
                    rpn.append(stack.pop());
                if char != ')':
                    stack.append(char);
        else:
            return "";  # Ошибка. Выражение содержит недопустимые символы
    for x in reversed(stack):
        rpn.append(x);
    tmp = "".join(rpn);
    return tmp;

s = "a&(b|(c&!d))";
print(check_expression(s));


Проблемы возникают, когда необходимо подставлять вместо буквенных переменных значения
(нули и единицы), поскольку подстановка будет производиться не по одной букве, а целым
двоичным вектором.  Не могу придумать, как сделать это как можно более "элегантно",
но в то же время безопасно.
    

Ответы

Ответ 1

Подход в get_lookup_table() и evaluate() работает, если имена переменных ограничены
одной маленькой латинской буквой. Можно их более идиоматично в Питоне реализовать:

import string

def get_lookup_table(bits): 
    return dict(zip(string.ascii_lowercase, map(str, bits)))

def evaluate(expression, lookup):
    return ''.join([lookup.get(token, token) for token in expression])


Пример:

>>> import string
>>> expression = "a&(b|(c&!d))"
>>> bits = "0010"
>>> lookup = dict(zip(string.ascii_lowercase, bits))
>>> ''.join([lookup.get(token, token) for token in expression])
'0&(0|(1&!0))'


Или в одну строчку, используя str.translate():

>>> expression.translate(dict(zip(map(ord, string.ascii_lowercase), map(str, bits))))
'0&(0|(1&!0))'




Хотя если у вас на входе выражение в Reverse Polish Notation, такое как 'abcd!&|&',
то можно вычислить его, используя простой цикл со стеком:

import operator

operators = {'!': operator.not_, '&': operator.and_, '|': operator.or_}

def eval_rpn(tokens, namespace):
    stack = []
    for tok in tokens:
        if tok not in operators:
            result = namespace.get(tok, tok) # tok is a name or a boolean
        elif tok == '!': # tok is a unary operator
            operand = stack.pop()
            result = operators[tok](operand)
        else: # tok is a binary operator
            a = stack.pop()
            b = stack.pop()
            result = operators[tok](a, b)
        stack.append(result)
    return stack.pop()


Пример:

>>> tokens = 'abcd!&|&'
>>> lookup = dict(zip('abcd', [0,0,1,0]))
>>> lookup
{'a': 0, 'b': 0, 'c': 1, 'd': 0}
>>> eval_rpn(tokens, lookup)
0


Ответ 2

Код на данный момент оптимального решения:

import operator

ops = {
    '&': {'priority': 1, 'action': operator.and_},
    '|': {'priority': 0, 'action': operator.or_},
    '!': {'priority': 3, 'action': operator.not_},
    '(': {'priority': 4},
    ')': {'priority': 1},
}
operands = [chr(x) for x in range(ord('a'), ord('z') + 1)] + ['0', '1']
variables = [chr(x) for x in range(ord('a'), ord('z') + 1)]


def a_prior_b(a, b):
    return ops[a]['priority'] >= ops[b]['priority']


def check_expression(exp):
    stack = []
    rpn = []
    for char in exp:
        if char in operands:
            rpn.append(char)
        elif char in ops:
            if char == ')':
                tmp = stack.pop()
                while stack and tmp != '(':
                    rpn.append(tmp)
                    tmp = stack.pop()
            if not stack:
                stack.append(char)
            else:
                while stack and a_prior_b(stack[len(stack) - 1], char) \
                        and stack[len(stack) - 1] != '(':
                    rpn.append(stack.pop())
                if char != ')':
                    stack.append(char)
        else:
            return ""  # Ошибка. Выражение содержит недопустимые символы
    for x in reversed(stack):
        rpn.append(x)
    tmp = "".join(rpn)
    return tmp


def get_lookup_table(vect):
    i = 0
    lookup = {}
    while i < len(vect):
        lookup[variables[i]] = vect[i]
        i = i + 1
    return lookup


def evaluate(expression, lookup):
    result = ""
    for x in expression:
        if x in lookup.keys():
            result = result + str(lookup[x])
        else:
            result = result + expression[expression.index(x)]
    return result


if __name__ == '__main__':
    s = "a&(b|(c&!d))"
    print(check_expression(s))
    vect = [0, 0, 1, 0]
    tmp = get_lookup_table(vect)
    print("Подстановочный словарь:", tmp)
    print("Evaluate: ", evaluate(s, tmp))


@gil9red, поправил код в соответствии с вашим советом