Пользователь
0,2
рейтинг
22 июня 2011 в 01:01

Разработка → Парсер формул с помощью метода рекурсивного спуска



Доброго времени суток, уважаемые Хабровчане!

Хочу поделится с вами реализацией алгоритма «Метод рекурсивного спуска» на примере написания парсера формул с поддержкой переменных и функций на языке Java

Эта статья в (скорее всего, во всяком случае я надеюсь :) ) будет интересна для новичков, или кому-то применить как фундамент для своего решения данной задачи.
Кому интересно — прошу под кат


ТЗ


Разработать парсер формул который:
  • соблюдает правильную очередь выполнения операций
  • поддерживает функции
  • поддерживает переменные


Вступление


Суть данного метода состоит в том, что он разделяется на свои подзадачи. В свою очередь подзадача должна работать только с тем, с чем умеет работать, если условия не удовлетворяются передавать управление дальше. Если же условия удовлетворены, делаем вычисления и передаем оставшуюся часть необработанного текста. Выполнение происходит до тех пор, пока текст все еще есть или же если ни одна подзадача не может обработать текущее состояние.

Также имеет значение приоритет подзадачи. Меняя приоритет подзадачи поменяется и поведение парсера.
Поскольку мы будем реализовывать парсер математических формул, то для расставления приоритетов мы будем руководствоваться приоритетами математических операций:
  1. функция и переменная
  2. скобки
  3. умножение и деление
  4. сложение и вычитание


Полетели



Ну, теперь за дело.
Как я уже выше упомянул, мы будем манипулировать остатком от строки, т.е каждая задача откусывает что ей по зубам и передает дальше, что проглотить не может.
Итого нам нужна следующая структура:
строковая переменная для хранения остатка строки
и так называемый аккумулятор, для хранения текущего состояния процесса вычисления
Нужно? Сделаем!
class Result
{

    public double acc;
    public String rest;

    public Result(double v, String r)
    {
        this.acc = v;
        this.rest = r;
    }
}


Теперь приступим за сам парсер:
первым делом вызывать мы будем подзадачу с самым низким приоритетом.
Подзадачи в свою очередь передают управление подзадачам с более высоким приоритетом и после каждого своего действия, которое повлияло на текст, также передаем управление подзадачи с высоким приоритетом.
И как сказано было уже выше, выполнение программы будет продолжаться пока есть что парсить, или мы наткнемся на неизвестную структуру или последовательность данных.

Из метода который осуществляет сложение/вычитание мы будем вызывать умножение/деление и так далее

Для общего понимания, немного упростим задачу, сделаем парсер, который лишь выполняет операции сложения и вычитания:

public class MatchParserPlusMinus {

    public MatchParserPlusMinus(){}

    public double Parse(String s) throws Exception
    {
        Result result = PlusMinus(s);
        if (!result.rest.isEmpty()) {
            System.err.println("Error: can't full parse");
            System.err.println("rest: " + result.rest);
        }
        return result.acc;
    }

    private Result PlusMinus(String s) throws Exception
    {
        Result current = Num(s);
        double acc = current.acc;

        while (current.rest.length() > 0) {
            if (!(current.rest.charAt(0) == '+' || current.rest.charAt(0) == '-')) break;

            char sign = current.rest.charAt(0);
            String next = current.rest.substring(1);

            acc = current.acc;
            
            current = Num(next);
            if (sign == '+') {
                acc += current.acc;
            } else {
                acc -= current.acc;
            }
            current.acc = acc;
        }
        return new Result(current.acc, current.rest);
    }

