用所有逻辑表达式返回数组的算法 [英] Algorithm to return an array with all pieces of a logical expression

问题描述

我一直在努力为这个问题找到解决方案5天，并且无法提出适用于每个输入的算法。我真的需要一些帮助！



这是一个输入和预期输出的例子。



输入：



逻辑表达式：（（ - A）+（ - B））+（ - C）//不是A或者不是B



预期输出：



数组：[A，B，（ - A），（ - B），（ - C） ，（ - A）+（ - B），（（ - A）+（ - B））+（ - C）]



我有什么试过：

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:

    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;
}

推荐答案

Quote：

逻辑表达式：（（ - A）+（ - B））+（ - C）//不是A或者不是B

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

第一个问题：注释对变量C没有任何说明，因此它不匹配表达式。

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）]

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

正如SA在溶液1中所述，表达式的分析导致树结构，而不是列表。如果你真的需要一个列表，你必须向我们解释上下文。

您的预期输出列表也不一致。如果你仔细观察，你会发现你需要 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.

你从一开始就犯了两个致命的错误;而这个错误驱使你的所有开发无处可去。



第一个错误很明显：将字符串作为表达式的元素处理。我认为不需要任何解释。在计算机代数系统（CAS）中，表达式和计算通常被称为符号，我已经遇到了一些天真的人认为符号应该表示字符或字符串。但这没有任何意义。那么，在结构上，什么是表达式？



如果你仔细研究表达式结构，你会发现它是一棵树。在大多数代数中，它是一个二叉树，一些节点只有零个或一个子节点，可以表示为二进制树，其中左或右子节点（实际上按照它们的顺序表示左或右操作数）用通常的数学符号表示，或者两个操作数都是空的。



请参阅：

二元表达树 - 维基百科，免费的百科全书。


$ b $bТ®用Java代表这样的树，你有定义一个节点类，它代表一个运算符，布尔与否。运算符类型最好表示为 enum 类型，但它也可以是一个抽象类，在每个具体的运行时类中都会覆盖一些虚函数;这样，您可以使用多态。选择取决于你想要达到的目标。



结论是：你必须退后一步，重新设计基于树木的一切;忘记列表和字符串元素。基于此，您可以开发表达式字符串到树中的解析以及所需的所有其他操作。处理表达式树的编程主题非常流行，因此您可以找到许多代码示例，开源产品，教程等等： Java ：二进制表达式树。

-SA

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

这篇关于用所有逻辑表达式返回数组的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！