Nur für Profis: Programmieraufgabe von meinem Prof

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Nur für Profis: Programmieraufgabe von meinem Prof

    Hallo zusammen,

    ich bin neue hier. Studiere im zweiten Semester Informatik und habe eine Hausarbeit im Bereich Logik von meinem Prof bekommen, die mir zu schaffen macht.

    Hier mal die Aufgabenstellung:

    ####

    -Textvarianten-
    Ein Text soll verschiedene Textvarianten beinhalen. Dazu gibt es die Steuerzeichen "[", "]" und das Trennzeichen "|".
    Diese Steuerzeichen im Text sollen wie Folgt interpretiert werden: Klammern bieten immer Optionen an, von denen später genau ein Element ausgewählt werden soll.

    Quellcode

    1. var bsp = "A B C [D|E]"; // Soll entweder A B C D ODER A B C E ausgeben!


    a) Geben Sie einen Algorithmus mit der Programmiersprache Ihrer Wahl an, der den eingegebenen String so ausgibt, dass dieser mit BELIEBIGER VERSCHACHTELUNG der Klammern funktioniert. Speichern Sie dazu das Ergebnis in einer Arraystruktur Ihrer Wahl zwischen.
    b) Zählen Sie die maximal möglichen Varianten
    c) Geben Sie eine zufällige Variante aus

    Weiteres Beispiel einer Eingabe:

    Quellcode

    1. var bsp = "A B C [D|E|F G H [I J |K ]|]";


    ####

    Könnt Ihr mir da helfen und mir den Algorithmus in Pseudocode, PHP oder Java posten?
    Das Problem habe ich mit der Verschachtelung... F G H [I J |K ] heißt ja im oberen Beispiel das F G H mit einer Variante I J O ODER K verknüpft wird. Diese & Verknüpfung kann ich aber in einer Arraystruktur nicht wirklich sichtbar machen.

    Wie gesagt, ist was für Profis... Ich hoffe ich finde hier Hilfe..

    Merci!

    Beste Grüße, Andre

  • Ich hätte es so gemacht, dass alle Möglichkeiten erstellt werden und diese einfach in einem Array gespeichert werden.
    Also "A [B | C] D" wird zu {"A B D", "A C D"}.
    Eine andere Arraystruktur fällt mir dazu nicht ein, interessant wären dann erst wieder Bäume oder Graphen.

    (Wenn die Arraystruktor so passend ist, kann ich mehr gerne Code überlegen :))

  • Hi,
    ja an die Möglichkeit alle Ergebnisse direkt in ein Array zu packen habe ich auch schon gedacht. Habe ich aber verworfen, weil dies extrem effizient ist. Folgendes Beispiel sind alleine 20 Varianten: "[A|B][C|D][E|F|G|H|I]"

    Die Idee mit Bäume oder Graphen ist mir noch nicht gekommen.
    Wie würdet du das mit einem Baum machen? Freue mich da sehr über Code!
    Merci!

    Andre

  • Quellcode

    1. // remove all spaces before !
    2. def parse(root: Node, text: String)
    3. if text.length == 0 then return
    4. if text[0] == '[' then
    5. val poss = text.substring(1).split(']')[0].split('|') // just getting all the possibilities
    6. foreach pos in poss
    7. parse(root, text.replaceFirst('[.*]', pos))
    8. else
    9. val newRoot = root.addNode(text[0])
    10. parse(newRoot, text.substring(1))


    Die Funktion setzt einen mutable Tree voraus (Könnte man aber sicherlich auch für immutable collections umschreiben).
    Keine Ahnung ob das so funktioniert, aber ich denke, dass es von der Idee schon funktionieren sollte.

  • Hey MrSpider,

    ich habe deinen Pseudocode mal mit PHP ausprobiert. Da funktioniert aber einiges nicht. Vielleicht habe ich da deinen Pseudocode an manchen Stellen nicht richtig interpretiert.
    Hier ist mal mein Beispiel:

    Quellcode

    1. function createvariants($root, $text){
    2. $string = trim($text);
    3. $pattern = '/[[|]/';
    5. if (strlen($string) == 0 ) return $root;
    6. if ($string[0] == '['){
    7. $poss = preg_split( $pattern, substr($string, 1) );
    8. foreach ($poss as $value){
    9. $root = createvariants($root, $value);
    10. }
    11. }
    12. else{
    13. $root = createvariants($string[0], substr($string, 1));
    14. }
    16. return $root;
    17. }
    Alles anzeigen


    Besten Dank für die Hilfe :)

  • Ich hab das ganze mal in Java geschrieben. Sind vermutlich noch ein paar kleine Fehler drin. Außerdem ist der Code nicht so schön .... (eher "quick & dirty")

    Quellcode

    1. import java.util.Collections;
    2. import java.util.LinkedList;
    5. public class LogicParser {
    7. private static class Node<T> {
    8. private T data;
    9. private LinkedList<Node<T>> children;
    11. public Node(T data) {
    12. this.data = data;
    13. children = new LinkedList<LogicParser.Node<T>>();
    14. }
    16. public Node<T> addNode(T data) {
    17. return addNode(new Node<T>(data));
    18. }
    20. public Node<T> addNode(Node<T> node) {
    21. children.add(node);
    22. return node;
    23. }
    25. public LinkedList<LinkedList<T>> getAll(){
    26. LinkedList<LinkedList<T>> result = new LinkedList<LinkedList<T>>();
    27. for(Node<T> node : children){
    28. LinkedList<LinkedList<T>> list = node.getAll();
    29. for(LinkedList<T> listInner : list){
    30. listInner.addFirst(data);
    31. }
    32. result.addAll(list);
    33. }
    34. if(children.size() == 0){
    35. LinkedList<T> add = new LinkedList<T>();
    36. add.add(data);
    37. result.add(add);
    38. }
    39. return result;
    40. }
    42. @Override
    43. public String toString() {
    44. StringBuilder result = new StringBuilder();
    45. result.append(data).append("\n");
    46. for(Node<T> node : children){
    47. result.append(node.toString().replace("\n", "\n\t"));
    48. }
    49. return result.toString();
    50. }
    51. }
    53. private static int getClosingBracket(String text){
    54. int result = 0, i = text.indexOf('[') + 1, bracketCount = 0;
    55. while(result == 0 && i < text.length()){
    56. if(text.charAt(i) == '[') ++bracketCount;
    57. else if(text.charAt(i) == ']' && bracketCount == 0) result = i;
    58. else if(text.charAt(i) == ']') --bracketCount;
    59. ++i;
    60. }
    61. return result;
    62. }
    64. private static String[] getPoss(String text) {
    65. if (text.charAt(0) != '[' || text.charAt(text.length()-1) != ']')
    66. return null;
    67. LinkedList<String> result = new LinkedList<String>();
    68. String currentText = text.substring(1);
    69. while (currentText.length() > 1) {
    70. int nextBracketO = currentText.indexOf('[');
    71. int nextBracketC = currentText.indexOf(']');
    72. int nextOpt = currentText.indexOf('|');
    73. if ((nextOpt < nextBracketO || nextBracketO == -1) && nextOpt != -1) {
    74. result.add(currentText.substring(0, nextOpt));
    75. currentText = currentText.substring(nextOpt + 1);
    76. } else if(nextBracketO != -1 && nextBracketC != -1) {
    77. result.add(currentText.substring(0, nextBracketC + 1));
    78. currentText = currentText.substring(nextBracketC + 1);
    79. } else if(nextBracketC == currentText.length() - 1){
    80. result.add(currentText.substring(0, currentText.length() - 1));
    81. currentText = "";
    82. }
    83. }
    84. return result.toArray(new String[result.size()]);
    85. }
    88. public static void parse(Node<String> node, String text){
    89. if(text.length() == 0) return;
    90. if(text.charAt(0) == '['){
    91. int split = getClosingBracket(text);
    92. String[] poss = getPoss(text.substring(0, split + 1));
    93. for(String pos : poss){
    94. parse(node, pos + text.substring(split + 1));
    95. }
    96. }
    97. else {
    98. int start = (text.indexOf('[') == -1) ? text.length() : text.indexOf('[');
    99. parse(node.addNode(text.substring(0, start)), text.substring(start));
    100. }
    101. }
    103. public static void main(String[] args) {
    104. Node<String> root = new Node<String>("");
    105. parse(root, "ABC[D|E|FGH|B[IJ|K]]XYZ");
    106. for(LinkedList<String> list : root.getAll()){
    107. list.removeFirst();
    108. System.out.println(list);
    109. }
    110. }
    111. }
    Alles anzeigen


    Ausgabe

    Quellcode

    1. [ABC, DXYZ]
    2. [ABC, EXYZ]
    3. [ABC, FGHXYZ]
    4. [ABC, B, IJXYZ]
    5. [ABC, B, KXYZ]