Write an expression evaluator for boolean expressions encoded as JSON. Read on for explanation and rules.
Motivation:
Consider a scenario where two agents (Alice and Bob) are communicating with each other under the following constraints:
- All communication must be done as valid JSON strings (no JSONP or extensions), because Bob and Alice love JSON. They have had problems with character encoding in the past, so they have decided to restrict themselves to ASCII.
- Alice needs Bob to notify her in case a certain condition is met, but:
- Bob doesn't know what the condition is in advance.
- Alice can't evaluate the condition herself because it requires information that only Bob has.
- The status of the variables can change rapidly enough (and the network is slow enough) that it would be infeasible for Bob to continuously transmit the data to Alice.
- Neither knows anything about the implementation of the other agent (for example, they can't make assumptions about the implementation language of the other agent).
Alice and Bob have worked out a protocol to help them complete their task.
Representing Conditional Expressions:
They have agreed to represent Boolean literals by strings, for example
"foo"
or"!bar"
, where!
represents the negation of a literal, and valid names contain only letters and numbers (case sensitive, any strictly positive length;""
and"!"
are not valid; i.e. a literal is a string whose contents match the regex/^!?[a-zA-Z0-9]+$/
).Expressions are only transmitted in negation normal form. This means that only literals can be negated, not subexpressions.
Expressions are normalized as a conjunction of disjunctions of conjunctions of disjunctions ... etc encoded as nested arrays of strings. This needs a bit more explanation, so...
Expression Syntax:
Consider the following boolean expression:
(¬a ∧ b ∧ (c ∨ ¬d ∨ e ∨ ¬f) ∧ (c ∨ (d ∧ (f ∨ ¬e))))
Notice that the entire expression is contained in parentheses. Also notice that the first level(and all odd levels) contains only conjunctions(∧), the second level(and all even levels) contains only disjunctions(∨). Also notice that no subexpression is negated. Anyway meat and potatoes... This would be represented by Alice in JSON as:
["!a","b",["c","!d","e","!f"],["c",["d",["f","!e"]]]]
Another example:
((a ∨ b ∨ c))
Becomes:
[["a","b","c"]]
In summary: []
are interpreted as parentheses, literals are wrapped in ""
,!
means negation, and ,
means AND
or OR
depending on nesting depth.
NB: the empty conjunction (the result of AND
ing no variables) is true
, and the empty disjunction (the result of OR
ing no variables) is false
. They are both valid boolean expressions.
Bob's data:
Bob's data is emitted by a program on his computer as a simple JSON object as key-value pairs, where the key is the name of the variable, and the value is either true
or false
. For example:
{"a":false,"b":true,"c":false}
Bob needs our help!
Bob has little programming experience, and he's in over his head. He has handed you the task.
You need to write a program that accepts the JSON text that Alice sent along with the JSON text for Bob's data, and evaluates the expression with those values, returning true or false (the actual strings true
and false
; Bob and Alice love JSON, remember?)
Bob says less is more, so he wants you to make your source code as short as possible (this is a code-golf)
You are allowed to use an external library to parse the JSON text, but this is the only exception. Only standard library functionality is allowed.
Note that the JSON is accepted and returned as a string. There is no requirement to explicitly parse it though, if you can get it to always work without doing so.
If Alice uses a variable that Bob doesn't know, assume it is false. Bob's data may contain variables that Alice doesn't use.
If Alice's or Bob's JSON Object contains an invalid literal, or the JSON is invalid, or it contains a non ASCII character, then your program must return
null
Some test cases(in JSON):
[
{"alice":"[\"\"]","bob":"{}","result":"null"},
{"alice":"[\"!\"]","bob":"{}","result":"null"},
{"alice":"[\"0\"]","bob":"{\"0\":true}","result":"true"},
{"alice":"[]","bob":"{}","result":"true"},
{"alice":"[[]]","bob":"{}","result":"false"},
{"alice":"[\"a>\"]","bob":"{\"a\":true}","result":"null"},
{"alice":"[\"0\"]","bob":"{}","result":"false"},
{"alice":"[\"0\"]","bob":"","result":"null"},
{"alice":"[\"1\"]","bob":"{\"1\":false}","result":"false"},
{"alice":"[\"true\"]","bob":"{\"true\":false}","result":"false"},
{"alice":"[\"foo\",\"bar\",\"baz\"]","bob":"{\"foo\":true,\"bar\":true,\"biz\":true}","result":"false"},
{"alice":"[[[\"a\",[\"!b\",\"c\"],\"!c\"],\"d\"]]","bob":"{\"a\":true,\"b\":false,\"c\":true,\"d\":false}","result":"false"},
{"alice":"[\"!a\",\"b\",[\"c\",\"!d\",\"e\",\"!f\"],[\"c\",[\"d\",[\"f\",\"!e\"]]]]","bob":"{\"a\":false,\"b\":true,\"c\":true,\"e\":true,\"f\":false}","result":"true"}
]
As can be seen from the test cases, input and output are strings that are correctly parseable JSON. The empty string test case for bob
was originally in error, the correct value to return is null
, but if it saves you characters to return false
, then that is also acceptable. I added cases for the empty clauses to make that explicit. I added another 2 test cases in response to a bug I found in someone's implementation
0
is not a valid identifier name. Is it deliberate that you include it nevertheless? \$\endgroup\$