Reverse Polish Notation

本文主要是介绍Reverse Polish Notation，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://www.1point3acres.com/bbs/thread-31595-1-1.html

定义一种叫做“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

应该用动态规划做，但是思路还不是很清晰，有空再研究下

递归：

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

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

动态规划

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

我的代码，参考：http://www.careercup.com/question?id=13216725

#include <iostream>
#include <stack>
#include <stdio.h>
#include <string>using namespace std;void minOp(stack<char> &stk, const char *s, int currNum, int &best) {if (stk.size() == 1 && *s == '\0') {if (currNum < best)best = currNum;return;}if (*s == '\0') {if (stk.size() >= 2) {//rm x; or add *stk.pop();minOp(stk, s, currNum + 1, best);stk.push('x');}else {//stk.size() == 0stk.push('x');minOp(stk, s, currNum + 1, best);stk.pop();}}else if (*s == '*'){if (stk.size() < 2) {//rm *minOp(stk, s + 1, currNum + 1, best);//*->xstk.push('x');minOp(stk, s + 1, currNum + 1, best);stk.pop();}else {stk.pop();minOp(stk, s + 1, currNum, best);stk.push('x');}}else {if (stk.size() >= 2) {//x->*stk.pop();minOp(stk, s + 1, currNum + 1, best);stk.push('x');//add *stk.pop();minOp(stk, s, currNum + 1, best);stk.push('x');}//rm xminOp(stk, s + 1, currNum + 1, best);//in stack        stk.push('x');minOp(stk, s + 1, currNum, best);stk.pop();}
}int minRPN (const char *s) {int xNum = 0;int nOfDel = 0;//del *int nOfAdd = 0;//add *int nOfRpl = 0;//*->x | x->*while (*s) {if (*s == 'x') {++xNum;}else {if (xNum == 0) {if (nOfDel >=2) {//如果直接 del *，则又增加了一个操作nOfDel -= 2;nOfRpl += 2;++xNum;}else {++nOfDel;//还可以将*变为x。但是之后有操作，再将del操作替换为replace操作}}else if(xNum == 1) {if (nOfDel >0) {--nOfDel;++nOfRpl;}else {++nOfDel;}}else {--xNum;}}++s;}while(xNum > 1) {if (xNum >= 3) {++nOfRpl;xNum -= 2;}else {++nOfAdd;--xNum;}}return (nOfAdd + nOfDel + nOfRpl);
}int main() {string ss[] = {"*","**","***","****","xx*xx**x","xxxxx","***x*"};for (int i = 0; i < 7; ++i) {stack<char> stk;int best = INT_MAX;minOp(stk, ss[i].c_str(), 0, best);cout << best <<":"<<minRPN(ss[i].c_str())<<endl;}return 0;
}

这篇关于Reverse Polish Notation的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---