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?

Community · Accepted Answer · 2017-05-23 11:46:21Z

1

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.

edited May 23, 2017 at 11:46

CommunityBot

11 silver badge

answered Sep 9, 2016 at 1:08

Ira Baxter

96k24 gold badges188 silver badges357 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Parse propositional logic string

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related