Разбор выражений с использованием бинарных операторов - PullRequest
Новая
       43

Разбор выражений с использованием бинарных операторов

2 голосов
/ 16 сентября 2011

Я пытаюсь выяснить способы анализа выражения, которое использует все бинарные операторы. Каждый оператор окружен ровно одним набором скобок, таким образом: 

5x^2 + 3x + 2

будет 

((5*(x^2))+((3*x)+2))

и принимается в качестве аргумента args [] (что более важно, он задается в виде строки).

Я рекурсивно разбираю это, где каждая рекурсия разбивает левую часть верхнего бинарного оператора и вызывает рекурсию с этим выражением в качестве аргумента, а затем снова с правым. Базовый случай - когда передаваемое выражение не содержит операторов.

У меня проблема в том, что я правильно разбираю левую и правую стороны. Я пытаюсь разработать способ, основанный на сканере, который подсчитывает общее количество скобок, но не может определить окончательное решение. У любого есть идея, как правильно разобрать это, чтобы передать это как выражение рекурсивному методу.

P.s. - Я использую язык * Java

EDIT ::::

Я использую этот синтаксический анализатор как часть графопостроителя графического интерфейса, поэтому я бы установил переменную (x) в зависимости от того, какое значение оси x я в данный момент ищу на графике графического интерфейса. Таким образом, выражение, анализируемое в программе (как показано во втором кодовом теге выше), будет разбито и использовано для получения окончательного значения "y", которое будет соответствовать позиции в окне, где будет использоваться маленькая точка представлять эту точку на линии графика.

Может быть, это лучше объяснит, как я пытаюсь это использовать.

Ответы [ 3 ]

2 голосов
/ 16 сентября 2011

Я бы начал с класса элементов 

interface Element {

}

и двух элементов 

abstract class Operator implements Element {

    Operand operate(Operand a, Operand b);

}

class Operand implements Element {
    int value;
    Operand(int value) { this.value = value; }
}

Теперь вы можете создать свою фабрику операторов 

class OperatorFactory {
    Operator createOperator(String symbol) {
         if("+".equals(symbol)) 
             return new Operator() {
                 Operator operate(Operand a, Operand b) { 
                     return new Operand(a.value + b.value);
                 }
             };
         if("-".equals(symbol)) /* continued */
    }
}

Теперь вы 'Вы можете сделать себе процессор стека, который повторяется, когда вы достигаете «(»), и работает, когда вы достигаете «)».Я думаю, что все остальное будет довольно тривиально.

1 голос
/ 16 сентября 2011

То, что вы хотите реализовать, - это простой синтаксический анализатор с рекурсивным спуском, что означает, что каждое производство вашей грамматики превратится в рекурсивную функцию, вероятно, похожую на то, что вы делаете в настоящее время.

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

Expression ::= Expression + Term
Expression ::= Expression - Term
Expression ::= Term

Term ::= Term * Factor
Term ::= Term / Factor
Term ::= Factor

Factor ::= number
Factor ::= ( Expression )

При этом вы можете видеть, что вы определяете выражение с помощью выражения, отсюда и использование рекурсивных функций.

Пожалуйста, прочитайте эту ссылку в Википедии, и вы сразу увидите, как реализовать то, что вы хотите. http://en.wikipedia.org/wiki/Recursive_descent_parser

0 голосов
/ 16 сентября 2011

Является ли ваша проблема с логикой или кодом?

В вашей логике я вижу только одну проблему: приоритет и ассоциативность также следует учитывать (в зависимости отоператор).

Если проблема с кодом, вы можете опубликовать код?Также поможет пример с ожидаемым выходным сигналом и фактическим выходным, поэтому мне не нужно помещать его в затмение и запускать его самому.

...