[FACEBOOK] Reverse Polish Notation

champoier

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

定义一种叫做“Reverse Polish Notation”的表达式：

3 + (4 * 5)

可以写成

3 4 5 * +

即运算符号写在数字的后面。

现在规定，x代表数字，*代表运算符。给定一个包含有x和*的string，问最少需要多少次操作（操作包括，添加一个字符，删除一个字符，替代一个字符）可以使一个string符合Reverse Polish Notation的表达方式。

Input:
第一行：数字n，代表有n组数据
第2~n+1行：一个包含有x和*的string

Output:
输出一个数字，代表最少需要多少次操作，string可以符合Reverse Polish Notation的表达方式

Sample Input:
5
x
xx*
xxx**
*xx
xx*xx**

Sample Output:
0
0
0
2
0

secretgu

本帖最后由 secretgu 于 2012-4-17 12:34 编辑

废了老大劲= =开始对 **** 这样的输入考虑有误。。。

没有像题目要求的input那样，只让用户输入一个字符串，不过这本来也不是这题的本质，所以感觉没太大关系
时间复杂度O(N)空间复杂度O(1)

求review code，设计test case，有发现代码问题或test case不通过请跟帖指出，谢谢~

#include <iostream>
using namespace std;
int *s, count;
string str;
void swap(int i, int j) {
int tmp = s[i];
s[i] = s[j];
s[j] = tmp;
}
int main() {
// init
cout << "input an expression: ";
cin >> str;
s = new int[str.size()];
int i, countx = 0;
for (i = 0; i < str.size(); ++i)
s[i] = i;
int j = str.size() - 1; // points to last 'x'
while (j >= 0 && str[j] == '*')
j--;
for (i = 0; i < str.size(); ++i) {
if (str[i] == '*') {
if (i - 1 >= 0 && s[i - 1] - 1 >= 0) {
// there are two x' waited to be reduced
s[i] = s[s[i - 1] - 1];
} else {
if (i < j) {
swap(i, j--);
count += 2; // swap char makes count += 2
while (j >= 0 && str[j] == '*')
j--;
} else
break;
}
} else
countx++;
}
int bk_x = countx, bk_s = str.size() - countx;
if (bk_x > bk_s) {
while (bk_x - bk_s > 1) {
// replace one x with one *
bk_x--;
bk_s++;
count++;
}
} else {
while (bk_s - bk_x > 0) {
// replace one * with one x
bk_s--;
bk_x++;
count++;
}
if (bk_s == bk_x)
count++; // delete one *
}
cout << "count: " << count << endl;
return 0;
}

复制代码

eastflag

本帖最后由 eastflag 于 2012-4-17 19:10 编辑

动态规划递归实现。每个xx*运算产生x，设计数器num，指针从字符串开头开始查找，如果找到第一个*，作如下处理：
1、若该*前面有2个（或以上）x，删去这两个x和*，首端增加一个x，递归余下字符串；
2、若该*前面只有1个x，num++
1）对应操作：加一个x或删去*，，递归除去*余下部分；
2）对应操作：替换*为x，递归替换后余下部分；
3、若该*前面没有x，num++
1）对应操作：删去*，递归余下部分；
2）对应操作：替换*为x，递归替换后余下部分；

如果没有找到而字符串长度>1，num++，加上一个*，递归余下字符串。

代码如下（java）（如何对齐啊。。。）：

public class RPN{
public static void main(String[] args){
String[] testCases = {
new String("x"),
new String("xx"),
new String("***"),
new String("xxx"),
new String("xxx***"),
new String("***xxx"),
new String("x*xx*"),
new String("*xx*x"),
};
for (String testCase : testCases){
//TODO check input legal
System.out.println(new RPN().operate(testCase));
}
}
private int operate(String tc){
if (tc.equals("x")) {
return 0;
}else if (tc.equals("") || tc.equals("*")){
return 1;
}
int pos = tc.indexOf('*');
if (pos < 0) {
return min (operate(tc.substring(1)),
operate(tc.substring(2))) + 1;
}else if (pos == 0){
return min(operate(tc.substring(pos + 1)), //delete *
operate('x' + tc.substring(pos + 1)) //replace * with x
) + 1;
}else if (pos == 1){
return min(operate('x' + tc.substring(pos + 1)), //add x or delete *
operate("xx" + tc.substring(pos + 1)) //replace * with x
) + 1;
}else{
return operate(tc.substring(0, pos - 1) + tc.substring(pos + 1));
}
}
private static int min(int ...a){
int m = a[0];
for (int k : a){
if (k < m) {
m = k;
}
}
return m;
}
}

