Working with python, do I need to write down AST to evaluate a boolean function?

Question

I am working on a project, one part of it is to generate a truth table for a given boolean expression ( such as: (A NOT B) NOR (C OR D)). I could not find a built in bitwise operator for NOR gate, so I wrote a code of my own for it, which works good with simple expressions. But if brackets are introduced for unambiguity and false results, the code does a terrible job. [for example, for the expression mentioned above, it gives an output of (a~b~()|()c|d)] Here is the code snippet:

 # to replace NOR gate with bitwise NOR operation of ~(var_a | var_b)
  for m in range(0,len(expression)):
   v=len(expression)
   for v in range(0,len(expression)):
     if (expression[v]=="!"):
        prev='~(' + expression[v-1]
        nextt=expression[v+1]+')'
        replacement= prev + "|" + nextt
        leftear= expression[:v-1]
        rightear=expression[v+2:]
        print('left right ears:',leftear,rightear)
        expression= leftear+replacement+rightear
        
  print('expression refined= X= ',expression)

The only solution that I found on google was to write a parse tree (which python says that, it has been deprecated so we are recommended to use AST). I am a total beginner and search out a little bit about parse trees, but I wanted to ask: 1)Is the AST or parsers the only way to do it? Are there any built in functions for it in python? 2) Whats the better way of handeling NOR gate ?

The solution you found means that instead of calculating the result of the expression while you traverse it, you first parse it into an object and continue working on that parsed object. This is a great way of handling your brackets. Of course you can also handle brackets directly when traversing your input but this will probably result in spaghetti code — Tracer69
– Tracer69, Commented Jul 20, 2021 at 13:21
The ast module can parse Python code. If the only non-Python syntax is NOR, you can try to extend Python syntax a little. Which syntax are you required to parse? Just one example (A NOT B) NOR (C OR D)) doesn't show it all. Are you required to parse XOR? Any Python expression, including arithmetic? Also, what operator precedence should you use (e.g. how to parse NOT A AND B)? The answer to these questions will affect the decision of whether or not to use ast. Also, what does A NOT B mean? — anatolyg
– anatolyg, Commented Jul 20, 2021 at 16:30

Arne · Accepted Answer · 2021-07-20 15:41:33Z

0

Why does it have to be bitwise? Judging from your example, you could just use the normal Boolean operators.

It's true there is no nor in Python, but you can easily translate it, because E NOR F equals NOT E AND NOT F, and not and and are available in Python.

For example:

from itertools import product

print('  A  |  B  |  C  |  D  | (A AND NOT B) NOR (C OR D)')
print('---------------------------------------------------')

for a, b, c, d in product((True, False), repeat=4):
    result = not (a and not b) and not (c or d)
    print('{:^5}|{:^5}|{:^5}|{:^5}|{:^34}'.format(a, b, c, d, result))

  A  |  B  |  C  |  D  | (A AND NOT B) NOR (C OR D)
---------------------------------------------------
  1  |  1  |  1  |  1  |                0                 
  1  |  1  |  1  |  0  |                0                 
  1  |  1  |  0  |  1  |                0                 
  1  |  1  |  0  |  0  |                1                 
  1  |  0  |  1  |  1  |                0                 
  1  |  0  |  1  |  0  |                0                 
  1  |  0  |  0  |  1  |                0                 
  1  |  0  |  0  |  0  |                0                 
  0  |  1  |  1  |  1  |                0                 
  0  |  1  |  1  |  0  |                0                 
  0  |  1  |  0  |  1  |                0                 
  0  |  1  |  0  |  0  |                1                 
  0  |  0  |  1  |  1  |                0                 
  0  |  0  |  1  |  0  |                0                 
  0  |  0  |  0  |  1  |                0                 
  0  |  0  |  0  |  0  |                1

edited Jul 20, 2021 at 15:41

answered Jul 20, 2021 at 15:26

Arne

10.6k2 gold badges22 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

blackbrandt Over a year ago

Consider using itertools to avoid the deep nested loops.

Junior Over a year ago

Oh yeah I don't need to use bitwise, its just increasng lines of code, Thank you 🖤 But, you translated the NOR gate by yourself. Thats exactly my problem. I want my program to take input from user and replace NOR via function, and like, in (A AND B) NOR (C OR D), NOR gate is in between two bracket terms and NORs the results of its neighbouring calculations. So I can't replace it directly. In my code, I have translated the NOR gate into NOT (A or B) as well but if there're backets around, it can't find the variables to NOR.

VirtualScooter · Accepted Answer · 2021-07-21 07:51:47Z

Assuming you can also use prefix notation, you might be able to use the sympy library.

Below is a small program that demonstrates using it for a sample expression derived from your question, with some code at the end to generate the truth table for the expression using the satisfiable function, which generates all possible models for the logic expression.

import itertools
from sympy import *
from sympy.logic import simplify_logic
from sympy.logic.inference import satisfiable

my_names = 'ABCD'
A,B,C,D = symbols(','.join(my_names))
e1 = Nor(Nor(A, B), Or(C, D))
e2 = ~(~(A | B) | (C | D))
print('e1 and e2 are same:', e1 == e2)
print(simplify_logic(e1))
my_symbols = sorted(e1.atoms(Symbol), key=lambda x: x.name)
print('Set of symbols used:', my_symbols)
models = satisfiable(e1, all_models=True)
sat_mods = []
for m in models:
    sat_mods.append(dict(sorted(m.items(), key=lambda x: x[0].name)))
truth_tab = []
for c in itertools.product((True, False), repeat=4):
    model = dict(zip(my_symbols, c))
    truth_tab.append((model, model in sat_mods))
print(truth_tab)

Output:

# e1 and e2 are same: True
# ~C & ~D & (A | B)
# Set of symbols used: [A, B, C, D]
# [({A: True, B: True, C: True, D: True}, False),
#  ({A: True, B: True, C: True, D: False}, False),
# ...

Collectives™ on Stack Overflow

Working with python, do I need to write down AST to evaluate a boolean function?

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related