Infix to Postfix!
Hej!
Jag har i uppgift att konvertera en String (expr) från infix till postfix, där (expr) har delats in i tokens som kan vara (nummer, operator och parentes "(" ")").
Så här har jag kommit med koden än så länge:
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 tokenValue = infix.get(i);
if ("0-9".contains(tokenValue)){
resultPostfix.add(tokenValue);
}else if (isOperator(tokenValue)){
while (!s.isEmpty() && getPrecedence(tokenValue) <= getPrecedence(s.pop()) && s.pop()!= "("){
resultPostfix.add(s.pop());
s.pop();
}
}
}
return null; //här returnerar jag null för att kunna debugga.
}
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);
}
}
Har ett problem med första metoden infixTopostfix, efter att jag får tokenValue så vill jag kolla om det är ett nummer. Är det ett nummer så vill jag addera det till min Lista. Men, det verkar vara fel där (Då jag får "False" vid debuggning av if-satsen).
Vidare så har jag inte riktigt koll om resten av metod är logisk.
Kan du ordna så koden blir indenterad? Då är den lättare att läsa. Använd kod-verktyget, som ser ut som {}.
Så har har jag kommit med koden. Den funkar ganska bra för några tester, men när det kommer till att behandla parenteser och fallet så har min kod misslyckats. bifogar tester och vad jag fått vid körning av koden.
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 + ^");
[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
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;
}Det här var svårare än de flesta programmeringsfrågor, men jag ska försöka lösa det.
Har du gjort algoritmen själv eller läst om den någonstans?
Laguna skrev:Det här var svårare än de flesta programmeringsfrågor, men jag ska försöka lösa det.
Har du gjort algoritmen själv eller läst om den någonstans?
Jag har haft en del mindre uppgifter som förberedelse inför denna uppgift.
Har oxå kollat på den här
Det verkar sunt i princip. Jag ser några tveksamheter, men de är inte relevanta för dina testfall. Men jag förstår inte hur parenteser kan hamna i utstacken, man får noggrant gå steg för steg. Har du gjort det?
Vad gäller ^ i fel ordning så får man betrakta en kommande ^ som högre prioritet än den första ^ så fungerar det.
Laguna skrev:Det verkar sunt i princip. Jag ser några tveksamheter, men de är inte relevanta för dina testfall. Men jag förstår inte hur parenteser kan hamna i utstacken, man får noggrant gå steg för steg. Har du gjort det?
Vad gäller ^ i fel ordning så får man betrakta en kommande ^ som högre prioritet än den första ^ så fungerar det.
Yes, i slutet så tänkte jag samma vad det gäller att gå steg för steg.
Koden innehåller många if/else if, men känns lätt att begripa. Tror att man kunde använde while för att släppa if/else if satser.
Här är 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 (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()))) {
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)) {
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;
}Koden har passerat alla tester förutom ett, bifogar testen också:
// Infix to postfix -----------------------
i2p ("Infix", "Förväntat")
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 + ^");
i2p(" 1 ^ 1 ^ 1 ^ 1 - 1", " 1 1 ^ 1 ^ 1 ^ 1 -"); //False
Resultat när jag körde koden:
[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, ^, ^]
true
[4, 3, ^, 2, *]
true
[1, 2, +, 3, *]
true
[2, 1, 1, +, ^]
true
[1, 1, 1, 1, ^, 1, -, ^, ^]
false
Process finished with exit code 0
koden lyckades inte med sista testet.
Laguna skrev:Det verkar sunt i princip. Jag ser några tveksamheter, men de är inte relevanta för dina testfall. Men jag förstår inte hur parenteser kan hamna i utstacken, man får noggrant gå steg för steg. Har du gjort det?
Vad gäller ^ i fel ordning så får man betrakta en kommande ^ som högre prioritet än den första ^ så fungerar det.
Vad det gäller ^, Jaha. Nu fattar jag varför testet gick inte igenom.
Nu löste det sig, tack för hjälpen.
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()))) {
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;
}
Nu har jag inte tittat så noga på det senaste, men fungerar det med parenteser i flera nivåer, t.ex. 2*(3-(4+7))?
Laguna skrev:Nu har jag inte tittat så noga på det senaste, men fungerar det med parenteser i flera nivåer, t.ex. 2*(3-(4+7))?
Ja, det fungerar bra.
Calculator v 1.0. To exit input bye
> 2*(3-(4+7))
-16.0
> bye
Process finished with exit code 0
Först nu upptäckte jag att du hade en till tråd om precis samma sak.
Laguna skrev:Först nu upptäckte jag att du hade en till tråd om precis samma sak.
Ja, försökte att radera en av de. Lyckades inte med det :).
Man kan tala om det i tråden. Jag tänkte jag skulle titta mer efter eventuella buggar, men nu gör jag inte det.