复制代码

eastflag

回复 2# secretgu

你的代码里面count没有定义，是不是和countx是一个变量？

secretgu

回复 4# eastflag

第5行，全局变量

eastflag

回复 5# secretgu

哦，你count需要设一下初值0，另外不知道为什么我的dev C++里面你的全局的count不能用，提示没有定义。。。

关于testCase，你测试一下，样例*x 输出应该是1，你输出3，类似的*xxx你输出了3，这些好像都有问题。

secretgu

回复 6# eastflag

我用gcc编译运行的，全局变量自动赋值为0，是可以用的

恩，我回头看看，总算有人帮看code了- -。。。谢了- -

zlxwd

本帖最后由 zlxwd 于 2012-4-17 17:47 编辑

动态规划，时间复杂度为O(N^2)，空间复杂度为O(N^2)

import java.util.*;
import java.math.*;
public class Main {
private static void set(int[][] dp, int i, int j, int val) {
if (dp[i][j] == -1) {
dp[i][j] = val;
}
else {
dp[i][j] = Math.min(dp[i][j], val);
}
}
public static void main(String[] args) throws Exception {
Scanner scan = new Scanner(System.in);
int taskCount = scan.nextInt();
scan.nextLine();
for (int taskIndex = 0; taskIndex < taskCount; taskIndex++) {
char[] arr = scan.nextLine().toCharArray();
if (arr.length == 0) {
System.out.println("Input string cannot be empty");
continue;
}
else if (arr.length == 1) {
System.out.println(arr[0] == '*' ? 1 : 0);
continue;
}
int[][] dp = new int[arr.length][arr.length];
for (int i = 0; i < dp.length; i++) {
Arrays.fill(dp[i], -1);
}
if (arr[0] == 'x') {
dp[0][0] = 0;
}
else {
dp[0][0] = 1;
}
for (int i = 1; i < arr.length; i++) {
if (arr[i] == 'x') {
set(dp, i, 1, dp[i - 1][0]);
set(dp, i, 0, dp[i - 1][0] + 1);
}
else {
set(dp, i, 1, dp[i - 1][0] + 1);
set(dp, i, 0, dp[i - 1][0] + 1);
}
for (int j = 1; j < arr.length; j++) {
if (dp[i - 1][j] == -1) {
continue;
}
if (arr[i] == 'x') {
set(dp, i, j + 1, dp[i - 1][j]);
set(dp, i, j, dp[i - 1][j] + 1);
set(dp, i, j - 1, dp[i - 1][j] + 1);
}
else {
set(dp, i, j + 1, dp[i - 1][j] + 1);
set(dp, i, j, dp[i - 1][j] + 1);
set(dp, i, j - 1, dp[i - 1][j]);
}
}
}
int result = arr.length;
for (int i = 0; i < arr.length; i++) {
if (dp[dp.length - 1][i] == -1) {
continue;
}
result = Math.min(result, dp[dp.length - 1][i] + i);
}
System.out.println(result);
}
}
}

复制代码

gboystal

zlxwd 发表于 2012-4-17 17:41
动态规划，时间复杂度为O(N^2)，空间复杂度为O(N^2)

请教一下你代码里面的dp[i][j]表示的是什么意义？
另外，感觉@eastflag的做法有点像递归搜索呢。。

[FACEBOOK] Reverse Polish Notation

注册一亩三分地论坛，查看更多干货！

相关帖子

浏览过的版块