Проблемы с алгоритмом маневрового двора - PullRequest
Новая
       53

Проблемы с алгоритмом маневрового двора

6 голосов
/ 09 марта 2011

Я успешно реализовал алгоритм маневрового двора в Java.Сам алгоритм был прост, однако у меня возникли проблемы с токенизатором.В настоящее время алгоритм работает со всем, что я хочу, исключая одну вещь.Как определить разницу между вычитанием (-) и отрицанием (-)

, например, 4-3 - вычитание, а -4 + 3 - отрицательное

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

3 + 4 * 2 / - (1 - 5) ^ 2 ^ 3

, когда 1-5 становится -4, он становится 4, прежде чем его возводят в квадрат и кубируют

точно так же, как 3 + 4 * 2 / cos (1 - 5) ^ 2 ^ 3, вы бы взяли косинус, прежде чем возводить в квадрат и кубировать

, но в реальной математике вы бы не с - потому что на самом деле вы говорите 3 + 4 * 2 / - ((1 - 5) ^ 2 ^ 3) чтобы иметь правильное значение

Ответы [ 4 ]

9 голосов
/ 09 марта 2011

Звучит так, будто вы делаете парсер стиля lex-then-parse, где вам понадобится простой конечный автомат в лексере, чтобы получить отдельные токены для унарного и двоичного минуса. (В PEG-парсере вам не о чем беспокоиться.)

В JavaCC у вас будет состояние DEFAULT, где вы будете считать символ - UNARY_MINUS. Когда вы токенизируете конец первичного выражения (или закрывающее слово, или целое число, основываясь на приведенных вами примерах), вы переключаетесь в состояние INFIX, где - будет считаться INFIX_MINUS. Когда вы встретите какой-нибудь инфиксный оператор, вы вернетесь в состояние DEFAULT.

Если вы катаетесь самостоятельно, это может быть немного проще, чем это. Посмотрите на этот код Python , чтобы узнать, как это сделать. По сути, когда вы встречаете -, вы просто проверяете, был ли предыдущий токен инфиксным оператором. В этом примере используется строка "-u" для представления унарного минусового токена, что удобно для неформального токенизации. Насколько я могу судить, пример Python не справляется со случаем, когда - следует за открытым паренем или идет в начале ввода. Они также должны считаться одинарными.

Для того чтобы унарный минус был правильно обработан в самом алгоритме маневрового двора, он должен иметь более высокий приоритет, чем любой из инфиксных операторов, и он должен быть помечен как правоассоциативный. (Убедитесь, что вы обрабатываете ассоциативность справа. Возможно, вы не указали ее, поскольку остальные ваши операторы левоассоциативны.) Это достаточно ясно в коде Python (хотя я бы использовал некоторую структуру, а не две отдельные карты) .

Когда придет время оценивать, вам нужно будет обрабатывать унарные операторы немного по-другому, так как вам нужно всего лишь вытолкнуть одно число из стека, а не два. В зависимости от того, как выглядит ваша реализация, может быть проще просмотреть список и заменить каждое вхождение "-u" на [-1, "*"].

Если вы вообще можете следовать Python, вы сможете увидеть все, о чем я говорю, в примере, на который я ссылаюсь. Я считаю, что код немного проще для чтения, чем версия C, о которой кто-то упоминал. Кроме того, если вам интересно, я некоторое время назад немного писал об использовании shunting-yard в Ruby , но я рассматривал унарные операторы как отдельный нетерминал, поэтому они не отображаются.

3 голосов
/ 09 марта 2011

Ответы на этот вопрос могут быть полезны.

В частности, один из этих ответов ссылается на решение в C, которое обрабатывает унарный минус.

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

Оригинальная статья Дейкстры не слишком ясно объясняет, как он справился с этим, но унарный минус был указан как отдельный оператор.

1 голос
/ 04 октября 2012

В вашем лексере вы можете реализовать эту псевдологию: 

if (symbol == '-') {
    if (previousToken is a number 
     OR previousToken is an identifier 
     OR previousToken is a function) {
        currentToken = SUBTRACT;
    } else {
        currentToken = NEGATION;
    }
}

Вы можете установить отрицание, чтобы иметь приоритет выше, чем умножение и деление, но ниже, чем возведение в степень.Вы также можете установить правильную ассоциативность (как '^').Тогда вам просто нужно интегрировать приоритет и ассоциативность в алгоритм, как описано на странице Википедии.

Если токен является оператором, o1, тогда: пока есть токен оператора, o2, навершина стека, и либо o1 является левоассоциативным, и его приоритет меньше или равен приоритету o2, либо o1 имеет приоритет меньше, чем у o2, выталкивает o2 из стека в очередь вывода;нажмите o1 в стек.

Я закончил тем, что реализовал соответствующий код: 

} else if (nextToken instanceof Operator) {
    final Operator o1 = (Operator) nextToken;

    while (!stack.isEmpty() && stack.peek() instanceof Operator) {
        final Operator o2 = (Operator) stack.peek();

        if ((o1.associativity == Associativity.LEFT && o1.precedence <= o2.precedence)
         || (o1.associativity == Associativity.RIGHT && o1.precedence < o2.precedence)) {
            popStackTopToOutput();
        } else {
            break;
        }
    }

    stack.push(nextToken);
}

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

if (token is operator negate) {
    operand = pop;
    push operand * -1;
}

Пример проекта:

https://github.com/Digipom/Calculator-for-Android/

Дополнительная информация:

http://en.wikipedia.org/wiki/Shunting-yard_algorithm

http://sankuru.biz/blog/1-parsing-object-oriented-expressions-with-dijkstras-shunting-yard-algorithm

0 голосов
/ 11 ноября 2013

Я знаю, что это старый пост, но, возможно, кто-то найдет его полезным.Я реализовал этот алгоритм раньше, начиная с токнизера, используя класс StreamTokenizer, и он отлично работает.В StreamTokenizer в Java есть некоторые символы с определенным значением.Например: (является оператором, грех является словом, ... По вашему вопросу, существует метод с именем «streamToknizer.ndomChar (..)», который указывает, что символьный аргумент является «обычным» в этом токенизаторе.удаляет любое специальное значение, которое символ имеет в качестве символа комментария, компонента слова, разделителя строк, пробела или символа цифры. Источник здесь

Таким образом, вы можете определить - как обычный символ, который означает,это не будет считаться знаком для числа. Например, если у вас есть выражение 2-3, у вас будет [2, -, 3], но если вы не укажете его как обычное, оно будет [2, -3]

...