Алгоритм разбора алгоритма функции маневрового двора

Question

Я пытаюсь заставить мою реализацию алгоритма маневрового двора работать. Хорошо работает с числами и операторами. Но проблемы возникают, когда я пытаюсь добавить функции для ввода. Потому что аргумент функции выводится слева от функции, когда предполагается вывод справа.

Тестовая программа

public class FrontTest
{
    public static void main(String[] args)
    {
        String str = "cbrt ( 8 )";
        System.out.println(ShuntTest.infixToPostfix(str));
    }
}

Алгоритм

import java.util.*;

public class ShuntTest
{
    public static String infixToPostfix(String infixStr)
    {
        Stack<String> operators = new Stack<String>();
        Queue<String> output = new LinkedList<String>();
        String[] tokens = infixStr.split("[\\s]");
        StringBuilder postfixStr = new StringBuilder();
        int tokensRemaining = tokens.length;

        final String PAREN_LEFT = "[\\(]";
        final String PAREN_RIGHT = "[\\)]";
        final String FUNCTION_ARGSEP = "[\\;]";

        for (int i = 0; i < tokens.length; i++)
        {
            if (isNumber(tokens[i]))
            {
                output.offer(tokens[i]);
            }
            else if (isFunction(tokens[i]))
            {
                operators.push(tokens[i]);
            }
            else if (tokens[i].matches(FUNCTION_ARGSEP))
            {
                while (!operators.empty() && operators.peek().matches(PAREN_RIGHT))
                {
                    output.offer(operators.pop());
                    if (operators.empty() && !operators.peek().matches(PAREN_RIGHT))
                    {
                        throw new RuntimeException("Mismatched Parentheses.");
                    }
                }
            }
            else if (isOperator(tokens[i]))
            {
                while (!operators.empty() && ((isOperator(operators.peek())
                        && ((isLeftAssociative(tokens[i]) == true && ((operatorPrecedence(tokens[i]) <= operatorPrecedence(operators.peek()))
                        || ((isLeftAssociative(tokens[i]) == false && ((operatorPrecedence(tokens[i]) < operatorPrecedence(operators.peek())))))))))))
                {
                    output.offer(operators.pop());
                }
                operators.push(tokens[i]);
            }
            else if (!operators.empty() && tokens[i].matches(PAREN_LEFT))
            {
                operators.push(tokens[i]);
            }
            else if (!operators.empty() && tokens[i].matches(PAREN_RIGHT))
            {
                while (!operators.empty() && !operators.peek().matches(PAREN_LEFT))
                {
                    output.offer(operators.pop());
                }
                if (!operators.empty())
                    {
                        operators.pop();
                    }
                else if (!operators.empty() && isFunction(operators.peek()))
                {
                    output.offer(operators.pop());
                }
                else if (operators.empty())
                {
                    throw new RuntimeException("Mismatched Parentheses.");
                }
            }
            tokensRemaining--;
        }

        if (tokensRemaining == 0)
        {
            while (!operators.empty())
            {
                if (operators.peek().matches(PAREN_LEFT)
                        || operators.peek().matches(PAREN_RIGHT))
                {
                    throw new RuntimeException("Mismatched Parentheses.");
                }
                output.offer(operators.pop());
            }
        }

        while (!output.isEmpty())
        {
            while (output.size() > 1)
            {
                postfixStr.append(output.poll() + " ");
            }
            postfixStr.append(output.poll());
        }
        return postfixStr.toString();
    }

    public static boolean isNumber(String str)
    {
        final String NUMBER = "^0?-?\\+?\\d+(\\.\\d+)?$";
        return str.matches(NUMBER) ? true : false;
    }

    public static boolean isOperator(String str)
    {
        switch (str)
        {
            case "^":   
            case "/":
            case "*":
            case "+":
            case "-":
                return true;
            default:
                return false;
        }
    }

    private static boolean isLeftAssociative(String str)
    {
        switch (str)
        {
            case "^":   
                return false;   
            case "/":
            case "*":
            case "+":
            case "-":
                return true;
            default:
                throw new IllegalArgumentException("Operator unknown: " + str);
        }   
    }

    private static int operatorPrecedence(String str)
    {
        switch (str)
        {
            case "^":
                return 4;
            case "/":
            case "*":
                return 3;
            case "+":
            case "-":
                return 2;
            default:
                throw new IllegalArgumentException("Operator unknown: " + str);
        }   
    }

    public static boolean isFunction(String str)
    {
        switch (str)
        {   
            case "sin": 
            case "cos":
            case "tan":
            case "sqrt":
            case "cbrt":
            case "root_of":
                return true;
            default:
                return false;
        }   
    }
}

Пример 1:

Входные данные:cbrt ( 8 )

Выход:8 cbrt

Выход должен быть:cbrt 8

Пример 2:

Входные данные:cbrt ( 8 ) + sqrt ( 9 )

Выход:8 9 sqrt + cbrt

Выход должен быть:cbrt 8 sqrt 9 +

Пример 3:

Входные данные:5 + 4 - 9 / 2 ^ 6 * cbrt ( 8 )

Выход:5 4 + 9 2 6 ^ / 8 cbrt * -

Выход должен быть:5 4 + 9 2 6 ^ / cbrt 8 * -

Answer 1

Думаю об этом. Алгоритм маневрового двора преобразует инфикс в постфикс. Однако это:

cbrt ( 8 )

не является инфиксным выражением. Это префиксное выражение.

Как выражение postfix это будет выглядеть так:

8  cbrt

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