אלגוריתם לחישוב תוצאה של מחרוזת מתמטית

מדעי המחשב ואלקטרוניקה
1

נתון ביטוי לדוגמה (1\cdot 2)+4^2\cdot 3-4. הביטוי הוא מחרוזת (string).
יש לתכנן אלגוריתם אשר יחזיר את התוצאה.
אשמח לעזרה עם תכנון אלגוריתם בשפת Java.
תודה רבה!

2

מצאתי באינטרנט תוכנית ממש טובה שעונה על הדרישות של האלגוריתם. זאת שאלה די נפוצה לכן עדיף להריץ חיפוש באחד ממנועי החיפוש ולמצוא תשובה.
להלן התוכנית בשפת Java:

public static double eval(final String str) {
    return new Object() {
        int pos = -1, ch;

        void nextChar() {
            ch = (++pos < str.length()) ? str.charAt(pos) : -1;
        }

        boolean eat(int charToEat) {
            while (ch == ' ') nextChar();
            if (ch == charToEat) {
                nextChar();
                return true;
            }
            return false;
        }

        double parse() {
            nextChar();
            double x = parseExpression();
            if (pos < str.length()) throw new RuntimeException("Unexpected: " + (char)ch);
            return x;
        }

        // Grammar:
        // expression = term | expression `+` term | expression `-` term
        // term = factor | term `*` factor | term `/` factor
        // factor = `+` factor | `-` factor | `(` expression `)`
        //        | number | functionName factor | factor `^` factor

        double parseExpression() {
            double x = parseTerm();
            for (;;) {
                if      (eat('+')) x += parseTerm(); // addition
                else if (eat('-')) x -= parseTerm(); // subtraction
                else return x;
            }
        }

        double parseTerm() {
            double x = parseFactor();
            for (;;) {
                if      (eat('*')) x *= parseFactor(); // multiplication
                else if (eat('/')) x /= parseFactor(); // division
                else return x;
            }
        }

        double parseFactor() {
            if (eat('+')) return parseFactor(); // unary plus
            if (eat('-')) return -parseFactor(); // unary minus

            double x;
            int startPos = this.pos;
            if (eat('(')) { // parentheses
                x = parseExpression();
                eat(')');
            } else if ((ch >= '0' && ch <= '9') || ch == '.') { // numbers
                while ((ch >= '0' && ch <= '9') || ch == '.') nextChar();
                x = Double.parseDouble(str.substring(startPos, this.pos));
            } else if (ch >= 'a' && ch <= 'z') { // functions
                while (ch >= 'a' && ch <= 'z') nextChar();
                String func = str.substring(startPos, this.pos);
                x = parseFactor();
                if (func.equals("sqrt")) x = Math.sqrt(x);
                else if (func.equals("sin")) x = Math.sin(Math.toRadians(x));
                else if (func.equals("cos")) x = Math.cos(Math.toRadians(x));
                else if (func.equals("tan")) x = Math.tan(Math.toRadians(x));
                else throw new RuntimeException("Unknown function: " + func);
            } else {
                throw new RuntimeException("Unexpected: " + (char)ch);
            }

            if (eat('^')) x = Math.pow(x, parseFactor()); // exponentiation

            return x;
        }
    }.parse();
}`

שים לב כי התוכנית תומכת לא רק באופרטורים בסיסים כמו חיבור, כפל והעלאה בחזקה אלא היא גם תומכת בפונקציית סינוס, פונקציית קסינוס וכו’. אם אתה לא מעוניין לתמוך בפונקציות אלה, פשוט תוריד אותן. כמו כן, שים לב כי מוגדר לך (בהערה) ה-BNF שהתוכנית תומכת, כלומר הדקדוק שעל פיו האלגוריתם עובד. לכן עבור התוכנית הבאה:

String InputString = "(1*2)+4^2*3-4";
System.out.println(eval(InputString));

נקבל את הפלט: 46.0, שזאת אכן התשובה של החישוב (1\cdot2)+4^2 \cdot 3-4.
בהצלחה :slight_smile: