How to create a string interpreter in python that takes propositions and return an answer based on a given dictionary keys?
<p>So after 2 days of struggling with this problem i gave up. You are given two inputs the first one is a lists that contains propositions and the second one is a dictionary. </p>

<p>example: </p>

<pre><code>arg= [&lt;prop1&gt;, "OPERATOR", &lt;prop2&gt;]

dicti= {&lt;prop1&gt;: key1, &lt;prop2394&gt;: key2394,&lt;prop2&gt;:key2}
</code></pre>

<p>the following is a possible input:</p>

<pre><code>    arg= [&lt;prop1&gt;, "OPERATOR (AND OR )",
[ "NOT" ,["NOT",&lt;prop2&gt;,"OPERATOR"[&lt;prop2&gt;, "OPERATOR", &lt;prop3&gt;]]]
</code></pre>

<p>I am betting that the problem wont be solved without using double recursion. This is my attempt to solve the problem, i started with base case that the input is a "<em>flat</em>" list which means 1D list that has no lists as elements of the the list. The program should not return boolean values but return <code>true</code> or <code>false</code> which are given in the dictionary.</p>

<pre><code>def interpret(arg, keys ):
    if not arg :
        return "false"
    elif not arg and not keys:
        return "false"
    elif not keys and isinstance(arg,list):
        return "true"
    elif isinstance(arg[0],list):
        return interperter(arg[0:],keys)
    else:
        trueCnr=0
        for i in range(len(arg)):
            if arg[i] in keys and keys[arg[i]]=="true":
                if isinstance (arg[i], list):
                    if("NOT" in arg):
                        indx= arg.index("NOT")
                        keys[arg[indx+1]]= "true" if keys[arg[indx+1]]=="true" else "false"
                    trueCnr+=1
        print(trueCnr)
        if trueCnr==len(arg)-1 and "AND" in arg: return "true"
        elif trueCnr!= 0 and "OR" in arg: return "true"
        else: return "false"

print (interpret(["door_open", "AND", ["NOT","cat_gone"]], {"door_open" : "false", "cat_gone" : "true", "cat_asleep" : "true"} ))
</code></pre>

<p>My question is how do i proceed from here.</p>

<p>You need to use recursion.  Define a function <code>eval(prop, keys)</code> to evaluate the proposition.  Then match the proposition with a case.  For example,</p>

<pre><code>['prop1', 'AND', 'prop2']
</code></pre>

<p>If you see the above, you would evaluate it as </p>

<pre><code>return eval(prop[:1], keys) and eval(prop[1:], keys)
</code></pre>

<p>A more complex example:</p>

<pre><code>[ "NOT" ,["NOT",'prop2',"OPERATOR"['prop2', "OPERATOR", 'prop3']]]
</code></pre>

<p>would look like</p>

<pre><code>return not eval(prop[1], keys)
</code></pre>

<p>The thing to realize is that at each call to <code>eval</code>, exactly one operator has precedence.  Your job is to recognize which operator that is, then pass the rest of the list off to other <code>eval</code> calls to handle.</p>

<p>In pseudocode:</p>

<pre><code>def eval(prop, keys):
  if not prop:
    return False
  if prop is a key:
    return keys[prop]
  if prop has a binary operator:
    return eval(stuff before operator) operator eval(stuff after operator)
  if prop has unary operator:
    return operator eval(stuff after operator)
</code></pre>

<p>Also, notice that you must return booleans <code>True</code> and <code>False</code> not strings <code>'True'</code> and '<code>False</code>'</p>

python recursion functional-programming string-interpolation