18 svar
96 visningar
Hmowed är nöjd med hjälpen
Hmowed 63
Postad: 1 dec 2021 16:28 Redigerad: 1 dec 2021 17:18

Evaluation av Postfix!

Hej! 

Jag håller på med att göra en metod som evaluerar en Postfix och som returnerar ett värde (int).

Vid testning av koden så fick jag False vid tre olika tillfällen. Bifogar koden och testet.

double evalPostfix(List<String> postfix) {

        Deque<Integer> s = new ArrayDeque<>(); 
        for (int i = 0; i < postfix.size(); i++){
            String token = postfix.get(i);

            if (!isOperator(token)){
                 int numToken = Integer.parseInt(token);  //String to Integer.
                s.push(numToken);

            }else if (isOperator(token)){
                double op2 = s.peek();
                s.pop();
                double op1 = s.peek();
                s.pop();
                s.push((int) applyOperator(token, op2, op1));

            }
        }
        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);
    }

Testet:

// Evaluation ------------------------------
                                       resultat:                            

        e("123", 123);                  123.0   True                        

    // Basic operations
        e("1 + 10", 11);                11.0    True                    
        e("1 + 0", 1);			1.0	True
        e("1 - 10", -9);  		-9.0	True
        e("10 - 1", 9);			9.0	True
        e("60 * 10", 600);		600.0	True
        e("60 * 0", 0);			0.0	True

        e("3 / 2", 1.5);  		1.0	False
        e("1 / 2", 0.5);		0.0	False

        e("2 ^ 4 ", 16);		16.0	True
        e("2 ^ 0 ", 1);			1.0	True

    // Associativity
        e("10 - 5 - 2", 3);  		3.0	True
        e("20 / 2 / 2", 5);  		5.0	True
        e("4 ^ 2 ^ 2", 256);  		256.0	True

    // Precedence
        e("3 * 10 + 2", 32);		32.0	True
        e("3 + 10 * 2", 23);		23.0	True
        e("30 / 3 + 2", 12);		12.0	True
        e("1 + 30 / 3", 11);		11.0	True
        e("3 * 2 ^ 2", 12);		12.0	True
        e("3 ^ 2 * 2", 18);		18.0	True

   // Parentheses
        e("10 - (5 - 2)", 7);		7.0	True
        e("1 * (2 + 3)", 5);		5.0	True
        e("20 / (10 / 2)", 4);		4.0	True
        e("(3 ^ 2) ^ 2", 81);		81.0	True
        e("3 * (10 + 2)", 36);		36.0	True
        e("30 / (3 + 2)", 6);		6.0	True
        e("(3 + 2) ^ 2", 25);		25.0	True
        e(" 2 ^ (1 + 1)", 4);		4.0	True
        e(" ((((1 + 1))) * 2)", 4);	4.0	True


   // Mix priority and right and left associativity
        e(" 1 ^ 1 ^ 1 ^ 1  - 1", 0);	1.0	False
        e(" 4 - 2 - 1 ^ 2 ", 1);	1.0	True


Process finished with exit code 0
Programmeraren 3334
Postad: 1 dec 2021 16:48 Redigerad: 1 dec 2021 16:49

Bra om testfallet, alltså givet, förväntat och utfall, skrivs ut före true/false, jobbigt matcha.

Hmowed 63
Postad: 1 dec 2021 17:04
Programmeraren skrev:

Bra om testfallet, alltså givet, förväntat och utfall, skrivs ut före true/false, jobbigt matcha.

Yes, jag kommer att ändra inlägget. 

Hmowed 63
Postad: 1 dec 2021 17:21
Programmeraren skrev:

Bra om testfallet, alltså givet, förväntat och utfall, skrivs ut före true/false, jobbigt matcha.

Har nu ändrat inlägget. 

Programmeraren 3334
Postad: 1 dec 2021 17:28

e("3 / 2", 1.5); 1.0 False

Ser konstig ut. Själva konverteringen till postfix vore bra att veta att den gått rätt, har du testat det ordentligt?

För säkerhets skull, lägg till så att testerna också skriver ut uttrycket i postfix innan evaluering.

Hmowed 63
Postad: 1 dec 2021 17:30
Programmeraren skrev:

e("3 / 2", 1.5); 1.0 False

