Replacing literal variables with values ​​from a binary vector in a logical stack calculator in Python

Question:

First serious "work" in Python. Wrote the part that is responsible for converting a string – a logical expression into a kind of reverse Polish notation. There she is:

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));

Problems arise when it is necessary to substitute values ​​(zeroes and ones) instead of literal variables, since the substitution will be performed not by one letter, but by a whole binary vector. Can't think of a way to make this as "elegant" as possible, but at the same time secure.

Answer:

The get_lookup_table() and evaluate() approach works if the variable names are limited to a single lowercase latin letter. You can implement them more idiomatically in Python:

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])

Example:

>>> 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))'

Or in one line using str.translate() :

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

Although if you have an expression in Reverse Polish Notation as input, such as 'abcd!&|&' , then you can evaluate it using a simple stack loop:

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()

Example:

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