美国某大学教授出的招生考试题 --Java

18号 发布于 2013/08/08 20:24
阅读 1K+
收藏 1

这是美国某大学的教授给中国留学生出的考试题。还望各位大神来讨论讨论,解答解答! 

GrammarMain.java

// Stuart Reges
// 3/10/04
//
// GrammarMain contains a main program that prompts a user for the name of a
// grammar file and then gives the user the opportunity to generate random
// versions of various elements of the grammar.

import java.io.*;
import java.util.*;

public class GrammarMain {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner console = new Scanner(System.in);
        System.out.println("Welcome to the cse143 random sentence generator.");
        System.out.println();

        // open grammar file
        System.out.print("What is the name of the grammar file? ");
        String fileName = console.nextLine();
        Scanner input = new Scanner(new File(fileName));

        // read the grammar file and construct the grammar solver
        List<String> grammar = new ArrayList<String>();
        while (input.hasNextLine()) {
            String next = input.nextLine().trim();
            if (next.length() > 0)
                grammar.add(next);
        }
        GrammarSolver solver = 
            new GrammarSolver(Collections.unmodifiableList(grammar));

        showResults(console, solver);
    }

    // pre : console open for console reading, solver initialized
    // post: allows the user to repeatedly pick a grammar element to generate
    public static void showResults(Scanner console, GrammarSolver solver) {
        boolean done = false;
        while (!done) {
            System.out.println();
            System.out.println("Available symbols to generate are:");
            System.out.println(solver.getSymbols());
            System.out.print("What do you want generated (return to quit)? ");
            String target = console.nextLine();
            if (target.length() == 0) {
                done = true;
            } else if (!solver.contains(target))
                System.out.println("Illegal symbol");
            else {
                System.out.print("How many do you want me to generate? ");
                if (!console.hasNextInt())
                    System.out.println("that's not an integer");
                else {
                    int number = console.nextInt();
                    if (number < 0)
                        System.out.println("no negatives allowed");
                    else {
                        String[] answers = solver.generate(target, number);
                        for (int i = 0; i < number; i++)
                            System.out.println(answers[i]);
                    }
                }
                console.nextLine();  // to position to next line
            }
        }
    }
}

sentence.txt这个是数据文件


<s>::=<np> <vp>
<np>::=<dp> <adjp> <n>|<pn>
<pn>::=John|Jane|Sally|Spot|Fred|Elmo
<adjp>::=<adj>|<adj> <adjp>
<adj>::=big|fat|green|wonderful|faulty|subliminal|pretentious
<dp>::=the|a
<n>::=dog|cat|man|university|father|mother|child|television
<vp>::=<tv> <np>|<iv>
<tv>::=hit|honored|kissed|helped
<iv>::=died|collapsed|laughed|wept


以上就是题目,我们需要做的就是实现上面出现的这些方法

以下是问题补充:

@18号:http://pan.baidu.com/share/link?shareid=2988614700&uk=640470395 这里有所有文件,解答后还望分享分享,谢谢! (2013/08/08 20:42)
加载中
1
明月照大江
明月照大江
这感情是找人写作业呢~
我是一名程序员
我是一名程序员
貌似楼主是那中国留学生中的一员~
0
番茄12
番茄12
但确实学生的质量就是不一样
0
铂金上帝
铂金上帝

这个很有意思啊。把散乱的单词通过符合语法的逻辑组合成一句话。

Google了一下貌似是华盛顿大学的

铂金上帝
铂金上帝
回复 @JavaCode : http://www.cs.washington.edu/education/courses/cse143/13su/homework.shtml#a6 的Homework 4 (GrammarSolver)多关注关注
18号
18号
好像是,我也google了一下
0
Jeky
Jeky

说复杂点是需要形式语言知识,简单点的话就是根据产生式形成最终的句子,就是一棵树。

睡前写了一下,不保证没bug,凑合看个意思吧。

import java.util.*;

/**
 *
 * @author jeky
 */
public class GrammarSolver {

    private Map<String, String[]> productions;

    public GrammarSolver(List<String> grammar) {
        productions = new HashMap<>();

        for (String g : grammar) {
            String[] split = g.split("::=");
            String symbol = split[0].trim();
            String[] candidates = split[1].split("\\s*\\|\\s*");
            productions.put(symbol, candidates);
        }
    }

    public String getSymbols() {
        return productions.keySet().toString();
    }

    public boolean contains(String target) {
        return productions.containsKey(target);
    }

    public String[] generate(String target, int number) {
        String[] result = new String[number];
        for (int i = 0; i < number; i++) {
            List<String> originSymbols = new LinkedList(Arrays.asList(target.split("\\s+")));
            result[i] = recursiveGenerate(originSymbols);
        }

        return result;
    }

    private String recursiveGenerate(List<String> symbols) {
        int removeIndex = -1;
        for (int i = 0; i < symbols.size(); i++) {
            if (productions.containsKey(symbols.get(i))) {
                removeIndex = i;
                break;
            }
        }
        if (removeIndex != -1) {
            // replace symbol with production result
            symbols.remove(removeIndex);
            
            String[] candidates = productions.get(symbols.get(removeIndex));
            String c = candidates[random.nextInt(candidates.length)];

            String[] split = c.split("\\s+");
            for (int j = 0; j < split.length; j++) {
                symbols.add(j + removeIndex, split[j]);
            }

            return recursiveGenerate(symbols);
        } else {
            return join(symbols);
        }
    }

    private String join(List<String> symbols) {
        StringBuilder builder = new StringBuilder();
        for (String s : symbols) {
            builder.append(s).append(" ");
        }
        return builder.toString();
    }
    private static final Random random = new Random();
}
18号
18号
感谢!
0
无奈的钝刀
无奈的钝刀
可以参考一下flex和bison
0
newzai
newzai
BNF了,用SCALA的 Parser模块,非常简单的哦.scala也是java虚拟机上的语言哦.帮个小时搞定 
0
专业打酱油
专业打酱油
智商是硬伤,伤不起啊
返回顶部
顶部