3

オペランドと二項演算子で構成される式は、両方のオペランドの後に演算子を記述することにより、逆ポーランド記法 (RPN) で記述できます。たとえば、3 + (4 * 5) は「3 4 5 * +」と記述できます。

x と * で構成される文字列が与えられます。x はオペランドを表し、* は二項演算子を表します。そのような文字列のすべてが有効な RPN 式を表しているわけではないことは容易にわかります。たとえば、「xx*」は有効な RPN 式ではありませんが、「xx*」と「xxx**」は有効な式です。指定された文字列を有効な RPN 式に変換するために必要な挿入、削除、および置換操作の最小数は?

入力: 最初の行にはテスト ケースの数 T が含まれます。T 個のテスト ケースが続きます。各ケースには、文字 x と * のみで構成される文字列が含まれます。

出力: T 行を出力します。必要な操作の数が最も少ないテスト ケースごとに 1 行です。

制約: 1 <= T <= 100 入力文字列の長さは最大 100 です。

サンプル入力:

5
x
xx*
xxx**
*xx
xx*xx**

サンプル出力:

0
0
0
2
0

説明：

最初の 3 つのケースでは、入力式はすでに有効な RPN であるため、答えは 0 です。4 番目のケースでは、1 つの削除操作と 1 つの挿入操作を実行できます: xx -> xx -> xx

4

4 に答える 4

3

これは非常に大きな答えの 1 つです。エレガントなツーライナーが存在しても驚かないでしょうが、それが投稿されるまではここに私のものがあります.

単純な 2D グラフがあるとします。x 軸は解析ステップを表し、y 軸は現在の X と星の数 n(x)-n(*) の差を表します。たとえば、入力xx*xx**の場合、グラフは次のようになります。

╫
╫         +
╫   +   +   +
╫ +   +       +
╬═╧═╧═╧═╧═╧═╧═╧
  x x * x x * *

式が有効であるためには、このグラフが y 軸でゼロ以下に達してはならず、最後に y の値が 1 (スタックに残された単一の値) でなければなりません。

入力式で使用する 3 つの操作 (挿入、削除、置換) が与えられます。この置換操作は、実際には 2 つのうちの 1 つです。x を * に置換するか、* を x に置換します。式の途中で挿入または削除を適用すると、その時点以降、グラフ内のすべてのポイントが上下に移動するようにグラフが変更されます。置換が適用されると、ポイントはグラフ内の 2 つのノッチに対して上下に移動します。興味深いことに、削除操作を行う必要はありません。これは、反対の挿入を適用した場合と同じ結果が得られるためです。ただし、挿入は常に適用でき、シンボルが使用可能な場合にのみ削除されるという違いがあります。

あなたの目標は、操作の最小数を見つけることです。最終目標 (y=1) のみを観察する場合、グラフを移動し、できるだけ多くの置換操作を適用し、さらに 1 つの挿入操作を適用する必要があるノッチの数を決定します。N(x)-N(*) の合計が N の場合、操作の数は floor((N-1)/2) になります。記号は、どの操作が適用されるかを決定します。

問題は、もう 1 つの条件に注意を払わなければならないことです。つまり、グラフがゼロに到達してはならないということです。これを判断するには、まず前の操作を式に適用する必要があります。'insert x' が先頭に追加され、'insert *' が最後に追加され、先頭からすべての * を検索して x に置換し、すべての x を検索して末尾から * に置換します。

このステップの後、新しい表現が得られます。最初から繰り返し、y=0 の場所を探します。そのような場所がある場合は、その前に x を 1 つ挿入し、式の末尾に * を 1 つ挿入して補う必要があります。しかし、すでにそれを行っている可能性があることを思い出してください (先頭に x を挿入するか、末尾に * を挿入してください)。2 つの挿入 x がある場合は、実際には * を x に置き換えたふりをして (操作が 1 つ少なくなります)、x を挿入する必要があることを忘れてください。同様に、インサートのペア *: 2 つのインサート * を削除し、もう 1 つ 'replace x with *' を適用します。最後から検索したときに見つけた x が実際に現在の位置の前にある場合、置換を適用できず、2 つの挿入操作を 1 つの置換に圧縮できないため、実際にそれを適用する、つまり式を変更する必要があります。

最後まで反復を続け、追加の操作をカウントし、挿入 x が 1 つと挿入 * が 1 つあるかどうかを常に念頭に置いてください。それだけです。最後に、いくつかの操作があります。

于 2012-04-04T16:31:10.540 に答える
0

これは明らかに、SE/SWE/SDE ポジションのオンライン コード テスト/チャレンジの問題の 1 つです。個人的には、このスタイルの質問は好きではありません。コーディング/アルゴリズム/設計能力には関係なく、「トリック」を以前に知っているかどうかにすべて関係するからです。「トリック」を知っている限り、helloworld.cpp と同じくらい簡単です。

