I have been presented the problem of reading an input file that contains logic statements, and am required to construct a Truth Table to determine whether an ASK matches any/all models that are determined. An example of some data I may expect to read in is:
(p & z => x) => ((p | d) & z)
Please don't get too caught up in the example and whether it really makes sense, I just made it up to show the different compositions I may be presented with. Multiple such statements can be separated with semicolons.
I have sorted out the semicolon splitting without any dramas, and now have a vector of strings containing each separate statement, where each string is as presented above. Now without parenthesis being involved, I believe determining the statements would be rather straight forward, but with their involvement I am now required to compute different sections before others. EG:
(p | d) = result and then (result & x)
I have seen people discussing the concept of using a stack to determine if open brackets are closed properly, but I do not believe that this would be appropriate for my situation as this would not allow me to determine what statements were inside what set of parenthesis.
The current idea I have is to use the stack idea, and try to determine the "depth" of a statement (essentially how far it is nested) and then mark this number with each statement, but I believe this sounds like an inelegant solution. Does anyone have any tips as to how I should construct an algorithm to properly address the problem?
You need to build a tree of the expressions, where your variables are leaves.
Your expression will then become:
=>
/ \
/ \
/ \
=> &
/ \ / \
& X | Z
/ \ / \
p z P D
Once you have built this kind of representation, the evaluation is straightforward.
Another approach, with the same result, is reducing your expression to something like RPN (where you can use your stack idea):
P, Z, &, X, =>, P, D, |, Z, &, =>
As suggested in the comments, you can do it with the shunting yard algorithm.