Infix till Postfix !
Hej!
Har I uppgift att skapa en metod som konverterar en string från infix till postfix.
Har nu kommit ganska långt med metoden. Då den funkar bra för vissa tester men, misslyckas helt för andra.
Bifogar testet, och koden.
List<String> infix2Postfix(List<String> infix) {
List<String> resultPostfix = new ArrayList<>();
Deque<String> s = new ArrayDeque<>();
for (int i = 0; i < infix.size(); i++) {
String token = infix.get(i);
if (!isOperator(token)) { //if token is operand.
resultPostfix.add(token); //add to postfix list.
} else if (isOperator(token)) { //if operator,
while (!s.isEmpty() && getPrecedence(s.peek()) >= getPrecedence(token) && !Objects.equals(s.peek(), "(")) {
resultPostfix.add(s.peek());
s.pop();
}
s.push(token);
} else if (token.equals("(")) {
s.push(token);
} else if (token.equals(")")) {
while (!s.isEmpty() && s.peek() != "(") {
resultPostfix.add(s.peek());
s.pop();
}
s.pop();
}
}
while (!s.isEmpty()) {
resultPostfix.add(s.peek()); //finally, we add left tokens to list and pop.
s.pop();
}
return resultPostfix;
}
boolean isOperator(String st) {
switch (st) {
case "^":
case "/":
case "*":
case "+":
case "-":
return true;
default:
return false;
}
}
int getPrecedence(String op) { //order of operations
if ("+-".contains(op)) {
return 2;
} else if ("*/".contains(op)) {
return 3;
} else if ("^".contains(op)) {
return 4;
} else {
throw new RuntimeException(OP_NOT_FOUND);
}
}
//Den delen är test delen!
// Infix to postfix -----------------------
i2p("1+10", "1 10 +");
i2p("1+2+3", "1 2 + 3 +");
i2p("1+2-3", "1 2 + 3 -");
i2p("3-2-1", "3 2 - 1 -");
i2p("1 + 2 * 3", "1 2 3 * +");
i2p("1 / 2 + 3", "1 2 / 3 +");
i2p("20/4/2", "20 4 / 2 /");
i2p("4^3^2", "4 3 2 ^ ^");
i2p("4^3*2", "4 3 ^ 2 *");
i2p("(1+2)*3", "1 2 + 3 *");
i2p("2^(1+1)", "2 1 1 + ^");
//kör jag koden på testet så får jag följande:
[1, 10, +]
true
[1, 2, +, 3, +]
true
[1, 2, +, 3, -]
true
[3, 2, -, 1, -]
true
[1, 2, 3, *, +]
true
[1, 2, /, 3, +]
true
[20, 4, /, 2, /]
true
[4, 3, ^, 2, ^]
false
[4, 3, ^, 2, *]
true
[(, 1, 2, ), 3, *, +]
false
[2, (, 1, ^, 1, ), +]
false
Process finished with exit code 0
Försökte att ta bort mitt gamla inlägg (då koden där var rörigt), kunde inte göra det.
Har inte satt mig in i algoritmen eller provat programmet men en undran:
Är inte det här testet fel?:i2p("4^3^2", "4 3 2 ^ ^"); och du får [4, 3, ^, 2, ^]
Är inte det programmet ger (också) rätt?
I så fall är det bara fallen med parenteser som är fel.
Om du inte har det redan, gör en metod som skriver ut i, token, s, resultPostfix som du ropar på efter varje förändring. Då borde du kunna se vad som går fel.
Programmeraren skrev:Har inte satt mig in i algoritmen eller provat programmet men en undran:
Är inte det här testet fel?:i2p("4^3^2", "4 3 2 ^ ^"); och du får [4, 3, ^, 2, ^]
Är inte det programmet ger (också) rätt?
I så fall är det bara fallen med parenteser som är fel.Om du inte har det redan, gör en metod som skriver ut i, token, s, resultPostfix som du ropar på efter varje förändring. Då borde du kunna se vad som går fel.
Ju, min kod ger fel på det testet. och på de två sista också.
Tycker inte det är uppenbart hur 4^3^2 ska tolkas. Från wikipedia:
Men om ni fått testerna som del av uppgiften så är det förstås definierat till 4^(3^2)
Hmowed skrev:Programmeraren skrev:Har inte satt mig in i algoritmen eller provat programmet men en undran:
Är inte det här testet fel?:i2p("4^3^2", "4 3 2 ^ ^"); och du får [4, 3, ^, 2, ^]
Är inte det programmet ger (också) rätt?
I så fall är det bara fallen med parenteser som är fel.Om du inte har det redan, gör en metod som skriver ut i, token, s, resultPostfix som du ropar på efter varje förändring. Då borde du kunna se vad som går fel.
Ju, min kod ger fel på det testet. och på de två sista också.
Jag försökte att ha med fallen med parenteser, är inte tanken att ifall man har "(" så fortsätter man tills man har en slut parentes ")" och då poppar man den som finns inuti parenteser? Jag kanske har fel.
Programmeraren skrev:Tycker inte det är uppenbart hur 4^3^2 ska tolkas. Från wikipedia:
Men om ni fått testerna som del av uppgiften så är det förstås definierat till 4^(3^2)
Jag tror att fallet med "^" har och göra med (Associativity), vi hade en hjälp metod som jag inte använt. bifogar den.
Kan det vara så att just vid konvertering från infix till postfix så finns det andra regler?
Assoc getAssociativity(String op) {
if ("+-*/".contains(op)) {
return Assoc.LEFT;
} else if ("^".contains(op)) {
return Assoc.RIGHT;
} else {
throw new RuntimeException(OP_NOT_FOUND);
}
}
enum Assoc {
LEFT,
RIGHT
}Du behöver använda getAssociativity() för att få "4^3^2" rätt.
Vad gäller parenteser så har jag inte satt mig in hur programmet funkar så har ingen åsikt. Rent allmänt med postfix brukar en av poängerna vara att man blir av med alla parenteser men du får ju med dina i resultatet så angående parenteser får du nog tänka om. I princip ska ju hela parentesen beräknas och ersättas med ett värde på stacken, typ:
(1+2)*(3+4) --> 1 2 + 3 4 + *
Du kan ju tänka att ett uttryck med parenteser är som ett helt separat uttryck.
Jag är lite ovan använda en stack i en loop, jag brukar göra metoder som ropar rekursivt på varandra istället (stacken blir då implicit i anropskedjan). Men i princip samma sak.
Programmeraren skrev:Du behöver använda getAssociativity() för att få "4^3^2" rätt.
Vad gäller parenteser så har jag inte satt mig in hur programmet funkar så har ingen åsikt. Rent allmänt med postfix brukar en av poängerna vara att man blir av med alla parenteser men du får ju med dina i resultatet så angående parenteser får du nog tänka om. I princip ska ju hela parentesen beräknas och ersättas med ett värde på stacken, typ:
(1+2)*(3+4) --> 1 2 + 3 4 + *
Du kan ju tänka att ett uttryck med parenteser är som ett helt separat uttryck.Jag är lite ovan använda en stack i en loop, jag brukar göra metoder som ropar rekursivt på varandra istället (stacken blir då implicit i anropskedjan). Men i princip samma sak.
Alright, så om operator är "^" så ska jag istället gå igenom från h=>v?
Jag tror att jag behöver sätta mig och debugga, för att se det som är fel med fallet med parenteser. för att sen försöka åtgärda detta.
tack för hjälpen så länge :)
Ja, höger till vänster för ^
Parenteser: Se till att hela uttrycket i parentesen beräknas klart innan nästa beräkning sker. Precis som om det hade varit ett eget uttryck du gett till din metod.
double evalPostfix(List<String> postfix) {
Deque<Double> s = new ArrayDeque<>();
for (int i = 0; i < postfix.size(); i++) {
String token = postfix.get(i);
if (token.matches("[0-9]+")) {
double numToken = Double.parseDouble(token);
s.push(numToken);
} else if (isOperator(token)) {
double op1 = s.peek();
s.pop();
double op2 = s.peek();
s.pop();
s.push(applyOperator(token, op1, op2));
}
}
return s.peek();
}
double applyOperator(String op, double d1, double d2) {
switch (op) {
case "+":
return d1 + d2;
case "-":
return d2 - d1;
case "*":
return d1 * d2;
case "/":
if (d1 == 0) {
throw new IllegalArgumentException(DIV_BY_ZERO);
}
return d2 / d1;
case "^":
return pow(d2, d1);
}
throw new RuntimeException(OP_NOT_FOUND);
}
// ------- Infix 2 Postfix ------------------------
List<String> infix2Postfix(List<String> infix) {
List<String> resultPostfix = new ArrayList<>();
Deque<String> s = new ArrayDeque<>();
for (int i = 0; i < infix.size(); i++) {
String token = infix.get(i);
if (token.matches("[0-9]+")) { //if token is operand.
resultPostfix.add(token); //add to postfix list.
} else if (isOperator(token)) {
if (s.isEmpty() || s.peek().equals("(")) {
s.push(token);
} else if (!s.isEmpty() && (getPrecedence(token) < getPrecedence(s.peek()))) {
while(!s.isEmpty() && getPrecedence(token) < getPrecedence(s.peek()))
{ resultPostfix.add(s.pop());}
s.push(token);
} else if (!s.isEmpty() && (getPrecedence(token) > getPrecedence(s.peek()))) {
s.push(token);
} else if (!s.isEmpty() && (getPrecedence(token) == getPrecedence(s.peek()))
&& (getAssociativity(s.peek()) == Assoc.LEFT )){//|| token.equals(s.peek()))){
resultPostfix.add(s.pop());
s.push(token);
}else if (!s.isEmpty() && (getPrecedence(token) == getPrecedence(s.peek()))
&& (getAssociativity(s.peek()) == Assoc.RIGHT)){
s.push(token);
}
} else if (token.equals("(")) {
s.push(token);
} else if (token.equals(")")) {
if (!s.isEmpty() && !Objects.equals(s.peek(), "(")) {
resultPostfix.add(s.pop());
}
s.pop();
}
}
while (!s.isEmpty()) {
resultPostfix.add(s.pop());
}
return resultPostfix;
}
boolean isOperator(String st) {
switch (st) {
case "^":
case "/":
case "*":
case "+":
case "-":
return true;
default:
return false;
}
}
int getPrecedence(String op) { //order of operations
if ("+-".contains(op)) {
return 2;
} else if ("*/".contains(op)) {
return 3;
} else if ("^".contains(op)) {
return 4;
} else {
throw new RuntimeException(OP_NOT_FOUND);
}
}
Assoc getAssociativity(String op) {
if ("+-*/".contains(op)) {
return Assoc.LEFT;
} else if ("^".contains(op)) {
return Assoc.RIGHT;
} else {
throw new RuntimeException(OP_NOT_FOUND);
}
}
enum Assoc {
LEFT,
RIGHT
}
// ---------- Tokenize -----------------------
// List String (not char) because numbers (with many chars)
List<String> tokenize(String expr) {
String goodExpr = padNumbersandParentheses(expr).trim(); //ligger mellan slag enligt metoden pNaP.
List<String> listTokens = new ArrayList<>();//Empty List.//
StringTokenizer tokens = new StringTokenizer(goodExpr); //StringTokenizer.
while (tokens.hasMoreTokens()) {
listTokens.add(tokens.nextToken());
}
return listTokens;
}
String padNumbersandParentheses(String expr) { //ligger mellanslag före och efter nummer/parenteser
return expr.replaceAll("([0-9]+)", " $1 ").replaceAll("([()])", " $1 ");
}
}
