Algorithm to return an array with all pieces of a logical expression

Question

1.00/5 (1 vote)

See more:

I have been trying to find a solution for this problem for 5 days now and could not come up with an algorithm that will work for every input. I really need some help!

Here is an example of an input and the expected output.

Input:

Logical Expression: ((-A)+(-B)) + (-C) // not A OR not B

Expected Output:

array:[A, B, (-A), (-B), (-C), (-A)+(-B), ((-A)+(-B))+(-C)]

What I have tried:

Java

    public static ArrayList<string> rec(String str){
    int count = 0;
    char ch;
    String s = "";
    ArrayList<string> array = new ArrayList<string>();

    for(int i = 0; i < str.length(); i++){
        ch = str.charAt(i);

        if(ch == '(')
            count++;
       
        if(count > 0)
            s += ch;

        if(ch == ')')
            count--;

        if(count == 0 && s != ""){
            s = s.substring(1, s.length()-1);
            array.add(s);
            count = 0;
            return rec(s);
        }
    }
    return array;
}

Posted 6-Jun-16 14:04pm

Member 12569032

Updated 7-Jun-16 3:52am

Patrice T

v3

Add a Solution

Comments

Matt T Heffron 6-Jun-16 20:21pm

You showed what you expect...how is that different from what you actually got?
(Use the "Improve question" above to add the information, and any other information that may be useful, like: does it work for some inputs but not others?)

2 solutions

Solution 2

Quote:
Logical Expression: ((-A)+(-B)) + (-C) // not A OR not B

First- problem: the comment say nothing about the variable C, thus it don't match the expression.

Quote:
array:[A, B, (-A), (-B), (-C), (-A)+(-B), ((-A)+(-B))+(-C)]

As SA said in Solution 1, the analyze of an expression leads to a tree structure, not a list. If you really need a list, you have to explain us the context.
Your expected output list is not consistent either. If you look carefully, you will see that you need A and B but not C. I see not reason to this.
The order of the array elements is also highly suspect. The array is sorted with the length of element, which is not related to some analyze logic.

At least you need to give us more explanations about the context, so we can understand why you do things this way.

Posted 7-Jun-16 3:52am

Patrice T

Updated 8-Jun-16 9:20am

v2

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Sergey Alexandrovich Kryukov · Accepted Answer · 2016-06-06T14:33:00

You are making two fatal mistakes, from the very beginning; and this mistake drives all your development nowhere.

First mistake is quite obvious: dealing with strings as elements of an expression. I don't think it needs any explanation. In Computer Algebra Systems (CAS) expressions and calculations are often called "symbolic", and I already met some naive people thinking that "symbols" should mean characters or string. But it makes no sense. So, what is, structurally, an expression?

If you look thoroughly at the expression structure, you will see that it is a tree. In most algebras, it is a binary tree, with some nodes having only zero or one child node, which can be represented as a binary tree where "left" or "right" children (really representing left or right operand in the order they are written in usual mathematical notation), or both operand children are null.

Please see:
Binary expression tree — Wikipedia, the free encyclopedia.

То represent such tree with Java, you have to define a node class, which represent an operator, Boolean or not. The operator type is best represented as an enum type, but it can also be an abstract class with some virtual functions to be overridden in each concrete runtime class; this way, you could use polymorphism. The choice depends on what you want to achieve.

Here is the conclusion: you have to make a step back and redesign everything based on trees; forget lists and string elements. Based on that, you can develop parsing of the expression string into the tree and all other operations required. The topics of programming dealing with expression trees are very popular, so you can find a lot of code samples, open-source products, tutorials, and so on: Java: binary expression tree.

—SA