3

由操作数和二元运算符组成的表达式可以用逆波兰表示法 (RPN) 编写，方法是在运算符后面写两个操作数。例如，3 + (4 * 5) 可以写成“3 4 5 * +”。

你得到一个由 x 和 * 组成的字符串。x 表示操作数，* 表示二元运算符。很容易看出，并非所有此类字符串都代表有效的 RPN 表达式。例如，“x*x”不是有效的 RPN 表达式，而“xx*”和“xxx**”是有效的表达式。将给定字符串转换为有效 RPN 表达式所需的最少插入、删除和替换操作数是多少？

输入：第一行包含测试用例 T 的数量。接下来是 T 测试用例。每个 case 都包含一个仅由字符 x 和 * 组成的字符串。

输出：输出 T 行，每个测试用例包含所需的最少操作数。

约束：1 <= T <= 100 输入字符串的长度最多为 100。

样本输入：

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

样本输出：

0
0
0
2
0

解释：

对于前三种情况，输入表达式已经是有效的RPN，所以答案是0。对于第四种情况，我们可以进行一次删除，一次插入操作：xx -> xx -> xx

4

4 回答 4

3

这是一个异常大的答案。如果还存在一个优雅的两班轮，我不会感到惊讶，但直到那一个被张贴在这里是我的。

假设您有一个简单的 2D 图，其中 x 轴表示解析步骤，y 轴表示当前 X 和星数之间的差异，n(x)-n(*)。例如，对于输入xx*xx**，图表将是这样的：

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

为了使表达式有效，此图在 y 轴上不得达到零或低于零，并且最后 y 的值必须为 1（堆栈上的单个值）。

为您提供了三个用于输入表达式的操作：插入、删除和替换。这个替换操作实际上是两者之一：用*替换x，用x替换*。当您在表达式中间的某处应用插入或删除时，图形会发生变化，以便从该点开始，图形中的所有点都会向上或向下移动。应用替换时，点会在图中向上或向下移动两个槽口。一个有趣的注意事项：我们不必处理删除操作，因为结果与应用相反的插入相同，不同之处在于插入可以始终应用，只有在有可用符号时才删除。

您的目标是找到最少数量的操作。如果我们只观察最终目标（y = 1），那么我们将确定我们必须移动图形并应用尽可能多的替换操作和一个额外的插入操作的缺口数。如果 N(x)-N(*) 的总和为 N，则操作数将为 floor((N-1)/2)。该符号确定要应用哪些操作。

问题是我们必须注意另一个条件，即图形永远不能达到零。为了确定这一点，我们必须首先对我们的表达式应用先前的操作。'Insert x' 添加在开头，'insert *' 出现在末尾，从开头搜索并用 x 替换每个 *，从结尾向后搜索并用 * 替换每个 x。

在这一步之后，我们有了新的表达方式。从头开始迭代并寻找 y=0 的地方。如果有这样的地方，那么你必须在它之前插入一个 x，并在表达式末尾插入一个 * 作为补偿。但请记住，您可能已经这样做了（在开头插入 x，或在结尾插入 *）。如果你有两个插入 x，那么假装它实际上是用 x 替换 *（少一个操作），而忘记必须插入 x。与一对插入 * 类似：删除两个插入 *，然后再应用一个“将 x 替换为 *”。您确实必须应用它，即更改表达式，因为如果从 end 搜索时找到的 x 实际上在您当前位置之前，那么您不能应用替换，因此不能将两个插入操作压缩为一个替换。

继续迭代直到结束，计算额外的操作，并且始终牢记您是否有一个插入 x 和一个插入 *。应该是这样的。最后，您将进行许多操作。

于 2012-04-04T16:31:10.540 回答
0

公共类 RPN {

public static boolean isValidRPN(String expr){

    char arr[] = expr.toCharArray();
    int x = 0;

    for(char c: arr){

        if ( c == 'x'){
            x++;
        }
        else if ( c == '*'){

            if ( x >= 2){
                x--;
            }
            else {
                return false;
            }
        }
    }

    if ( x == 1){
        return true;
    }

    return false;
}

//Think of RPN recursively as x(RPN)*
//The remaining code is self explanatory
private static int computeToRPN(String expr){

    int length = expr.length();

    if ( length == 1 ){
       if (expr.equals("x")){
           return 0;
       }
       else if ( expr.equals("*")){
           return 1;
       }
    }

    if ( length == 2){

        if ( expr.equals("xx") || expr.equals("*x") || expr.equals("x*")){
            return 1;
        }
        else if ( expr.equals("**")){
            return 2;
        }
    }

    char startChar = expr.charAt(0);
    char endChar = expr.charAt(expr.length()-1);

    if ( startChar == 'x' ){

        if ( endChar == 'x'){
            return 1 + compute2RPN(expr.substring(1,length-1));
        }
        else if ( endChar == '*'){
            return compute2RPN(expr.substring(1,length-1));
        }
    }

    return 2 + compute2RPN(expr.substring(1, length-1));


}

public static int compute2RPN(String expr){

    if ( isValidRPN(expr) ) return 0;
    else return computeToRPN(expr);

}

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    System.out.println(compute2RPN("xx*"));
    System.out.println(compute2RPN("xxx**"));
    System.out.println(compute2RPN("xxxx"));
    System.out.println(compute2RPN("*xx"));
    System.out.println(compute2RPN("xxxx*"));
    System.out.println(compute2RPN("**xx"));
    System.out.println(compute2RPN("xx*xx**"));

}

}

于 2013-10-21T04:59:41.240 回答
0

好吧，这显然是 SE/SWE/SDE 职位的在线代码测试/挑战问题之一。我个人不喜欢这种风格的问题，因为它们与您的编码/算法/设计能力无关，而是与您之前是否知道“技巧”有关。只要你知道'trick'，它就像helloworld.cpp 一样简单。

所以这里是诀窍：

从 Dialecticus 的帖子来看，有两点非常明显：

  1. 在任何时候，如果 X 的数量为 n，则最多应该有 (n-1) 个*s。
  2. * 的最终数量应完全等于 X 的数量减一。

因此，您的程序应该将无效字符串转换为满足这两个条件的字符串（我跳过了检查字符串是否有效的部分）。此外，应尽量减少转换次数。那么如何最小化呢？

以下是一些观察结果（假设字符串的长度大于 2，否则它是微不足道的）：

  1. 如果我们只想满足条件 2.，我们只需要替换几次加上最多一次插入。因为如果 n(X)>n(*)+1，则将 X 更改为 *，反之亦然。最后，如果字符串的长度是偶数，则只需再插入一个 X（或 *）。

  2. 如果同时您想满足标准 1.，您仍然只需要多次替换和一次插入，但位置很重要。我们进一步可以观察到，在字符串的开头用 X 替换 * 并在字符串的末尾用 * 替换 X 总是安全的。同样，很明显，对于一个有效的子串，我们可以将它表示为一个等价的 X。

从上面的观察，现在很清楚，这个问题可以很容易地通过动态规划来解决。

所以这个问题其实和你的算法/设计能力没有关系（其实因为规模很小，1<=T<=100，如果你愿意，你甚至可以通过蛮力解决）只要你知道你只能做更换，最多插入一次。

于 2015-02-15T21:07:08.040 回答
-1

导入 java.util.HashSet；导入 java.util.Set；导入 java.util.Stack；

导入 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 回答