Skip to content

Instantly share code, notes, and snippets.

@ohbadiah
Last active September 17, 2020 13:29
Show Gist options
  • Save ohbadiah/4da139d094c16620b07cc767ddf06f0d to your computer and use it in GitHub Desktop.
Save ohbadiah/4da139d094c16620b07cc767ddf06f0d to your computer and use it in GitHub Desktop.
Infix-prefix coding problem
We have some expressions, represented as a list where every term is either:
- A variable (e.g. A, B, C)
- A boolean operator (AND or OR)
- A nested expression (list)
You're presented an expression with infix operators, like:
[A AND [B OR C]]
Can you transform these expressions so the operators are in prefix order? The output for this case is:
[AND A [OR B C]]
====
If you can do that, let's try:
[A AND [B OR [C AND D]]]
-> [AND A [OR B [AND C D]]]
===
How would you handle this?
[A AND B OR C AND D]
===
Note: the representation of these expressions will be a little different depending on your language,
but the important thing is you don't need to worry about parsing and tokenizing the expression yourself;
it will already come nicely formatted. For example, in javascript it could look like:
["A", "AND", ["B", "OR", "C"]]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment