5

評価したい論理式があります。式は入れ子にすることができ、T (True) または F (False) と括弧で構成されます。括弧 "(" は「論理 OR」を意味します。2 つの用語 TF が隣り合っている場合 (または他の 2 つの組み合わせが隣り合っている場合) は、ANDED (論理 AND) である必要があります。

たとえば、式:

((TFT)T) = true

この問題を解決するためのアルゴリズムが必要です。最初に式を論理和または論理積の正規形に変換してから、式を簡単に評価できるようにすることを考えました。しかし、式を正規化するアルゴリズムが見つかりませんでした。助言がありますか？ありがとうございました。

問題の説明はここにあります: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=2&category=378&page=show_problem&problem=2967

編集：問題の一部を誤解しました。与えられた論理式では、AND/OR 演算子はすべての括弧 "(" と交互に使用されます。式をツリーで表す場合、AND/OR 演算子はサブツリーの深さレベルに依存します。ただし、最初に、最も深いレベルのツリーは AND ツリーであると仮定しました. 私の仕事は、おそらくツリーを構築することによって、与えられた式を評価することです. 問題の正しい要件を明確にした以下の回答に感謝します.

4

4 に答える 4

3

文字列を左から右にスキャンします。左括弧が表示されるたびに、新しいエントリをスタック構造に追加します。右括弧が表示されたら、スタックの一番上のエントリをポップし、それを T または F に評価し、スタックを再度ポップして、計算された値をポップされた項に追加します。文字列の最後まで続けます。この時点で、T と F の文字列が得られ、それを評価します。

T と F の文字列を評価するには、すべてが T の場合は T を返し、そうでない場合は F を返します。だから私たちは...

evaluate(String expression)
 1. subexpr = ""
 2. for i := 1 to n do
 3.     if expression[i] == "(" then
 4.         stack.push(subexpr)
 5.         subexpr = ""
 6.     else if expression[i] == ")" then
 7.         result = evaluateSimple(subexpr)
 8.         subexpr = stack.pop() + result
 9.     else subexpr += expression[i]
10. return evaluate2(subexpr)

evaluate2(String expression)
 1. for i := 1 to n do
 2.     if expression[i] == "F" then return "F"
 3. return "T"

または、そのようなことを行う必要があります（編集：実際、これは尋ねられたとしても、質問に正しく答えません。コメントを参照してください。それでも正しい方向に進むので、これをそのままにしておきます）。evaluate2 と同じことを行う関数 evaluate を 1 つだけ持つこともできますが、最初のループの後で、subexpr に対してのみであることに注意してください。これにより、必要な不要なコピーを回避できますが、逆にコードが少なくなります。

于 2012-12-06T21:34:35.970 に答える
2

元の問題を見た後、あなたはそれを誤解したと思います。

この質問は、最も深いレベルAND/ORのノードがノードであるツリーに関するものです。他のノードの論理演算はこの要因によって決定されます-それらが最初にノードであるかノードであるかはわかりません。最も深いレベルのノードがノードであるとだけ与えられます-したがって、次に高いレベルのノードはノードです、そして次に高いレベルはノードなどです...論理的な工作員はツリーの異なる深さの間で交換します。彼らが提供したサンプルツリーを見ると、これは明らかになります。ANDANDORANDORANDAND/OR

この問題に取り組む方法は、最初にルートノードの論理接続詞を理解することです。これは、式を1回スキャンし、括弧の数を追跡することで実行できます。()それぞれがツリー（ツリーの次のレベル）の新しいノードに対応することに注意してください。例として、次の式について考えてみます。

((F(TF))(TF))

この式を歩くと、最初に3つの開き括弧、2つの閉じ括弧、1つの開き括弧、最後に2つの閉じ括弧が表示されます。このウォーク中に任意の時点で開いていた括弧の最大数を取得すると、それはこのAND/ORツリーの最大の深さになります（3上記の例では）。

では、これはどういう意味ですか？ツリーの深さが奇数の場合、ルートノードはANDノードです。それ以外の場合、ルートはORノードです（接続が交互になっているため）。

ルートノードの接続がわかったら、単純なスタックベースのマシンを使用してこの式を評価できます。かっこを開いたり閉じたりするたびに、接続を反転する必要があることに注意する必要があります。上記の式が評価される方法は次のとおりです。

AND |- (•(F(TF))(TF))

箇条書きは、式のどこにいるかを示していることに注意してください（スタックの一番上など）。次に、以下のように進めます。