だからここにトリックがあります：

Dialecticus の投稿から明らかなことが 2 つあります。

  1. X の数が n の場合、任意の時点で最大 (n-1) 個の * があるはずです。
  2. * の最終的な数は、X から 1 を引いた数と正確に等しくなければなりません。

したがって、プログラムは無効な文字列をこれら 2 つの基準を満たす文字列に変換する必要があります (文字列が有効かどうかをチェックする部分は省略します)。さらに、変換の数を最小限に抑える必要があります。では、最小化する方法は？

ここにいくつかの観察があります（文字列の長さが2より大きいと仮定します。そうでない場合は自明です）：

  1. 基準 2. を満たしたいだけの場合は、数回置換し、多くても 1 回の挿入を行うだけで済みます。n(X)>n(*)+1 の場合、X を * に変更し、その逆も同様です。最後に、文字列の長さが偶数の場合は、もう 1 つ X(または *) を挿入します。

  2. 同時に基準 1. を満たしたい場合は、複数の置換と 1 つの挿入が必要ですが、位置が重要です。さらに、文字列の先頭で * を X に、文字列の末尾で X を * に置き換えることは常に安全であることがわかります。また、有効な部分文字列の場合、それを同等の X として表現できることも明らかです。

上記の観察から、この問題は動的計画法によって簡単に解決できることが明らかです。

したがって、この問題は実際にはアルゴリズム/設計能力とは何の関係もありません (実際、スケールは非常に小さいため、1<=T<=100 であり、必要に応じて力ずくで解決することもできます)。交換と最大1回の挿入を行うことができます。

于 2015-02-15T21:07:08.040 に答える
-1

java.util.HashSet をインポートします。java.util.Set をインポートします。java.util.Stack をインポートします。

import org.apache.commons.lang3.mutable.MutableInt;

パブリック クラス ProperRPNConversion {

public static final char X='x';
public static final char S='*';



public static boolean isRPN(String string)
{
    char[] str=string.toCharArray();
    int count=0;
    Stack stack=new Stack();

    for(char c:str)
    {
        if(c==X)
            stack.push(c);
        else
        {
            if(stack.size()>=2)
            {
                if(((Character)stack.peek())==X)
                {
                    stack.pop();
                }
                else
                    return false;
                if(((Character)stack.peek())==X)
                {
                    stack.pop();
                }
                else
                    return false;
                stack.push(X);

            }
            else
                return false;

        }
    }

    if(stack.size()==1&&(Character)stack.peek()==X)
        return true;

    return false;

}


public static int convertToRPNSteps(String s)
{
    Set<String> curLevel=new HashSet<String>();
    Set<String> nextLevel=new HashSet<String>();
    char[] ss=s.toCharArray();
    curLevel.add(s);
    int minsteps=0;

    if(isRPN(s))
        return minsteps;

    while(curLevel.size()!=0)
    {
        minsteps++;
        for(String str:curLevel)
        {
            //delete
            int lenss=str.length();
            for(int i=0;i<lenss;i++)
            {
                String newstr=new StringBuffer(str).delete(i, i+1).toString();
                if(isRPN(newstr))
                {
                    System.out.println(s);
                    System.out.println(newstr);
                    return minsteps;
                }
                nextLevel.add(newstr);
            }
            //insert
            for(int i=0;i<=lenss;i++)
            {
                //System.out.println(i);
                //System.out.println(s);
                //System.out.println(lenss);
                String newstr=new StringBuffer(str).insert(i, X).toString();
                if(isRPN(newstr))
                {
                    System.out.println(s);
                    System.out.println(newstr);
                    return minsteps;
                }
                nextLevel.add(new StringBuffer(str).insert(i, X).toString());
                String newstr2=new StringBuffer(str).insert(i, X).toString();
                if(isRPN(newstr2))
                    return minsteps;
                nextLevel.add(newstr2);
            }

            //replace
            for(int i=0;i<lenss;i++)
            {
                StringBuffer b=new StringBuffer(str);
                if(ss[i]==X)
                    b.setCharAt(i, S);
                else
                    b.setCharAt(i, X);

                String newstr=b.toString();
                if(isRPN(newstr))
                {
                    System.out.println(s);
                    System.out.println(newstr);
                    return minsteps;
                }
                nextLevel.add(newstr);

            }

        }
        curLevel=nextLevel;
        nextLevel=new HashSet<String>();

    }
    return -1;
}





public static void main(String[] args) {

    System.out.println(convertToRPNSteps("xx*xxxx**xx*x**"));
    System.out.println(convertToRPNSteps("*xx"));


}

}

于 2013-11-13T06:16:57.203 に答える