   private Result Num(String s) throws Exception
   {
        int i = 0;
        int dot_cnt = 0;
        boolean negative = false;
        // число также может начинаться с минуса
        if( s.charAt(0) == '-' ){
            negative = true;
            s = s.substring( 1 );
        }
        // разрешаем только цифры и точку
        while (i < s.length() && (Character.isDigit(s.charAt(i)) || s.charAt(i) == '.')) {
            // но также проверям, что в числе может быть только одна точка!
            if (s.charAt(i) == '.' && ++dot_cnt > 1) {
                throw new Exception("not valid number '" + s.substring(0, i + 1) + "'");
            }
            i++;
        }
        if( i == 0 ){ // что-либо похожее на число мы не нашли
            throw new Exception( "can't get valid number in '" + s + "'" );
        }

        double dPart = Double.parseDouble(s.substring(0, i));
        if( negative ) dPart = -dPart;
        String restPart = s.substring(i);

        return new Result(dPart, restPart);
    }
} 



и при вызове:
        MatchParserPlusMinus pm = new MatchParserPlusMinus();
        String f = "10-8+2+6";
        try{
            System.out.println( "PlusMinus: " + pm.Parse(f) );
        }catch(Exception e){
            System.err.println( "Error while parsing '"+f+"' with message: " + e.getMessage() );
        } 


Выведет нам:
PlusMinus: 10.0


В данном парсере мной было реализованы следующие функции (расширить этот список своими функциями можно добавив соответствующее условие в processFunction ):
  • sin
  • cos
  • tan

Над обработкой ошибок я особо не заморачивался (что бы не засорять «полезный» код), а то в итоге кода по обработке ошибок может быть больше чем кода для самого парсера :)

Вот полный листиннг класса без упрощения:
public class MatchParser
{
    private HashMap<String, Double> variables;

    public MatchParser()
    {
        variables = new HashMap<String, Double>();
    }

    public void setVariable(String variableName, Double variableValue)
    {
        variables.put(variableName, variableValue);
    }

    public Double getVariable(String variableName)
    {
        if (!variables.containsKey(variableName)) {
            System.err.println( "Error: Try get unexists variable '"+variableName+"'" );
            return 0.0;
        }
        return variables.get(variableName);
    }

    public double Parse(String s) throws Exception
    {
        Result result = PlusMinus(s);
        if (!result.rest.isEmpty()) {
            System.err.println("Error: can't full parse");
            System.err.println("rest: " + result.rest);
        }
        return result.acc;
    }

    private Result PlusMinus(String s) throws Exception
    {
        Result current = MulDiv(s);
        double acc = current.acc;

        while (current.rest.length() > 0) {
            if (!(current.rest.charAt(0) == '+' || current.rest.charAt(0) == '-')) break;

            char sign = current.rest.charAt(0);
            String next = current.rest.substring(1);

            current = MulDiv(next);
            if (sign == '+') {
                acc += current.acc;
            } else {
                acc -= current.acc;
            }
        }
        return new Result(acc, current.rest);
    }

    private Result Bracket(String s) throws Exception
    {
        char zeroChar = s.charAt(0);
        if (zeroChar == '(') {
            Result r = PlusMinus(s.substring(1));
            if (!r.rest.isEmpty() && r.rest.charAt(0) == ')') {
                r.rest = r.rest.substring(1);
            } else {
                System.err.println("Error: not close bracket");
            }
            return r;
        }
        return FunctionVariable(s);
    }

    private Result FunctionVariable(String s) throws Exception
    {
        String f = "";
        int i = 0;
        // ищем название функции или переменной
        // имя обязательно должна начинаться с буквы
        while (i < s.length() && (Character.isLetter(s.charAt(i)) || ( Character.isDigit(s.charAt(i)) && i > 0 ) )) {
            f += s.charAt(i);
            i++;
        }
        if (!f.isEmpty()) { // если что-нибудь нашли
            if ( s.length() > i && s.charAt( i ) == '(') { // и следующий символ скобка значит - это функция
                Result r = Bracket(s.substring(f.length()));
                return processFunction(f, r);
            } else { // иначе - это переменная
                return new Result(getVariable(f), s.substring(f.length()));
            }
        }
        return Num(s);
    }