OR  |- ((•F(TF))(TF))   // flipped the connective because we jumped a node
OR  |- ((F•(TF))(TF))   // nothing to evaluate on the current node, push F
AND |- ((F(•TF))(TF))
AND |- ((F(T•F))(TF))
AND |- ((F(TF•))(TF))
AND |- ((F(F•))(TF))    // Two booleans on top, T AND F = F (reduce)
OR  |- ((F(F)•)(TF))    // Jumped out of a node, flip the sign
OR  |- ((FF•)(TF))      // Completely evaluated node on top, (F) = F (reduce)
OR  |- ((F•)(TF))       // Two booleans on top, F OR F = F (reduce)
AND |- ((F)•(TF)) 
AND |- (F•(TF))
OR  |- (F(•TF))
OR  |- (F(T•F))
OR  |- (F(TF•))
OR  |- (F(T•))
AND |- (F(T)•)
AND |- (FT•)
AND |- (F•)

したがって、最終的な答えはとして得られFます。これはshift-reduce解析とある程度の関係がありますが、この場合の減少は、操作しているASTの現在の深さに依存します。このアイデアをコードに変換できることを願っています（現在有効な論理演算を追跡するには、スタックとグローバル変数が必要です）。

最後に、そのサイトをご紹介いただきありがとうございます。あなたもこのサイトが好きかもしれません。

于 2012-12-07T00:11:24.753 に答える
1

上記とは異なる手法を使用してこの問題を解決しました。そして、オンラインシステム審査員に受理されました。

ツリーの最初のレベルで演算子を見つけた後 (@Asiri Rathnayake のアイデアに感謝)、式ツリーを再帰的に構築します。建設中、私はストリングをスキャンします。文字が '(' の場合、現在の演算子の値でノードを作成し、それをツリーに追加します。次に、演算子を交互に使用して、より深い再帰レベルに進みます。文字が 'T' の場合、作成します値が「True」のノードをツリーに追加し、スキャンを続行します. 文字が「F」の場合、値が「False」のノードを作成し、それをツリーに追加してスキャンを続行します.文字が ')' の場合、1 レベル上の再帰に戻ります。

最後に、式ツリーを完成させます。あとは、基本的な再帰関数を使用してツリーを簡単に評価するだけです。

以下は私のC++コードです：

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

struct Node {

    char value;
    vector<Node*> children;
};


void ConstructTree (int &index, string X, Node *&node, int op)
{

    for(; index<X.size(); index++)
    {
        if(X[index]=='T')
        {
            Node *C= new Node;
            C->value='T';
            node->children.push_back(C);
        }


        else if(X[index]=='F')
        {
            Node* C= new Node;
            C->value='F';
            node->children.push_back(C);
        }


        else if(X[index]=='(')
        {
            if(op==0)
            {
                Node* C= new Node;
                C->value='O';
                node->children.push_back(C);
            }


            else
            {
                Node* C= new Node;
                C->value='A';
                node->children.push_back(C);
            }

            index++;
            ConstructTree(index,X,node->children[node->children.size()-1],1-op);
        }

        else
            return;
    }



}

bool evaluateTree(Node* node)
{
    if(node->value=='T')
        return true;
    else if(node->value=='F')
        return false;
    else if(node->value=='O')
    {
        for(int i=0; i<node->children.size(); i++)
            if(evaluateTree(node->children[i])==true)
                return true;

        return false;
    }

    else if(node->value=='A')
    {

        for(int i=0; i<node->children.size(); i++)
            if(evaluateTree(node->children[i])==false)
                return false;

        return true;
    }
}


int main()
{
    string X;
    int testCase=1;

    while(cin>>X)
    {
        if(X=="()")
            break;


        int index=0;

        int op=-1;

        int P=0;

        int max=0;
        for(int i=0; i<X.size(); i++)
        {
            if(X[i]=='(')
                P++;
            if(X[i]==')')
                P--;

            if(P>max)
                max=P;
        }


        if(max%2==0)
            op=0; //OR
        else
            op=1; //AND


        Node* root = new Node;

        if(op==0)
        root->value='O';
        else
        root->value='A';

        index++;
        ConstructTree(index,X,root,1-op);

        if(evaluateTree(root))
            cout<<testCase<<". true"<<endl;
        else
            cout<<testCase<<". false"<<endl;

        testCase++;
    }
}
于 2012-12-26T20:05:15.027 に答える
1

リンク先のサイトの問題の説明を読むと、問題を誤解している可能性があると思います。「論理 AND」または「論理 OR」のどちらが必要かは、ルート ノードから何レベル下にあるかによって異なります。

この問題は、式を構文ツリーに構文解析してから再帰的にツリーをたどり、ルート ノードに戻るまで各サブ式を評価することで簡単に解決できます。

于 2012-12-06T21:38:57.063 に答える