#Java algorithm problem

71 messages · Page 1 of 1 (latest)

lethal kraken
#

i have this formula: A&(A->B)<=>(C&A->B&C) and i want to write all subformulas of it such as:
A, B, C, A->B, A&(A->B), C&A, B&C, (C&A->B&C), A&(A->B)<=>(C&A->B&C).
i've been thinking about creating a tree with this formula and somehow when i traverse the formula in an order, i can select the leafs and somehow concatenate the other nodes in order to get some subformulas and add them to a list of generic type string but i'm not sure this is the right way. do you have any ideas? maybe using recursion?

stark pantherBOT
#

⌛ This post has been reserved for your question.

Hey @lethal kraken! Please use /close or the Close Post button above when your problem is solved. Please remember to follow the help guidelines. This post will be automatically closed after 300 minutes of inactivity.

TIP: Narrow down your issue to simple and precise questions to maximize the chance that others will reply in here.

lament dew
lethal kraken
lament dew
#

I dont know

#

I didnt understand ur question

#

explain better

#

the formulas

#

how they work

#

and what ur tryingto achieve

#

Input:

#

Output:

lethal kraken
#

input is this: A&(A->B)->(C&A->B&C)

#

output: A, B, C, A->B, A&(A->B), C&A, B&C, (C&A->B&C), A&(A->B)<=>(C&A->B&C).

#

extracting them

#

the subformulas form the formula

lament dew
#

you can do this with regex

lethal kraken
#

not quite familiar with it

lament dew
#

this outputs all the letters for example

#

to only have 1 copy of one

#

u can use a set

#

sets dont allow duplicates

#

there u go

lethal kraken
#

yeah i used it just to extract the single ones, but as for more complex operations i don't have ideas using regex

lament dew
#

well

#

how deep can these formulas go

#

are u only trying to extract this one

#

or is this a general method ur going to use toe xtrat formulas

#

etc

lethal kraken
#

there are many more who could use ~ or = as equivalent, it has to fit these criterias

lament dew
#

show me another example of that formula

lethal kraken
#

there could be a sign as <-> or <=> depends on writing

lament dew
#

my question is

#

is there any general structure to the formula

#

or no

lethal kraken
#

there isn't

lament dew
#

so it can be anything

#

like'

#

helloworld->aaaa

lethal kraken
#

yea

lament dew
#

well the oprators

lethal kraken
#

mainly, these are the operators: !, &, ||, ^, ~, =, <->, <=>,

lament dew
#

are the general structur then

#

define how they work

lethal kraken
#

the operators should be defined by me in functions for example

tardy crescentBOT
#

-> has this function: private static int implicatie(int a, int b) { return ((a == 1) && (b == 0)) ? 0 : 1; }

This message has been formatted automatically. You can disable this using /preferences.

lament dew
#

a parenthesis for example

#

what can it contain

#

?

lethal kraken
#

well these letters A,B,C.. represent binary digits, i'm trying to compare them in the final part of the exercise when i'll create the table, but that's the easy part since i'll apply the functions that i told you about above. but how can i use those functions if i don't have the subformulas of my formula

#

the paranthesis can contain any crazy things such as

#

((!A)&B||C)

#

that's why i'm desperate to find the subformulas

lament dew
#

formulas and subforumals can be separated by & -> <- and <-> right

lethal kraken
#

formula is the entire thing, which is separated by these operators

#

these operators form the subformulas

#

this is how the table looks like on paper

#

you just use all the possibilities

lament dew
#

I have no idea how this can be done

#

if u can explain the point of all of this

#

maybe i find a way

lethal kraken
#

i guess if the main formula is too complicated

#

you just take one subformula at a time to solve the way the table shows: you first solve A->B and then using the result from A->B, you will solve A&(A->B)

#

that's the point of the exercise

#

sort of divide et impera where you make the problem smaller and smaller

dull elbow
#

If you have an arbitrary string like "A&(A->B)", then parsing it recursively is probably your best bet. Regexes typically don't work for recursive structures.

What you typically do is define some interface like "Expr", and then make different kinds of expressions as subclasses, like "BinaryExpr", "UnaryExpr", "GroupExpr", or "LiteralExpr".
You can then define methods like "solve()" or "toString()" on the interface that is trivial for LiteralExpr, while BinaryExpr recursively calls solve/toString on its' parts.

To build up the expression tree, you again rely on recursion.
It's important to try to parse a binary expression before attempting to parse a literal, because "A&B" might look like a literal at first (A), and is only discovered to be a binary expression when "&B" is examined.
At the same time, if you try to parse an expression by first trying to parse a (left) expression, you will get into an infinite loop without consuming any input.
So the left side of the binary expression must be "more simple" - it cannot be a binary expression, but could still be a unary expression, a group, or a literal. A group itself might contain an arbitrary expression though.

Sometimes you don't know if you want to consume a character or not before consuming it, so you should probably create you own class that wraps an InputStream or similar, that remembers what has been read, and can be "rewound" x number of characters if we didn't find what we searched for (like a 2-character operator).

It's not an easy problem to tackle, and for a real-life scenario I would probably use a parser combinator or parser generator.