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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。