編程實現 4 條重寫規則，有友好的接口。輸入任意字后，可生成（1）半法式和（2）法式，并且注明每一步應用了哪一個重寫規則。給出源程序和可以執行的程序。

/*** @author 康雨城* @time 2017/10/17* csdn : http://blog.csdn.net/kangyucheng* * 運行說明：在任何IDE中創建java Project，然后將創建class命名為Main，將本段代碼復制進去即可運行。*/ import java.util.ArrayList; import java.util.Scanner;public class Main {public static void main(String[] args) {// 輸入字wArrayList<Word> inputList=new ArrayList<Word>();//存儲輸入字ArrayList<Word> subNormalList=new ArrayList<Word>();//存儲半法式ArrayList<Word> normalList=new ArrayList<>();//存儲法式//輸入任意字inputList=getInputList();System.out.println("輸入數據為：");printList(inputList);System.out.println("其中每組數字第一個數字代表下標，第二個數字1代表正字母，-1代表負字母");//按照NF1的要求進行排序，得到半法式subNormalList=sort(inputList);System.out.println("半法式為：");printList(subNormalList);//刪除違規二元組得到法式normalList=subNormalToNormal(subNormalList);System.out.println("法式為：");printList(normalList);}private static ArrayList<Word> getInputList() {// 分為隨機輸入和手動輸入兩種ArrayList<Word> list=new ArrayList<Word>();Scanner input =new Scanner(System.in);System.out.println("需要手動輸入請按y或Y并按回車鍵,按任意鍵后并按回車鍵系統將為您自動輸入一組測試數據");char c=input.next().charAt(0);if(c=='Y'||c=='y'){System.out.println("請按以下格式輸入數據： a b 回車。（中間有空格）a為非負數，b為1或-1,當輸入0 0時，系統結束輸入");System.out.println("例如： \n3 1回車\n6 -1回車\n9 -1回車 \n8 -1回車 \n1 -1回車 \n0 0回車\n");System.out.println("或者按照以下格式輸入：3 1 6 -1 9 -1 8 -1 1 -1 2 1 0 0");System.out.println("其中每兩個數字一組，每組數字第一個數字代表下標，第二個數字1代表正字母，-1代表負字母");while(true){int inKey=input.nextInt();int inLetter=input.nextInt();if(inKey==0&&inLetter==0)break;list.add(new Word(inKey,inLetter));}}else{//以下數字可計算題目中的（2） // list.add(new Word(5,-1)); // list.add(new Word(3,1)); // list.add(new Word(7,1)); // list.add(new Word(9,-1)); // list.add(new Word(4,-1));//以下數字可計算題目中的（3） // list.add(new Word(3,-1)); // list.add(new Word(2,1)); // list.add(new Word(7,1)); // list.add(new Word(9,-1)); // list.add(new Word(4,-1)); // list.add(new Word(1,-1));//以下數字可計算題目中的(4) // list.add(new Word(0,1)); // list.add(new Word(5,-1)); // list.add(new Word(3,1)); // list.add(new Word(7,1)); // list.add(new Word(11,1)); // list.add(new Word(9,-1)); // list.add(new Word(4,-1)); // list.add(new Word(0,-1)); // list.add(new Word(0,-1)); // list.add(new Word(0,-1)); // list.add(new Word(0,-1));//以下式子可以實現消除最大違規二元組list.add(new Word(7,1));list.add(new Word(9,1));list.add(new Word(4,-1));list.add(new Word(1,-1));list.add(new Word(10,-1));list.add(new Word(11,1));list.add(new Word(13,1));list.add(new Word(7,-1));list.add(new Word(1,-1));list.add(new Word(15,-1));//以下獅子可以是反證（4）的例子 // list.add(new Word(0,1)); // list.add(new Word(3,-1)); // list.add(new Word(0,1)); // list.add(new Word(2,1)); // list.add(new Word(5,1)); // list.add(new Word(4,-1)); // list.add(new Word(3,-1));}input.close();return list;}private static ArrayList<Word> sort(ArrayList<Word> list) {// 冒泡排序的方法寫成半法式int length=list.size();for(int i=0;i<length;i++){for(int j=0;j<length-i-1;j++){Word word1=list.get(j);Word word2=list.get(j+1);int key1=word1.getKey();int key2=word2.getKey();if(word1.getLetter()==Word.POSITIVE&&word2.getLetter()==Word.NEGETIVE){//正字母在左，負字母在右，不交換位置}else if(word1.getLetter()==Word.NEGETIVE&&word2.getLetter()==Word.POSITIVE){//負字母在左，正字母在右，只有左側下標小于右側下標的情況需要交換位置if(word1.getKey()<word2.getKey()){//負字母在左，且負字母下標較小 滿足i<k條件 應用R3list.get(j).setKey(key2+1);list.get(j).setLetter(Word.POSITIVE);list.get(j+1).setKey(key1);list.get(j+1).setLetter(Word.NEGETIVE);System.out.print("應用一次R3，得到：");printList(list);}else{//負字母在左，且負字母下標較大 應用 R2list.get(j).setKey(key2);list.get(j).setLetter(Word.POSITIVE);list.get(j+1).setKey(key1+1);list.get(j+1).setLetter(Word.NEGETIVE);System.out.print("應用一次R2，得到：");printList(list);}}else if(word1.getLetter()==Word.POSITIVE&&word2.getLetter()==Word.POSITIVE){//兩個字母都是正字母的情況，只有左側下標大于右側下標的情況需要交換位置if(word1.getKey()>word2.getKey()){list.get(j).setKey(key2);list.get(j+1).setKey(key1+1);System.out.print("應用一次R1，得到：");printList(list);}}else{//兩個字母都是負字母的情況，只有左側下標小于右側下標的情況需要交換位置if(word1.getKey()<word2.getKey()){list.get(j).setKey(key2+1);list.get(j+1).setKey(key1);System.out.print("應用一次R4，得到：");printList(list);}}}}return list;}private static ArrayList<Word> subNormalToNormal(ArrayList<Word> list) {//通過刪除違規二元組，將半法式轉化為法式int maxKeyIndex=getMaxKeyIndex(list);int left=maxKeyIndex,right=maxKeyIndex+1;while(left>=0&&right<list.size()){int pkey=list.get(left).getKey();int rkey=list.get(right).getKey();if(pkey<rkey){right++;}else if(pkey>rkey){left--;}else{int nextPkey=list.get(left+1).getKey();int nextRkey=list.get(right-1).getKey();if((nextPkey!=pkey+1)&&(nextRkey!=rkey+1)){//已找到最大違規二元組，開始消除System.out.println("找到最大違規二元組：("+pkey+",1) 和 ("+rkey+",-1)");int cr1=0,cr4=0;if(left+1!=right){//違規二元組中間有字母，與中間字母進行交換for(int l=left+1;l<=maxKeyIndex;l++){list.get(l).keyMul();//System.out.print("應用一次R1,得到：");printList(list);cr1++;}for(int r=right-1;r>maxKeyIndex;r--){list.get(r).keyMul();//System.out.print("應用一次R4,得到：");printList(list);cr4++;}}//刪除字母，并修改左右指針。list.remove(list.get(left));left--;right--;list.remove(list.get(right));System.out.print("應用"+cr1+"次R1,應用"+cr4+"次R4，應用一次R5，刪除了最大違規二元組,得到：");printList(list);}}}return list;}private static int getMaxKeyIndex(ArrayList<Word> list) {//獲取正字母中下標最大的元素，因為已經是排列完成的半法式，//所以，只需要找到兩個正字母和負字母的交界即可int i=0;for(int j=0;j<list.size();j++){if(list.get(j).getLetter()==1&&list.get(j+1).getLetter()==-1){i=j;break;}}return i;}private static void printList(ArrayList<Word> list) {//打印數組for(int i=0;i<list.size();i++){System.out.print(list.get(i).getKey()+" "+list.get(i).getLetter() +" ");}System.out.println();}}class Word{public static int POSITIVE=1;//正字母public static int NEGETIVE=-1;//負字母private int key;//下標private int letter;//正負字母標識public Word(int key, int letter) {this.key = key;this.letter = letter;}public Word() {}public int getKey() {return key;}public void setKey(int key) {this.key = key;}public int getLetter() {return letter;}public void setLetter(int letter) {this.letter = letter;}public void keyMul() {this.key--;} }

總結

以上是生活随笔為你收集整理的编程实现 4 条重写规则,可生成半法式和法式的全部內容，希望文章能夠幫你解決所遇到的問題。

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