    private Result MulDiv(String s) throws Exception
    {
        Result current = Bracket(s);

        double acc = current.acc;
        while (true) {
            if (current.rest.length() == 0) {
                return current;
            }
            char sign = current.rest.charAt(0);
            if ((sign != '*' && sign != '/')) return current;

            String next = current.rest.substring(1);
            Result right = Bracket(next);

            if (sign == '*') {
                acc *= right.acc;
            } else {
                acc /= right.acc;
            }

            current = new Result(acc, right.rest);
        }
    }

   private Result Num(String s) throws Exception
   {
        int i = 0;
        int dot_cnt = 0;
        boolean negative = false;
        // число также может начинаться с минуса
        if( s.charAt(0) == '-' ){
            negative = true;
            s = s.substring( 1 );
        }
        // разрешаем только цифры и точку
        while (i < s.length() && (Character.isDigit(s.charAt(i)) || s.charAt(i) == '.')) {
            // но также проверям, что в числе может быть только одна точка!
            if (s.charAt(i) == '.' && ++dot_cnt > 1) {
                throw new Exception("not valid number '" + s.substring(0, i + 1) + "'");
            }
            i++;
        }
        if( i == 0 ){ // что-либо похожее на число мы не нашли
            throw new Exception( "can't get valid number in '" + s + "'" );
        }

        double dPart = Double.parseDouble(s.substring(0, i));
        if( negative ) dPart = -dPart;
        String restPart = s.substring(i);

        return new Result(dPart, restPart);
    }

    // Тут определяем все нашие функции, которыми мы можем пользоватся в формулах
    private Result processFunction(String func, Result r)
    {
        if (func.equals("sin")) {
            return new Result(Math.sin(Math.toRadians(r.acc)), r.rest);
        } else if (func.equals("cos")) {
            return new Result(Math.cos(Math.toRadians(r.acc)), r.rest);
        } else if (func.equals("tan")) {
            return new Result(Math.tan(Math.toRadians(r.acc)), r.rest);
        } else {
            System.err.println("function '" + func + "' is not defined");
        }
        return r;
    }
} 


И при вызове:

        String[] formulas = new String[] { "2+2*2", "2+X*2", "sin(90)+4-cos(0)", "2--4", "2**3*5-----7", "3.5.6-2" };
        MatchParser p = new MatchParser();
        p.setVariable("X", 2.0 );
        for( int i = 0; i < formulas.length; i++){
            try{
                System.out.println( formulas[i] + "=" + p.Parse( formulas[i] ) );
            }catch(Exception e){
                System.err.println( "Error while parsing '"+formulas[i]+"' with message: " + e.getMessage() );
            } 
        }

Выведет:
2+2*2=6.0
2+X*2=6.0
sin(90)+4-cos(0)=4.0
2--4=6.0
Error while parsing '2**3*5-----7' with message: can't get valid number in '*3*5-----7'
Error while parsing '3.5.6-2' with message: not valid number '3.5.'


