# 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.

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
``````
Scroll to Top