Ser konstig ut. Själva konverteringen till postfix vore bra att veta att den gått rätt, har du testat det ordentligt?

För säkerhets skull, lägg till så att testerna också skriver ut uttrycket i postfix innan evaluering.

Har debuggat, och Postfix i detta fall var 32/. Vilket ser bra ut va?

Programmeraren 3334
Postad: 1 dec 2021 17:33 Redigerad: 1 dec 2021 17:33

Ja. Men svårt se koden ovan göra det till 1.0

Skriva ut op, d1, d2 i applyOperator kanske. Divisionen beter sig som om det var "int":ar. Vilket inte är möjligt.

Programmeraren 3334
Postad: 1 dec 2021 17:35 Redigerad: 1 dec 2021 17:35

Ah ser felet, du castar till int i push():

s.push((int) applyOperator(token, op2, op1));

Hmowed 63
Postad: 1 dec 2021 17:42
Programmeraren skrev:

Ja. Men svårt se koden ovan göra det till 1.0

Skriva ut op, d1, d2 i applyOperator kanske. Divisionen beter sig som om det var "int":ar. Vilket inte är möjligt.

Vid applyOperator så ser det bra ut d2/d1 => 3/2, men resultatet i det fallet blir 1. 

Hmowed 63
Postad: 1 dec 2021 17:44
Programmeraren skrev:

Ah ser felet, du castar till int i push():

s.push((int) applyOperator(token, op2, op1));

Jaha, ska jag inte göra det ? Här ger jag type int till token om det är ett nummer. Är det fel?

int numToken = Integer.parseInt(token);
Programmeraren 3334
Postad: 1 dec 2021 17:52 Redigerad: 1 dec 2021 17:52

Nu är det inte tokens längre, nu räknar du tal.

3 2 / --> 1.5
(int) 1.5 --> 1

Din parsning kommer bara klara heltal. Verkar bättre med:
double num = Double.parseDouble(token)

Hmowed 63
Postad: 1 dec 2021 17:57 Redigerad: 1 dec 2021 18:08
Programmeraren skrev:

Nu är det inte tokens längre, nu räknar du tal.

3 2 / --> 1.5
(int) 1.5 --> 1

Din parsning kommer bara klara heltal. Verkar bättre med:
double num = Double.parseDouble(token)

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();
    }

Det löste sig för de fall med div. 

Programmeraren 3334
Postad: 1 dec 2021 18:05

Men byt till
double num = Double.parseDouble(token)
så klarar du även decimaltal.

Hmowed 63
Postad: 1 dec 2021 18:06

Nu är det detta fall som min kod ger False på:

e(" 1 ^ 1 ^ 1 ^ 1  - 1", 0);

När jag debuggar så får jag Postfix uttrycket till att vara 

[1, 1, 1, 1, ^, 1, -, ^, ^]

Vilket ser inte bra ut va, Det verkar att rätt postfix i detta fall skall vara 

11^1^1^1-
Hmowed 63
Postad: 1 dec 2021 18:09
Programmeraren skrev:

Men byt till
double num = Double.parseDouble(token)
så klarar du även decimaltal.

Japp, gjorde det. 

Programmeraren 3334
Postad: 1 dec 2021 18:09 Redigerad: 1 dec 2021 18:09

Exakt. Kanske nåt med din höger-association för ^ som gör att du glömmer sätta in ^

Hmowed 63
Postad: 1 dec 2021 18:12
Programmeraren skrev:

Exakt. Kanske nåt med din höger-association för ^ som gör att du glömmer sätta in ^

Det kan vara något som är fel med min infixTopostfix kod som göra att jag får fel Postfix nu. Det är ganska märkligt då min infixTopostfix kod klarade alla tester som är nödvändiga för nästa steg.

Hmowed 63
Postad: 1 dec 2021 18:16
Programmeraren skrev:

Exakt. Kanske nåt med din höger-association för ^ som gör att du glömmer sätta in ^

Skulle du kunna ta och kika på min infixTopostfix kod,

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.peek());
                    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.peek());
                    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.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);
        }
    }

    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
    }
Programmeraren 3334
Postad: 1 dec 2021 18:41

Har inte läst men kan det vara så att din högerassociation av ^ inte kollar att det är ^ till vänster? Och därför hamnar de till höger om "-"?

Svara Avbryt
Close