Скачать весь проект можно тут ( спасибо flexoid за подсказку, куда можно сохранить архив)
Спасибо за внимание!
Александр @shushu
карма
26,0
рейтинг 0,2
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (25)

  • +3
    Спасибо, прочитал на одно дыхании. Продолжайте в том же духе))
  • +14
    Кажется, у вас проблемы с java.
    • +9
      И с русским языком тоже.
      • +5
        Извините, но я старался, честно!
  • +1
    Спасибо за статью.

    P.S. Code Conventions наверное не читали? Тестов не хватает в проекте, нормальных junit-тестов, хотя бы.
  • +2
    > посоветуйте пожалуйста хостинг, куда можно залить архив код
    github.com, bitbucket.org
    • 0
      Спасибо за наводку, учту в следующий раз. Пока залил на народ.
  • +8
    Я, глядя на иллюстрацию, ждал от статьи большего.
    • +3
      это ведь не Шелдон
  • +4
    > Хочу поделится с вами реализацией алгоритма «Метод рекурсивного спуска» на примере написания парсера формул с поддержкой переменных и функций на языке Java

    Складывается впечатление, что вы не до конца понимаете разницу между алгоритмом для решение конкретной задачи и общей для многих задач идеей.

    Иными словами, некорректно говорить об алгоритме «Метод рекурсивного спуска».
    • 0
      Согласен с Вами, возможно я несколько не так выразился. Наверное было бы лучше написать:

      «Хочу поделится с вами реализацией парсера математических формул с поддержкой переменных и функций на основе алгоритма „Метод рекурсивного спуска“?
      • +1
        Человек хотел сказать, что «Метод рекурсивного спуска» — это метод, не алгоритм. Т.е. это общая идея, например, как «метод деления пополам», «разделяй и властвуй» или динамическое программирование. Это не конкретные алгоритмы, это подходы к решению задачи.
  • +1
    Задача хорошая, на 1м курсе такое решали. Рекомендую вам поработать над дизайном кода.
  • –4
    Неделя парсинга формул на хабре!
  • +10
    И ни слова про грамматики. Советую, вместо того чтобы читать подобные статьи в интернете, взять нормальную книжку по теме.
  • +2
    Честно говоря не понял в чем тут заключается метод рекурсивного спуска, какой-то код, что-то в него вносим, что-то он выдает.

    Кстати, как сказали выше, о термах, грамматике ни слова.
  • +8
    Но Вы ведь знаете о существующих готовых парсерах грамматики? Например, ANTLR, с которым весь описанный выше функционал (парсинг выражений вида "(1+2)*3+4*5+6*sin(0.7)") выражается несколько проще:

    grammar extcalc;

    /*------------------------------------------------------------------
    * PARSER RULES
    *------------------------------------------------------------------*/

    expr : plusminus* EOF ;

    plusminus
    : multdiv ( ( '+' | '-' ) multdiv )* ;

    multdiv : factor ( ( '*' | '/' ) factor )* ;

    factor : NUMBER | func | '(' plusminus ')' ;

    func : NAME '(' plusminus ')' ;

    /*------------------------------------------------------------------
    * LEXER RULES
    *------------------------------------------------------------------*/

    NUMBER : (DIGIT)+ ('.' (DIGIT)+)* ;
    NAME : (ALPHA)+ ;

    WHITESPACE : ( '\t' | ' ' | '\r' | '\n'| '\u000C' )+ { $channel = HIDDEN; } ;

    fragment DIGIT : '0'..'9' ;

    fragment ALPHA : 'a'..'z' ;
    • +1
      Я думаю, автор ставил целью описать, как именно работает анализатор, изнутри. Готовые парсеры тут ни к месту. Но у него это, на мой взгляд, получилось не слишком хорошо — отсутствуют любые признаки теории.
      Вообще, в этой теме, код — совсем не главное, потому что он получается довольно простой. Важно знание основ.
  • +3
    Всё-таки, в реальных случаях лучше использовать нормальные решения по парзингу, а не рекурсивный спуск. Мне до сих пор стыдно за то, что в DN OSP используется мой старый вычислитель на базе рекурсивного спуска :(
  • 0
    Почему он "--" понимает, а "**" нет?
    • 0
      например: есть выражение: 4--4
      Парсер воспринимает это как: 4 — (-4), а что должно значить **?
      Кстати заметьте, 4++4 он также не пропустит
      • 0
        Это степень.
        • 0
          Намного проще и естественней для обозначения степени использовать "^"
          Для того что бы разобраться как это работает, предлагаю добавить поддержку степени самостоятельно.
  • 0
    а что это у вас за формула для привлечения внимания?
    • 0
      Просто обычная трёхэтажная формула) Выглядит вроде эффектно.
      Извините если ввел вас в заблуждение и вы ожидали чего-то большего.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.