Parse propositional logic string

Question

I have a propositional logic formula

((a or b) and !d) or e -> c

How is it possible to parse this string, so I can make a truth tree?

I guess I should split my string by ->, and and or, but it will mess up the parentheses. How do I protect each parenthesis before splitting my string? Should I maybe split using regular expression to split by expressions in parenthesis before doing anything else?

For the string in my example, I guess it should make a nested array where ['or', a, b] is the 'deepest' level which is stored in the 'next most deep level' ['and', ['or', a, b]]. So my guess would be that this string should be converted to an array

[
    'implication'
    [
        'or',
        [
            'and',
            [
                'or',
                'a',
                'b'
            ]
        ],
        'e'
    ],
    'c'
]

where each array consists of 3 elements where the first element tells the operator and the two next elements tell which 'propositions' the operator should work on.

I am not sure if this is a clever structure, but I guess it would be a possible way to parse the string.

I have looked at the shunting-yard algorithm to convert from infix to postfix notation or abstract syntax tree (AST). Should I use something like that to do this properly?

score 1 · Answer 1 · edited May 23 '17 at 11:46

First you should define a BNF grammar for your propositional calculus language. This is pretty easy. Then you can use that to define a parser for the language.

See this SO answer on how to hand-write recursive descent parsers easily: Is there an alternative for flex/bison that is usable on 8-bit embedded systems?

This answer also discusses how you can evaluate the expression as you parse it, or how you can save the formula as a "tree" and evaluate it later with different values for the variables.

Parse propositional logic string

1 Answers1