Инфикс в Postfix с поддержкой функций

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

Я также написал реализацию Java для того же самого.

Кроме того, есть несколько замечаний по поводу этой реализации:

1. Этот алгоритм предполагает поток токенов в инфиксе. Он не анализирует строку выражения. Таким образом, каждый токен может быть идентифицирован как операнд, оператор, вызов функции и т. д.

2. Существует 7 различных видов токенов:

   • Operands X, Y etc
   • Левая парантеза - (
   • Правая парантеза - )
   • Операторы - +, *
   • Начинается вызов функции - sin(
   • Завершение вызова функции - sin( x )
   • запятая - ,

3. Начало вызова функции обозначается в алгоритме символом [, а окончание вызова функции обозначается символом ]. Обратите внимание, что завершение вызова функции — это другой токен, чем правая скобка ), хотя они могут быть представлены одним и тем же символом в строковом выражении.

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

5. #P8#

   f(a,b,c)
   
   first comma separates a and b
   second comma separates a,b and c
   
   So the postfix for the above will be 
   ab,c,f
   

   <блочная цитата> #P9#

Алгоритм

infix_to_postfix(infix):

    postfix = []
    infix.add(')')
    stack = []
    stack.push('(')
    for each token in infix: 
        if token is operand:
            postfix.add(token)
        if token is '[':
            stack.push(token)
        else if token is operator:
            if stack is empty OR 
               stack[top] is '(' or stack[top] is '[':
                stack.push(token)
            else if (operator)token['precedence'] > stack[top]['precedence'] OR
               ( (operator)token['precedence'] == stack[top]['precedence'] AND 
                 (operator)token['associativity') == 'RIGHT' ):
                stack.push(token)     
            else
                postfix.add(stack.pop())
                stack.push(token)
        else if token is '(':
            stack.push(token)
        else if token is ')':            
            while topToken = stack.pop() NOT '(':
                postfix.add(topToken)
        else if token is ']':
            while True:
                topToken = stack.pop()
                postfix.add(topToken)
                if topToken is '[':
                    break

        else if token is ',':
            while topToken = stack.peek() NOT '[':
                postfix.add(topToken)
                stack.pop()
            stack.push(token)

Это довольно просто: он работает и с функциями, обычные операторы, которые вы используете (например, +,-,*), тоже являются функциями. Ваша проблема в том, что то, что вы считаете «функцией» (например, грехом), находится не в инфиксе, а в префиксе.

Чтобы вернуться к вашей проблеме: просто преобразуйте эти функции префикса в постфикс (вы также должны найти префикс к постфиксу в Интернете - я предполагаю, что вы не знаете термин «префикс») заранее.

РЕДАКТИРОВАТЬ: По сути, это не что иное, как сначала преобразовать аргументы и вывести их последовательно, а затем добавить имя функции.

Код вам придется разработать самостоятельно. Использование вашего конкретного случая в качестве примера может помочь вам начать; постфиксная форма sin(x + y) * z будет:

х у + грех г *

Обратите внимание, что в этом примере одни операции работают с двумя значениями (+ и *), а другие с одним (sin)

бинарные операторы, такие как +, можно рассматривать как +(x,y) Аналогично. Рассмотрим функции sin, cos и т. д. как унарные операторы. Итак, sin(x+y)*z можно записать как x y + sin z *. Вы должны уделить особое внимание этим унарным функциям.

Хотя алгоритм @mickeymoon, похоже, работает, мне все же пришлось внести некоторые коррективы (у меня это не сработало), поэтому я думаю, что это может быть полезно для кого-то в другой реализации (Java-подобная реализация). На основе https://en.wikipedia.org/wiki/Shunting-yard_algorithm

Stack<Token> stack = new Stack<>();
List<Token> result = new ArrayList<>();
//https://en.wikipedia.org/wiki/Shunting-yard_algorithm
// with small adjustment for expressions in functions. Wiki example works only for constants as arguments
for (Token token : tokens) {
    if (isNumber(token) || isIdentifier(token)) {
        result.add(token);
        continue;
    }
    if (isFunction(token)) {
        stack.push(token);
        continue;
    }


    // if OP(open parentheses) then put to stack
    if (isOP(token)) {
        stack.push(token);
        continue;
    }
    // CP(close parentheses) pop stack to result until OP
    if (isCP(token)) {
        Token cur = stack.pop();
        while (!isOP(cur)) {
            if (!isComma(cur)) {
                result.add(cur);
            }
            cur = stack.pop();
        }
        continue;
    }
    if (isBinaryOperation(token)) {
        if (!stack.empty()) {
            Token cur = stack.peek();
            while ((!isBinaryOperation(cur)
                    || (isBinaryOperation(cur) && hasHigherPriority(cur, token))
                    || (hasEqualPriority(cur, token) && isLeftAssociative(token)))
                    && !isOP(cur)
            ) {
                // no need in commas in resulting list if we now how many parameters the function need
                if (!isComma(cur)) {
                    result.add(cur);
                }

                stack.pop();
                if (!stack.empty()) {
                    cur = stack.peek();
                }
            }
        }
        stack.push(token);
        continue;
    }

    if (isComma(token)) {
        Token cur = stack.peek();
        while (!(isOP(cur) || isComma(cur))) {
            result.add(cur);
            stack.pop();
            if (!stack.empty()) {
                cur = stack.peek();//  don't pop if priority is less
            }
        }
        stack.push(token);

    }
}
while (!stack.empty()) {
    Token pop = stack.pop();
    if (!isComma(pop)) {
        result.add(pop);
    }

}
return result;

Я протестировал его с различными сложными выражениями, включая композицию функций и сложные аргументы (не работает с примером из алгоритма Wiki). Пара примеров(e просто переменная, min,max, rand - функции):

Ввод: (3,4+2^(5-e))/(1+5/5)

Вывод: 3,4 2 5 e - ^ + 1 5 / + /

Ввод: 2+ранд(1,4+2, 3+4)

Вывод: 2 1,4 2 + 3 4 + ранд +

Ввод: макс(4+4,мин(1*10,2+(3-e)))

Вывод: 4 4 + 1 10 * 2 3 e - + мин. макс.

Я также протестировал его со сложной функцией с тремя аргументами (где каждый аргумент сам по себе является выражением), и все в порядке.

Вот github для моего функция Java, которая принимает список токенов и возвращает список токенов в постфиксной нотации. А вот и функция, которая получает результат первой функции и вычисляет значение выражения