Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
In einer fiktiven Programmiersprache gibt es arithmetische Ausdrücke wie in der Mathematik, z.B. 2 + 3. Zur Vereinfachung gibt es nur „Fully Parenthesized Expressions“ (FPE), d.h. dass jeder Operator mit seinen beiden Operanden geklammert ist. Priorität und Assoziativität sind hier irrelevant. Numerale sind zur Vereinfachung nur einzelne Dezimalziffern ohne Vorzeichen.
Korrekte FPEs sind z.B. (2 + ( 3 * 4)) oder ((2 + 3 ) * 4)
Unzulässige FPEs wären: 2 + 3 * 5 oder (2+ ) * 5 oder )(
Ihre Aufgabe ist es, einen als String gegebenen Ausdruck auf syntaktische Korrektheit hin zu untersuchen, d.h. Sie müssen zuerst überprüfen, ob die Klammern im String korrekt geschachtelt sind. Ihre Methode liefert entsprechend true oder false.
Auf den ersten Blick sieht das garnicht so schwer aus, aber wenn man sichs dann mal genauer überlegt.. Um 100%ige Korrektheit zu überprüfen muss man schon einiges beachten. Zunächst hab ich gedacht "Regexp und gut is!" aber stellt sich heraus das ein Regex für so eine Syntax überprüfung garnicht so leicht ist.
Also gehn wirs mal langsam an, hier meine erste Methode:
Code:
public boolean isBalanced(String fpe) {
char[] chars = fpe.toCharArray();
int opened = 0, closed = 0;
for(char c : chars) {
if(c == '(')
opened++;
if(c == ')')
closed++;
}
return opened > 0 && opened == closed;
}
Was die macht is klar, einfach nur sehen ob genau so viele offene Klammern '(' wie geschlossene Klammern ')' in der FPE sind. Auch muss mindestens eine Klammer offen (dh. auch geschlossen) sein, da '5 + 2' keine FPE ist.
Nur wie überprüfe ich die restliche syntaktische Korrektheit?
Nach jeder offenen Klammer muss ja entweder eine Zahl mit Operator oder eben eine neue FPE kommen.
Jede Hilfe für (möglichst) schlaue Lösungsansätze ist willkommen!
MfG
EDIT:
Ich vermute stark das die Aufgabe auf eine Rekursion hinausläuft.
Mhh ich denke nicht das meine isBalanced() falsch ist, die Methode ansich soll ja nur sehen ob es
a) exakt soviele '(' wie ')' gibt und
b) mindestens eine '(' bzw ')' gibt
Deine Methode macht doch eigentlich das gleiche, nur das du die "Klammerntiefe" bei '(' hochzählst und bei ')' runterzählst.
Hab gerade beide getestet und sehe da keinen Unterschied. Das eigentliche Problem, ob die Klammern (Ausdrücke) korrekt geschachtelt sind muss man natürlich anders lösen (ich vermute mit einer Rekursion).
@sh: die aufgabe hatte ich auch mal so ähnlich. eine einfache lösung war die indizes der öffnenden (is) und schließenden klammern (ie) zu suchen. wenn weder is noch ie da sind, balanced. wenn nur einer der indizes existiert, unbalanced. wenn beide indizes existieren, rekursion mit dem substring von is+1 bis ie .
die methode prüft natuerlich nur die klammern, nicht jedoch die operatoren oder operanden.
EDIT: habs gefunden
Java:
public static boolean isBalanced (String t) {
int s = t.indexOf('(');
int e = t.lastIndexOf(')');
if ((s == -1) && (e == -1))
return true;
else if ((s == -1) || (e == -1) || (s >= e))
return false;
else
return isBalanced(t.substring(s+1, e));
}
Ich denke ich weiss nun wie es geht. In der Teilaufgabe c) (ja die habe ich euch verschwiegen, hab ich grad aus den Tiefen meines Ordners hervorgekramt) ist eine Zustandstabelle. Einfach dumm nach der Tabelle programmieren sollte klappen. Mein zweiter Lösungsansatz war eh schon relativ ähnlich.
Code:
package aufgabe1;
public class FPE {
public static void main(String... args) {
}
private enum State {
OpenBracket, Digit, Operator, CloseBracket, Eof, Undefined
}
private boolean isCorrectSyntax(String fpe) {
CHECK check = new CHECK(fpe);
//...... do the check stuff here
}
private static class CHECK {
private char[] fpe;
private int pos;
public CHECK(String fpe) {
this.fpe = fpe.toCharArray();
pos = -1;
}
public State nextState() {
pos++;
if(fpe.length - 1 < pos)
return State.Eof;
if(fpe[pos] == ' ')
return nextState();
if(fpe[pos] == '(')
return State.OpenBracket;
if(fpe[pos] == ')')
return State.CloseBracket;
if(Character.isDigit(fpe[pos]))
return State.Digit;
if(fpe[pos] == '+' || fpe[pos] == '*')
return State.Operator;
return State.Undefined;
}
}
}
Das Mal grob wie ichs angegangen bin, hier noch wie der Automat dazu aussieht:
EDIT:
Okay, ich komm mit der Zustandstabelle schon nicht klar. Wieso kann im Zustand "Plain" ein Operator kommen (1. Zeile, letzte Spalte).
Also im Zustand "Plain" wird eine OpenBracket erkannt. Ist noch nachvollziehbar, das erste Zeichen muss ja '(' sein. Nur wieso geht man, wenn im Zustand "Plain" ein Operator kommt dann zu Numeral1?
Ich mein, dann wär ja zB. ein + oder * am ANFANG der FPE?
Bzw. weiß jemand wie das Ding korrekt auszufüllen ist?
EDIT2:
Stimmt das so?
EDIT3:
Hier mal meine Lösung nach obiger Zustandstabelle, könnte mir bitte jemand sagen ob das so richtig ist?
Code:
package aufgabe1;
public class FPESyntax {
public static void main(String... args) {
String fpe = "((1+2)*(3+4))";
System.out.println(isCorrectSyntax(fpe));
}
private static boolean isCorrectSyntax(String fpe) {
//eventuell noch whitespaces strippen
char[] chars = fpe.toCharArray();
int depth = 0;
State state = State.Plain;
for(int i = 0; i < chars.length; i++) {
if(state == State.Plain) {
if(chars[i] == '(') {
depth++;
state = State.OpenBracket;
}
else if(chars[i] == '+' || chars[i] == '*') {
state = State.Numeral1;
}
else if(chars[i] == ')' || Character.isDigit(chars[i])) {
return false;
}
}
else if(state == State.OpenBracket) {
if(isOpenBracket(chars[i])) {
depth++;
state = State.OpenBracket;
}
else if(isClosedBracket(chars[i])) {
return false;
}
else if(isDigit(chars[i])) {
state = State.Numeral1;
}
else if(isOperator(chars[i])) {
return false;
}
}
else if(state == State.Numeral1) {
if(isOpenBracket(chars[i]) || isClosedBracket(chars[i]) || isDigit(chars[i])) {
return false;
}
else if(isOperator(chars[i])) {
state = State.Operator;
}
}
else if(state == State.Numeral2) {
if(isOpenBracket(chars[i]) || isDigit(chars[i]) || isOperator(chars[i])) {
return false;
}
else if(isClosedBracket(chars[i])) {
depth--;
state = State.CloseBracket;
}
}
else if(state == State.Operator) {
if(isOpenBracket(chars[i])) {
depth++;
state = State.OpenBracket;
}
else if(isClosedBracket(chars[i]) || isOperator(chars[i])) {
return false;
}
else if(isDigit(chars[i])) {
state = State.Numeral2;
}
}
else if(state == State.CloseBracket) {
if(isOpenBracket(chars[i]) || isDigit(chars[i])) {
return false;
}
else if(isClosedBracket(chars[i])) {
depth--;
state = State.CloseBracket;
}
else if(isOperator(chars[i])) {
state = State.Plain;
}
}
}
if(!isBalanced(fpe))
return false;
return true;
}
public static boolean isDigit(char c) {
return Character.isDigit(c) == true;
}
public static boolean isOperator(char c) {
return c == '+' || c == '*';
}
public static boolean isOpenBracket(char c) {
return c == '(';
}
public static boolean isClosedBracket(char c) {
return c == ')';
}
public static boolean isBalanced(String fpe) {
char[] chars = fpe.toCharArray();
int opened = 0, closed = 0;
for(char c : chars) {
if(c == '(')
opened++;
if(c == ')')
closed++;
}
return opened > 0 && opened == closed;
}
public enum State {
Plain, OpenBracket, Numeral1, Numeral2, Operator, CloseBracket
}
}
Was ich nach wievor nicht verstehe ist der Zustand "Plain", wieso da ein Operator kommen darf. Ist mit "Plain" ein whitespace-char gemeint?
EDIT-AGAIN(!):
Scheinbar nicht, das Programm funktioniert auch mit whitespaces im FPE, auch wenn man diese nicht strippt. Ich gehe mal davon aus das diese Lösung korrekt ist, wenn jemand noch Anmerkungen hat das ich was falsch gemacht habe, bitte bescheid geben!
In der Aufgabe heißt es ja auch: Achtung: der Automat erkennt nicht alle Ausdrücke richtig. Er gnügt aber für Ausdrücke der Form
((1+2) * (3+4))
Daraus schließe ich mal das mein Programm trotz Akzeptanz von zB "((1+2) * (3+4))-" dennoch richtig ist.
