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

shushu 22 июня 2011 в 01:01 52,1k


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

Хочу поделится с вами реализацией алгоритма «Метод рекурсивного спуска» на примере написания парсера формул с поддержкой переменных и функций на языке 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 за подсказку, куда можно сохранить архив)
Спасибо за внимание!
Проголосовать:
+44
Сохранить: