تقييم التعبير العودية باستخدام جافا

Question

سأقوم بكتابة مُقيِّم تعبير لا يفعل سوى الإضافة والطرح. لدي خوارزمية بسيطة للقيام بذلك ؛ لكن لدي بعض مشاكل التنفيذ.

لقد اعتبرت تعبيرًا (إنها سلسلة)

"(" <expression1> <operator> <expression2> ")"

ها هي خوارزمية

String evaluate( String expression )

   if expression is digit
      return expression

   else if expression is "(" <expression1> <operator> <expression2> ")"
      cut the brackets out of it
      expression1 = evaluate( <expression1> )
      operator = <operator>
      expression2 = evaluate( <expression2> )

   if operator is +
      expression1 + expression2

   else if operator is -
      expression1 - expression2 

مشكلتي هي التحليل <expression1>, <operator> و <expression2> من التعبير. كيف أقوم بذلك؟

ملاحظة: أنا لا أطلب رمزًا. كل ما أحتاجه هو فكرة للقيام بذلك.

شكرًا لك،

-لي

Answer 1

مشكلتي هي التحليلu003Cexpression1> بu003Coperator> وu003Cexpression2> من التعبير

لا تفعل ذلك ، ثم :) عندما ترى قوسًا افتتاحيًا ، قم بإجراء مكالمتك العودية للتعبير. في نهاية عملية التعبير ، إما أن تجد مشغلًا آخر (ولذا أنت لست في نهاية التعبير بعد كل شيء) ، أو شوطًا يمينيًا ، وفي هذه الحالة تعود من التقييم.

Answer 2

إما أنك تستخدم مولد محلل مثل جافاكوب أو Antlr. اكتب BNF من تعبيرك وإنشاء محلل. فيما يلي عينة من القواعد التي ستجعلك تبدأ:

Expression ::= Digit
            |  LeftBracket Expression Plus Expression RightBracket
            |  LeftBracket Expression Minus Expression RightBracket
            |  LeftBracket Expression RightBracket

طريقة "الاختراق" لفعل ذلك بنفسك هي البحث عن الأول ) التراجع إلى الأقرب ( انظر إلى تعبير حرية قوسين بينهما ، ما عليك سوى الانقسام على رموز المشغل والتقييم.

Answer 3

أوصي بتغيير إدخال Infix إلى Postfix ثم تقييمه ، بدلاً من تقليل التعبير عن infix-wise. هناك بالفعل خوارزميات محددة جيدًا لهذا الغرض ولا تأتي مع مشاكل تحليل الأمراض المتعددة المتأصلة.

ألق نظرة على خوارزمية ساحة Shunting للتحويل إلى postfix/rpn ثم تقييمه باستخدام مكدس باستخدام عمليات postfix. هذا سريع (س (ن)) وموثوق به.

HTH

Answer 4

استخدم stringtokenizer لتقسيم سلسلة الإدخال الخاصة بك إلى قوسين ومشغلي وأرقام ، ثم تكرار على الرموز المميزة الخاصة بك ، وإجراء مكالمة متكررة لكل حماة مفتوحة ، والخروج من طريقتك لكل قوسين قريبة.

أعلم أنك لم تطلب رمزًا ، لكن هذا يعمل لإدخال صالح:

public static int eval(String expr) {
    StringTokenizer st = new StringTokenizer(expr, "()+- ", true);
    return eval(st);
}

private static int eval(StringTokenizer st) {
    int result = 0;
    String tok;
    boolean addition = true;
    while ((tok = getNextToken(st)) != null) {
        if (")".equals(tok))
            return result;
        else if ("(".equals(tok))
            result = eval(st);
        else if ("+".equals(tok))
            addition = true;
        else if ("-".equals(tok))
            addition = false;
        else if (addition)
            result += Integer.parseInt(tok);
        else
            result -= Integer.parseInt(tok);
    }
    return result;
}

private static String getNextToken(StringTokenizer st) {
    while (st.hasMoreTokens()) {
        String tok = st.nextToken().trim();
        if (tok.length() > 0)
            return tok;
    }
    return null;
}

سيحتاج إلى معالجة أفضل لإدخال غير صالح ، لكنك تحصل على الفكرة ...

Answer 5

أود أن أقترح اتباع نهج يشبه بشكل أوثق تلك الموصوفة في هذه القديمة ولكن (في رأيي) سلسلة من المقالات ذات الصلة حول تصميم المترجم. لقد وجدت أن نهج استخدام وظائف/طرق صغيرة تحدر أجزاء من التعبير فعالة للغاية.

يتيح لك هذا النهج أن تحلل طريقة التحليل الخاصة بك إلى العديد من الأهداف الفرعية التي يتبع أسماءها وترتيب التنفيذ عن كثب ebnf قد تستخدم لوصف التعبيرات المراد تحليلها.

Answer 6

ربما خلق تعبيرات منتظمة إلى عن على التعبير و المشغل أو العامل ثم استخدم المطابقة لتحديد المحتوى الخاص بك.